Anonymous user
Talk:Sorting algorithms/Quicksort: Difference between revisions
→Algorithm description
Line 20:
Would someone care to add some text describing the Quicksort algorithm? I.e., its worst-case completion time, a pseudocode implementation, what the pivot does, etc. --[[User:Short Circuit|Short Circuit]] 03:28, 7 October 2007 (MDT)
: Quicksort is an elegant and powerful algorithm. If you want to learn about it, read the [http://comjnl.oxfordjournals.org/cgi/content/short/5/1/10 Hoare's original 1962 paper on Quicksort]. Note that the task description and code here on Rosetta Code and the Wikipedia article are wrong. --[[User:Jdh30|Jon Harrop]]
::If it wouldn't be too much trouble (since you seem to understand it yourself) could you maybe add a summary to this task then? It would be more convenient to have the proper sort on-site. --[[User:Mwn3d|Mwn3d]] 03:17, 26 May 2010 (UTC)
::: I'm not sure what you mean by a summary but I can certainly fix the task description if you like. The quicksort algorithm is very simple: you randomly choose a pivot and swap it with the last element in the current slice of the array, then you start pointers at either end of the slice and move them towards the middle swapping any pairs that are out of place until the pointers meet and, finally, recursively quicksort the lower and upper slices separated by the point the pointers converged on. Sedgewick gave a nice C++ implementation (without randomization) [http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf here] except for a bug where the array element should only be loaded within the 'if' statement. Here's the fixed code: --[[User:Jdh30|Jon Harrop]]
void quicksort(Item a[], int l, int r) {
if (r > l) {
int i = l-1, j = r;
Item v = a[r];
for (;;) {
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
}
== UnixPipes solution ==
| |||