{"id":317,"date":"2009-05-31T01:59:02","date_gmt":"2009-05-31T06:59:02","guid":{"rendered":"http:\/\/vgable.com\/blog\/2009\/05\/31\/the-best-quicksort-ever\/"},"modified":"2009-05-31T01:59:05","modified_gmt":"2009-05-31T06:59:05","slug":"the-best-quicksort-ever","status":"publish","type":"post","link":"https:\/\/vgable.com\/blog\/2009\/05\/31\/the-best-quicksort-ever\/","title":{"rendered":"The Best Quicksort Ever"},"content":{"rendered":"

The first time I saw this quicksort in Haskell<\/a> was an eye opening moment,<\/p>\n

\n
 \nqsort []     = []\nqsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)\n<\/pre>\n
The first line reads: “When you sort an empty list ([]<\/code>), the result is another empty list”. The second line reads: “To sort a list whose first element is named x<\/code> and the rest of which is named xs<\/code>, sort the elements of xs<\/code> that are less than x<\/code>, sort the elements of xs<\/code> that are greater than or equal to x<\/code>, and concatenate (++<\/code>) the results, with x<\/code> sandwiched in the middle.”\n<\/p><\/blockquote>\n
The code is so concise, yet clear (even with cryptic variable names like xs<\/code>). The day my professor wrote it on the whiteboard was the first time I internalized that there might be something good about the alien<\/em> world of functional programming.<\/p>\n
The biggest revelation to me was, filter (< x) xs<\/code> . It’s amazing that (< x)<\/code> builds a temporary, unnamed, function equivalent to C++,<\/p>\n
bool lessThanX(AnyOrderedType y){\n    return y < X;\n}\n\/\/plus the definition of X somewhere...<\/pre>\n
Building a function!<\/em> It’s still profound stuff to me. And clearly it really uses fewer lines of code<\/strong>. Amazingly, using list comprehension<\/a> syntax is not more concise,<\/p>\n
qsort (x:xs) = qsort [i | i <- xs, i < x] ++ [x] ++ qsort [i | i <- xs, i <= x]<\/pre>\n
compared to the original,<\/p>\n
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)<\/pre>\n
I hope this is an ah-ah<\/em> moment for someone else too. I’d love to know what made you interested in functional programming; or if you know of a more elegant quicksort implementation.<\/p>\n","protected":false},"excerpt":{"rendered":"
The first time I saw this quicksort in Haskell was an eye opening moment, qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) The first line reads: “When you sort an empty list ([]), the result is another empty list”. The second line reads: […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,4,13],"tags":[432,430,326,69,431],"class_list":["post-317","post","type-post","status-publish","format-standard","hentry","category-design","category-programming","category-sample-code","tag-algorithms","tag-college","tag-functional-programming","tag-haskell","tag-quicksort"],"_links":{"self":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/317","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/comments?post=317"}],"version-history":[{"count":0,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/317\/revisions"}],"wp:attachment":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/media?parent=317"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/categories?post=317"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/tags?post=317"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}