sorting and scrambling

thinking about sorting algorithms today and wondering whether in general a sorting algorithm can be reversed (with some randomness thrown in) to create a algorithm for effective shuffling. this might yield very efficient ways of scrambling things into random permutations, since sorting algorithms are highly efficient ways of transforming any one of all possible permutations into one unique one. you see, it's difficult to shuffle quickly and know that you have shuffled well enough not to have excluded any possible order of say a pack of cards.
thinking about quicksort (of which more about my personal adaptation anon) its clear that one single step is roughly analogous to the reverse of one 'riffle shuffle' of a pack of cards. how to invert the whole, recursive procedure is another story...

Comments: Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?