An Efficient way of randomizing an array - Shuffle code

Question

Hi,

I was asked this question in an interview and I gave various solutions but the interviewer was not convinced. I am interested to find a solution. Please throw in your views :

Q: Write an efficient data structure to implement the shuffle in an ipod. It must play all the songs, each time in different random order, the same song should not be repeated. ( mostly O(n))

One solution , I thought off after the interview : I can do a randomized quick sort without recursion. Where we randomly, chose 1 pivot O(1) and then do quicksort O(n). Now songs will be sorted in some order and I play them till the end. Once it reaches the end, I will Again chose a random pivot and , repeat this process again and again.

Regards, Sethu

Answer 1

Place all the songs in an array... For each element in the array swap it with a random position.

Answer 2

Well, the first linear-time solution that springs to mind:

You could make a linked list of all the songs, which would take about O(n) (given that insertions are constant time operations). Then, generate a random number, modulo the size of the list to get a random index, and remove that index and append it to a new list (both of which are constant time operations).

An insertion for each O(n) + a removal for each O(n) + a second insertion O(n). This would overall lead to a linear time solution.

Edit: I completely forgot about walking the list. So, instead, you could make the result a fixed length array. Pop the head of the linked list, assign it the random index, and populate the array.

Answer 3

Nate's (edited) and Brian's algorithms are the Fisher–Yates shuffle O(n), while shuffling by sorting is O(nlogn), but may actually be faster in practice (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Comparison_with_other_shuffling_algorithms). Getting song shuffling wrong may have insignificant consequences, but if you are writing a shuffling algorithm for an online poker game, make sure you know what you are doing (http://www.cigital.com/news/index.php?pg=art&artid=20).

Answer 4

You want the Fisher-Yates shuffle. Be aware of the implementation errors mentioned on that page, as your currently accepted answer falls foul of one.