3
$\begingroup$

For Hoare's partitioning algorithm quicksort is implemented as such

 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot);
        quickSort(array, pivot+1, last);

but Lomuto is

 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot-1);
        quickSort(array, pivot+1, last);

Notice the first one doesn't have pivot-1. Is it correct to call these two the same implementations of the quicksort algorithm? I'm having trouble rapping my head around the difference, I thought quicksort worked on the premise that after one call to it the pivot is in it's final place (so do +1 and -1 for the rest of the array) but Hoare's method doesn't seem to work like this.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

The term "Quicksort" stands for this abstract algorithmic idea:

  1. Pick a value $x$.
  2. Partition the input into $\{y\mid y \leq x\}$ and $\{y \mid y > x\}$.
  3. Recurse on the partitions (if they are non-trivial) and append the results.

You may want to generalise to multiple pivots, or create a third partition for elements equal the pivot, but mostly that's it.

There are many, many implementations. All of them are called "Quicksort", but many modify the name. See here for a discussion about the differences of these particular two variants.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Is it correct to call something like quicksort an algorithm? If an algorithm is a detailed step by step set of instructions, there is so much variability in quicksort depending on the partitioning method used and the pivot selection method. $\endgroup$
    – user20767
    Commented Aug 11, 2014 at 21:40
  • 1
    $\begingroup$ @Celeritas Well, all variants output the exact same thing, don't they? So, arguably, the description is precise enough -- to describe the algorithm, not its execution "on the metal". Also, there is no general consensus on the necessary level of detail; from what you'll find in mathematics lectures over CS-style pseudocode used in analysis all the way to "real" code or even machine code, every form has its use. See here for an example. $\endgroup$
    – Raphael
    Commented Aug 11, 2014 at 22:17
  • $\begingroup$ Disclaimer: different variants may output different things if we sort complex data with duplicate sorting keys; in particular, Quicksort is (usually) not stable. My earlier comment had pairwise distinct sorting keys resp. indistinguishable duplicate elements in mind. $\endgroup$
    – Raphael
    Commented Aug 12, 2014 at 5:51
  • 1
    $\begingroup$ Just because two programs output the same thing certainly does not mean they use the same algorithm. I guess what you're saying is the definition of algorithm is itself not strictly defined? $\endgroup$
    – user20767
    Commented Aug 12, 2014 at 8:51
  • 2
    $\begingroup$ You might prefer to call quicksort a family of algorithms but fussing over exactly what words to use isn't very productive. $\endgroup$
    – David Richerby
    Commented Aug 12, 2014 at 9:02