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

  1. Silahkan di kunjungi ya kawan-kawan 100% Memuaskan
    > Hoki anda ada di sini <
    Bandar Q Online Terpercaya dan Teraman di GUNUNGPOKER
    Link daftar : http://bandaraduq.com/Register.aspx?lang=id
    BBM : 56978317

    SEMUA GAME HANYA PAKAI 1 USER ID : Poker, Domino QQ, Capsa Susun, Adu Q, Bandar Poker,

    Segera daftarkan userid anda di GUNUNGPOKER
    Promo Terbaru dari GUNUNGPOKER
    - Minimal DEPOSIT & WITHDRAW Rp 20.000,-
    - Tersedia 7 game dalam 1 USER ID
    - BONUS Turnover 0.5%
    - BONUS Referral 20%

    UNTUK INFORMASI SELANJUTNYA BISA HUB KAMI DI :
    LIVECHAT GUNUNGPOKER 24 JAM ONLINE
    Fanspage FB : @agengunungpoker
    Pin BB : 56978317
    WA : +62812-7287-4416
    LINE : gunungpokercsr1
    WECHAT : gunungpokercsr1
    YM : gunungpokercsr1@yahoo.com
    Agen domino
    BandarQ
    Domino 99
    Domino QQ
    Agen Poker
    Bandar Poker
    Agen Judi QQ
    Judi Online
    Forum Judi Online

    hubungi kami di :
    Line : gunungpokercsr1
    Bbm : 56978317
    Wa : +6281272874416

    ReplyDelete

Post a Comment

Popular posts from this blog

Efficiently Remove Duplicate Rows from a 2D Numpy Array

Multi-Core Programming with Java

Beat the Streak: Day Three