Clarify the swap criteria in a Quicksort?

0
votes

In a quicksort, the idea is you keep selecting a pivot. And you swap the a value you find on the left that is greater than the pivot with a value you find on the right which is less than the pivot. see: ref

Just want to be 100% sure what happens in the following cases:

  • No value on left greater than pivot, value on right less than pivot
  • Value on left greater than pivot, no value on right less than pivot
  • No value on left greater than pivot, no value on right less than pivot
2
algorithmsortingquicksort
You should re-read the stuff that Lars Vogel states in his post, seems you didn't understand the algorithm completely. – Thomas Jungblut
Actually, Vogel's implementation is flawed. Since it is not moving the pivot to its final position, the pivot may end up in some pretty inconvenient positions that doesn't follow his own algorithm explanation – Alexander
@Alexander yes his partitioning implementation seems wrong. – Thomas Jungblut
It would be better if you refer a standard book for algorithms like 'Cormen' or 'Mark Allen Weiss' – banarun
Robert Sedgewick's Algorithms web site has extensive discussion and several Quicksort implementations in Java. – Blastfurnace

2 Answers

0
votes

While the choice of the pivot value is important for performance, it is unimportant for sorting.

Once you've chosen some value as the pivot, you then move all values smaller than or equal to the pivot to the left of the pivot and to the right of it you end up with all values greater than the pivot.

After all these moves, the pivot value is in its final position.

Then you recursively repeat the above procedure for the sub-array to the left of the pivot value and also for the sub-array to the right of it. Or course, if the sub-arrays have 0 or 1 elements in them, there's nothing to do with them, nothing to sort.

So in this way you end up choosing a bunch of pivot values which get into their final positions after all the moves. Between those pivot values are empty or single-element sub-arrays that don't need sorting as described previously.

0
votes

The swap criteria depend on the implementation. What happens in the three cases you mention depends on the partitioning scheme. There are many implementations of Quicksort, but the main two best known ones (in my opinion) are:

  • Hoare's Partition: The first element is the pivot, and two index variables (i and j) walk the array (a[])towards the center while the elements they encounters are less than / greater than the pivot. Then a[j] and a[i] are swapped. Note that in this implementation the swap happens for elements that are equal to the pivot. This is believed to be important when your array contains many identical entries. After i and j cross, a[0] is swapped with a[j], so the pivot goes between the smaller-or-equal-to partition and larger-or-equal-to partition.

  • Lomuto's partition. This is the one implemented in pseudo-code in the current Wiki quicksort entry under "In-place version". Here pivot could be anything (say a median, or a median of three), and is swapped with the last element of a. Here only i "walks" toward the end of the array: whenever a[i]>=pivot it is swapped with a[j] and j is decremented. At the end, the pivot is swapped with a[i+1]

(See here for instance for an illustration).

Robert Sedgewick chamions a three way partitioning scheme, where the array is divided into three partitions: less than, equal to, and greater than the pivot: the claim is that it has better performance on arrays with lots of dupes, or identical values. It is implemented yet differently (see the link above).