patternMinor
Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?
Viewed 0 times
samethestrictlyandalgorithmsquicksortalgorithmworkspeakinghoare
Problem
For Hoare's partitioning algorithm quicksort is implemented as such
but Lomuto is
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.
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.
Solution
The term "Quicksort" stands for this abstract algorithmic idea:
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.
- Pick a value $x$.
- Partition the input into $\{y\mid y \leq x\}$ and $\{y \mid y > x\}$.
- 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.
Context
StackExchange Computer Science Q#29076, answer score: 5
Revisions (0)
No revisions yet.