Sorting as a Means of Shuffling in Racket

Racket is a derivative of Lisp, and it was also the language used in my first computer science class in college.  It is a functional language which encourages thinking in terms of composing simple functions to accomplish possibly complex goals.  When I was a lab assistant for the class, I recall having a conversation with the professor about how to shuffle a list of numbers in the language, and I came up with an interesting solution which I will talk about in this post.

In Racket, you can sort a list of anything by calling the sort function along with a list, and a function to compare any two items in the list.  An example use is (sort (list 4 1 3 2) <) which produces (list 1 2 3 4).  Since shuffling isn't natively supported in Racket and the simplest shuffling algorithms are not suitable for functional languages with lists instead of arrays, we have to be creative to achieve shuffling behavior.  My idea to shuffle a list was simple: replace the function to compare two items with a function that returns true or false randomly, independent of the inputs.  For example, (sort (build-list 25 identity) (lambda (x y) (< 0.5 (random)))) might produce (list 12 13 0 14 15 16 3 17 5 1 4 18 2 7 19 6 8 20 10 9 11 21 22 23 24) which appears somewhat random.  Upon closer inspection, however, there seem to be some obvious patterns that emerge.

Some sorting algorithms would produce very different outputs than others.  So one natural question I have is what is the distribution over shuffled sequences using the random compare function together with standard comparison-based sorting algorithms such as insertion sort, bubble sort, quick sort, and merge sort?  Can you tell based on the above random output which sorting algorithm Racket uses in the backend?  What if we iterated this shuffling algorithm $n$ times?  Would the distribution over input sequences converge to a uniform distribution or something else?  If you figure out the answer to any of these questions, please post them in the comments below!

Comments

Popular posts from this blog

Optimal Strategy for Farkle Dice

Markov Chains and Expected Value

Automatically Finding Recurrence Relations from Integer Sequences