# Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?

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.

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.

• 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.
– user20767
Commented Aug 11, 2014 at 21:40
• @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. Commented Aug 11, 2014 at 22:17
• 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. Commented Aug 12, 2014 at 5:51
• 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?
– user20767
Commented Aug 12, 2014 at 8:51
• You might prefer to call quicksort a family of algorithms but fussing over exactly what words to use isn't very productive. Commented Aug 12, 2014 at 9:02