QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?

Question

Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following happens:

Scenario: i -> "X", "X" > "P"

1. swap("X", "Z"), gt--;   // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--;   // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--;    // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

Why don't we just decrement gt until gt points to a value that is < the value at lt ("P" in this case), then we swap this value with the value at i. This will save swapping operations.

So if we do that for the scenario mentioned above, we'll do:

1. gt--
2. gt--
3. swap("X", "C"), gt--;   
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

Is this excessive swapping needed for the algorithm? does it improve performance in some way? If it does improve performance, how?

If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.

Also, would the second method I mentioned affect performance in any way? please explain why.

P.S. "Affect performance" as used above means either improve/degrade performance.

Answer 1

In order to know that you may just decrement gt, you have to compare the element at position gt to the pivot.

For illustration, here is the relevant part of the code from the slides you took your illustration from:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0) exch(a, i, gt--);
   else              i++;
}

Your modification would look like this:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0) 
   {
      while (a[gt].compareTo(v) > 0) gt--;
      exch(a, i, gt--);
   }
   else              i++;
}

If the element is larger, we save a swap, as you illustrated. Furthermore we won't have to compare that element again. If, however, the element is not larger, we will compare it to the pivot twice, once before the swap and once after the swap.

So with your modification we save a swap for each element that is larger than the pivot and on a position that ends up to the right of the pivot, while we introduce an additional comparison for each element in such a position that is not larger than the pivot.

Averaging over all inputs we can expect the number of elements smaller resp. larger than the pivot to be equal. So the performance will depend on the number of elements equal to the pivot (and the cost of a swap vs. a comparison). Your modification will have the better relative performance, the smaller that number is. But 3-way partitioning was developed with inputs with many equal keys in mind, so the original choice seems reasonable.

---

Taking a second look at the modified algorithm, we note that if we compare an element twice, there is no other comparison happening between these two. So it seems worthwhile to remember the result of the comparison. However, if we want to keep the structure of the code, this means a lot of control structure overhead:

Boolean doComp = true;
int cmp;
while (i <= gt)
{
   if (doComp) cmp = a[i].compareTo(v);
   doComp = true;
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0) 
   {
      while (cmp = a[gt].compareTo(v) > 0)
      {
         gt--;
         doComp = false;
      }
      exch(a, i, gt--);
   }
   else              i++;
}

My gut feeling is that even though it combines the advantages of the previous two versions in terms of number of comparisons and swaps, it will perform worse due to the overhead of the additional control structures.

Not only have we introduced additional operations (checking conditions, maintaining the flag), we also introduced (compared to Dijkstra's version) two additional conditional jumps (for if and while), that will often but irregularly switch between taken and not taken. The latter is a problem on modern processors, since they rely on branch predictions for optimal performance and such branches will lead to a high number of mispredictions. (The branch corresponding to the outer loop is an opposite example: Always predicting that the loop will be entered is wrong only once.)

With these considerations in mind, we can try to optimize the code. The following should perform quite well:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if (cmp > 0) 
   {
      while ((cmp = a[gt].compareTo(v)) > 0) gt--;
      exch(a, i, gt--);
   }
   if (cmp < 0) exch(a, lt++, i++);
   else         i++;
}

This version makes as many comparisons as Dijkstra's version and as many swaps as your suggested version without introducing too much overhead: For each comparison we have one branch based on cmp > 0 and possibly one based on cmp < 0. This is the same as for Dijkstra's version except that the role of the two comparisons is exchanged.

---

So, summing up / answering your final questions explicitly:

• The additional swaps you point out can be avoided without introducing other costs. So, as you suspected, they degrade performance compared to the final version in this answer.
• The version you suggest removes the unnecessary swaps, but introduces additional comparisons. So it will too perform worse than the final version in this answer.
• As I pointed out, the realitve performance of the original and your version will depend on the input at hand and the relative costs of swaps and compares. (Since usually compares are faster than swaps, I'd expect your version to be faster on average.)

Answer 2

Some Context and History

FrankW's post answers most of the question, but I can add some references and give some context to it.

First of all, the algorithm is named after Dijkstra because of his 1976 programming book “A Discipline of Programming”, wherein chapter 14 deals with the so-called “Dutch National Flag Problem (DNFP)”:

Rearrange an array of red, white and blue pebbles by swaps, such that their colors mimic the flag of the Netherlands.

The DNFP was intended as a programming exercise and is maybe not interesting per se.
What is often needed, however, is sorting an array, and this is often done using Quicksort (see this question if you are interested in why is quicksort better than other sorting algorithms in practice).

From flags to sorting

The crucial part in Quicksort is to partition an array around a pivot, i.e. rearrange the array to have small elements to the left, elements equal to the pivot in the middle and large elements to the right. — exactly like in the DNFP! Therefore, we can use the algorithms for the DNFP in the 3-way partitioning step for Quicksort.

Is this excessive swapping needed for the algorithm?

As the algorithm from FrankW's answer nicely demonstrates, the extra swapping is not needed. Dijkstra gives an enhanced version of the algorithm in his book that avoids the extra swap, as well.

I suppose that Sedgewick used the version with the extra swap to keep the code concise — for educational reasons, so to say.

What is “Performance”?

Does it improve performance in some way? If it does improve performance, how?

If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.

Also, would the second method I mentioned affect performance in any way? please explain why.

First of all, performance depends on the input, especially the length of the array; but also on the number of elements equal to the pivot and so on. To answer you question, you will have to fix an input model.

Secondly, it is not clear what exactly we mean by “performance” ...
If we are interested in total running time in seconds, then the answer will depend on the machine/processor you use, the compiler, potentially the Java Virtual Machine, the OS, other processes ...
There will not be a definite answer to the above questions then, but you might run some experiments on your machine.

For comparing two alternative algorithms, it might be enough to compare a coarser measure, like the number of executed instructions: If one algorithm needs much more instructions, it will (usually) also be slower.

Why Dijkstra's method is hardly used in practice

In the case of 3-way Quicksort, practical implementations (e.g. C++ standard library, Java 6 runtime library) use “fat partitioning”, a different partitioning scheme developed by Bentley and McIlroy (see their paper “Engineering a sort function”):

a = b = 0;
c = d = n-1;
for (;;) {
  while (b <= c && A[b] <= v) {
    if (A[b] == v) swap(A, a++, b);
    b++;
  }
  while (c >= b && x[c] >= v) {
    if (A[c] == v) swap(A, d--, c);
    c--;
  }
  if (b > c) break;
  swap(A,b++, c--);
}
s = min(a, b-a);
for(l = 0, h = b-s; s; s--) swap(A, l++, h++);
s = min(d-c, n-1-d);
for(l = b, h = n-s; s; s--) swap(A, l++, h++);

The invariant for the array is then

--------------------------
| = | <  |   ?   | > | = |
--------------------------

i.e. equal elements are put to the extreme ends and have to be swapped to the middle again at the end.

This method does in fact more swaps for many equal elements than your optimized Dijkstra partitioning. But it has almost no overhead for inputs without equal elements when compared to an optimized 2-way Quicksort; this is not the case for your algorithm: It would do roughly three times as many swaps on inputs without equal elements (see very similar computation here).

Dual-Pivot Quicksort

A second way how the DNFP can help in Quicksort is when we use two pivots instead of one. Then, each partitioning step rearranges the array such that small elements are left, elements between the two pivots go to the middle and large ones to the right.

You may find it interesting that the Java 7 runtime library uses dual-pivot Quicksort with a partitioning method that is essentially your algorithm from above!

Answer 3

FrankW's answer above clearly answers my question, however I would like to add an answer from the stackoverflow copy of my question for anyone who bumps into this question. Answer from Yu Hao on StackOverflow

You are right, the extra swap operations are not necessary, this algorithm here is best for clarity, but not for performance. See the discussion of Quick Sort (3 Way Partition).

In Quicksort is optimal by Robert Sedgewich himself, he has a different approach that uses much less swap operation, but you can imagine it also needs more code, and is less clear than the algorithm in the demo.

Answer 4

I was in a confussion while doing merge and quick sort and i read this article here that clears my all doubts about quick sort

http://geeksprogrammings.blogspot.com/2014/02/algorithm-quick-sort-program.html