### 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

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!

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!

Free Game

ReplyDeleteSteam Keys

Free Steam Keys

Game Giveaway

Game Steam Giveaway

Free Steam Game Giveaway

Superb Article, visit mine at

ReplyDeleteAgen DominoAgen PokerAgen ReferralPoker Live

ReplyDeleteSilahkan 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