[erlang-questions] Speedy unsort:shuffle/1,2 ?

[Johan Montelius]

On Thu, 27 May 2010 02:47:03 +0200, Toby Thain <toby@REDACTED>  
wrote:

> It won't. Use Fisher-Yates or an equivalent method.
> http://en.wikipedia.org/wiki/Fisher–Yates_shuffle

Fisher-Yates (or the Knuth version) uses teh fact that you can access  
elements in an array and do the shuffling in O(n). If we have a list to  
shuffle the same algorithm will be O(n2) since we have to run down the  
list do find the element we want to shuffle.

If we are working with lists I think any solutions is a version of  
merge-sort or quick-sort and have a O(n*lg(n)) complexity.


-- 
Associate Professor Johan Montelius
Royal Institute of Technology - KTH
School of Information and Communication Technology - ICT