Watrophy: code challenges by Robert Smith

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.

#28: QUOBOSORT