[Haskell-cafe] Linear shuffle

Scott Turner p.turner at computer.org
Fri Jan 14 09:06:55 EST 2005

The shuffling algorithms mentioned so far are comparable to 
insertion/selection sort. I had come up with a shuffler that relates to 
quicksort, in that it partitions the input randomly into lists and works 
recursively from there. It looks efficient and works out well in Haskell.

shuffle [] = return []
shuffle [c] = return [c]
shuffle deck0 = partition deck0 [] []
        partition [] p0 p1 = do
                s1 <- shuffle p0
                s2 <- shuffle p1
  return (s1 ++ s2)
        partition (d : deck) p0 p1 = do
  n <- randomRIO (0::Int,1)
  case n of
   0 -> partition deck (d : p0) p1
   1 -> partition deck p0 (d : p1)

Analogous to quicksort's bad behavior in the worst case, an invocation of 
'partition' is not guaranteed to make any progress with the shuffling, 
because one of the output lists might receive all of the input items.

More information about the Haskell-Cafe mailing list