Tagged as challenge
Written on 2018-01-30
You happen upon the following note, which seems to describe a novel algorithm for sorting.
QUOBOSORT: a sort made by ROBERT SMITH aka STYLEWARNING Patents Pending. SUMMARY ------- Permute X until the minimum is in the first position of X. When this occurs, QUOBOSORT the rest of X until we reach an empty listte. ALGORITHM --------- QUOBOSORT(X) := -- INPUT: a list of integers X -- OUTPUT: sorted X in ascending order Q0. Is X an empty list? Yes: Return X. No : Go to Q1. Q1. Find the minimum M of X. Q2. Randomly permute X. Q3. Is M in the first position of X? Yes: Concatenate M and QUOBOSORT(REST(X)) No : Go to Q2.
Implement this algorithm.
Extra Credit: Analyse the time and memory complexity of this algorithm.