Talk:Sorting algorithms/Quicksort: Difference between revisions
→Fortran-90 code ... pivot choice can cause it to go O(N^2)
| (One intermediate revision by one other user not shown) | |||
Line 16:
:: 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]]
::: I already warned you once about vitriol. this site functions as well as it does because of cooperative behavior among participants, regardless of what they think of each others' preferred languages. If you have no intention of non-inflammatory and non-malicious participation, you'll find yourself unwelcome to the point of my exercising admin powers. Last warning on that front. As for the issues with the Quicksort task description, I'll leave that to others to discuss and debate. --[[User:Short Circuit|Michael Mol]] 09:47, 25 May 2010 (UTC)
::I made some measurements for the F# version which physically splits the list to be sorted into 2 new lists for one thousand to ten million elements as follows (x is a random number generator):
<pre>
> let n = List.init 1000 (fun _->x.Next());;
> qsort n;;
Real: 00:00:00.012, CPU: 00:00:00.020, GC gen0: 0, gen1: 0
> let n = List.init 10000 (fun _->x.Next());;
> qsort n;;
Real: 00:00:00.047, CPU: 00:00:00.040, GC gen0: 5, gen1: 0
> let n = List.init 100000 (fun _->x.Next());;
> qsort n;;
Real: 00:00:00.485, CPU: 00:00:00.660, GC gen0: 53, gen1: 2
> let n = List.init 1000000 (fun _->x.Next());;
> qsort n;;
Real: 00:00:05.200, CPU: 00:00:06.990, GC gen0: 602, gen1: 10
> let n = List.init 1000000 (fun _->x.Next());;
> qsort n;;
Real: 00:01:34.239, CPU: 00:02:01.510, GC gen0: 7331, gen1: 20
</pre>
which is a little worse than linear but not too bad, so the situation for Haskell may not be as bad as you think. I have 8 cores available to me and if I wanted to write a parallel version I'd prefer the copied list to the single array with pointers. Even using a single core swapping in place requires three read write operations: read i and write to temp; read j and write to i; read temp and write to i. Whereas copying to new lists can be done in one read and write.
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 17:17, 24 April 2018 (UTC)
==Algorithm description==
Line 68 ⟶ 88:
: The comments say just it's a good pivot choice for already sorted data or for reverse sorted data; I haven't checked it, but I can believe it, as I can believe it's not a so good choice for "symmetric triangle" distribution. --[[User:ShinTakezou|ShinTakezou]] 18:44, 26 June 2009 (UTC)
--[[User:Mecej4|Mecej4]] ([[User talk:Mecej4|talk]]) 01:06, 1 October 2022 (UTC)
The routine Qsort may get stuck in an infinite loop when the input array has two or more elements of equal value. For example:
L=4
A(1)%value = 2.0; A(2)%value = 1.0; A(3)%value = 3.0; A(4)%value=2.0
A(1)%order = 1; A(2)%order = 2; A(3)%order = 3; A(4)%order = 4
call Qsort(A, L)
== IDL ==
| |||