Talk:Sorting algorithms/Quicksort: Difference between revisions

: I'm glad to see you finally created an account (I've been following your FFF blog for a while), but I should mention that vitriol is unwelcome, and vitriolic arguments against particular languages fall directly outside my [[User:Short Circuit#Language Promotion|language advocacy]] policy. I've tried finding the original definition of Quicksort a few times, but the original paper is hidden behind a paywall. If the task description requires cleanup, then so be it, but access to an authoritative source is lacking. --[[User:Short Circuit|Michael Mol]] 19:45, 19 April 2010 (UTC)

:: The British Computer Society host [http://comjnl.oxfordjournals.org/cgi/content/short/5/1/10 Hoare's original 1962 paper]. In the paper, Hoare emphasizes the speed and memory efficiency of his quicksort algorithm and describes the algorithm explicitly in terms of pointers converging to the middle of the array and "exchanges" of pairs of elements that are in the wrong order and he uses the word "overwrites". In the Conclusion, he says "the data are sorted in situ". I'm sure variations on the theme are welcome but I would expect them to preserve the essence of the original and this bastardized out-of-place "quicksort" does not: it is asymptotically slower in theory (you're supposed to choose the pivot randomly!), hundreds of times slower in practice and consumes asymptotically more memory to the extent that it is practically useless (even the Haskell stdlibs do not use it!). At the very least, I recommend marking the fake quicksorts to avoid confusion. Ideally, demand real quicksorts (preferably parallel and generic) and [http://www.haskell.org/haskellwiki/Introduction/Direct_Translation watch the Haskellers squirm]! --[[User:Jdh30|Jon Harrop]]

 

==Algorithm description==