-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Fri, Oct 21, 2005 at 02:35:21AM +0000, n a wrote: > For anyone interested in dabbling in the functional programming I will > offer the following to egg you on: > > quicksort (p:xs) = quicksort [ x | x <-xs, x <= p ] > ++ [p] ++ > quicksort [ x | x <- xs, x >p ] > > these three lines represent the entire quicksort algorithm
You forgot empty set. ;-) I added a really concise version to wikipedia today in boredom. > quicksort [] = [] > quicksort (x:xs) = quicksort [y|y<-xs,y<x]++[x]++quicksort [y|y<-xs,y>=x] I wonder which is faster... doing <= first or doing >= last? Or is there any difference? I'm too tired to think... Before I edited the wiki I noticed one was incorrect and just did > without the =. So if you sorted like: Main> quicksort [1,2,5,8,5,2,10,-1] [-1,1,2,5,8,10] It would remove all duplicates. Which isn't really proper sorting ;) Adding it back in yields the expected solution: Main> quicksort [1,2,5,8,5,2,10,-1] [-1,1,2,2,5,5,8,10] Some interesting comparisons: http://en.wikipedia.org/w/index.php?title=Quicksort http://en.wikipedia.org/w/index.php?title=Quicksort_implementations It seems like the most obfuscated and concise is J: quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ [EMAIL PROTECTED])) ^: (1:<#) peace, core -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFDWHm8GAuLrxOyeJMRAsN9AJwOP72FZpXGnWCKYL+q95YwiqNRRgCdFkB5 SNd+DAdPeaXtS1YIv44gSyQ= =cbMS -----END PGP SIGNATURE----- _______________________________________________ RLUG mailing list [email protected] http://lists.rlug.org/mailman/listinfo/rlug
