Quicksorting – 3-way and Dual Pivot

It’s no news that Quicksort is considered one of the most important algorithms of the century and that it is the defacto system sort for many languages, including the Arrays.sort in Java.

So, what’s new about quicksort?

Well, nothing except that I figured just now (after 2 damn years of release of Java 7) that the Quicksort implementation of the Arrays.sort has been replaced with a variant called Dual-Pivot QuickSort. This thread is not only awesome for this reason but also how humble Jon Bentley and Joshua Bloch really are.

What did I do next?

Just like everybody else, I wanted to implement it and do some benchmarking – against some 10 million integers (random and duplicate).

Oddly enough, I found the following results :

Random Data :

  • Quick Sort Basic : 1222 millis
  • Quick Sort 3 Way : 1295 millis (seriously !!)
  • Quick Sort Dual Pivot : 1066 millis

Duplicate Data :

  • Quick Sort Basic : 378 millis
  • Quick Sort 3 Way : 15 millis
  • Quick Sort Dual Pivot : 6 millis

Stupid Question 1 :

I am afraid that I am missing something in the implementation of 3-way partition. Across several runs against random inputs (of 10 million) numbers, I could see that the single pivot always performs better (although the difference is less than 100 milliseconds for 10 million numbers).

I understand that the whole purpose of making the 3-way Quicksort as the default Quicksort until now is that it does not give 0(n2) performance on duplicate keys – which is very evident when I run it against duplicate input. But is it true that for the sake of handling duplicate data, a small penalty is taken by 3-way? Or is my implementation bad?

Stupid Question 2

My Dual Pivot implementation (link below) does not handle duplicates well. It takes a sweet forever (0(n2)) to execute. Is there a good way to avoid this? Referring to the Arrays.sort implementation, I figured out that ascending sequence and duplicates are eliminated well before the actual sorting is done. So, as a dirty fix, if the pivots are equal I fast-forward the lowerIndex until it is different than pivot2. Is this a fair implementation?

else if (pivot1==pivot2){
        while (pivot1==pivot2 && lowIndex<highIndex){
            lowIndex++;
            pivot1=input[lowIndex];
        }
    }

That’s it. That is all I did?

I always find the tracing of the algorithm interesting but with the number of variables in Dual Pivot quicksort, my eyes found it overwhelming while debugging. So, I also went ahead and created trace-enabled implementations (for all 3) so that I could see where the variable pointers currently are.

These trace-enabled classes just overlay where the pointers are below the array values. I hope you find these classes useful.

eg. for a Dual Pivot iteration

QuickSortTracing

The entire project (along with a few lame implementations of DSA) is available on github here. The quicksort classes alone could be found here.

Here’s my implementation of the SinglePivot (Hoare), 3-way (Sedgewick) and the new Dual-Pivot (Yaroslavskiy)

Single Pivot

Optimized-SinglePivot.png

package basics.sorting.quick;

import static basics.sorting.utils.SortUtils.exchange;
import static basics.sorting.utils.SortUtils.less;
import basics.shuffle.KnuthShuffle;

public class QuickSortBasic {

  public void sort (int[] input){

      //KnuthShuffle.shuffle(input);
      sort (input, 0, input.length-1);
  }

  private void sort(int[] input, int lowIndex, int highIndex) {

      if (highIndex<=lowIndex){
          return;
      }

      int partIndex=partition (input, lowIndex, highIndex);

      sort (input, lowIndex, partIndex-1);
      sort (input, partIndex+1, highIndex);
  }

  private int partition(int[] input, int lowIndex, int highIndex) {

      int i=lowIndex;
      int pivotIndex=lowIndex;
      int j=highIndex+1;

      while (true){

          while (less(input[++i], input[pivotIndex])){
              if (i==highIndex) break;
          }

          while (less (input[pivotIndex], input[--j])){
              if (j==lowIndex) break;
          }

          if (i>=j) break;

          exchange(input, i, j);

      }

      exchange(input, pivotIndex, j);

      return j;
  }

}

3-way

Optimized-3Way.png

package basics.sorting.quick;

import static basics.shuffle.KnuthShuffle.shuffle;
import static basics.sorting.utils.SortUtils.exchange;
import static basics.sorting.utils.SortUtils.less;

public class QuickSort3Way {

  public void sort (int[] input){
      //input=shuffle(input);
      sort (input, 0, input.length-1);
  }

  public void sort(int[] input, int lowIndex, int highIndex) {

      if (highIndex<=lowIndex) return;

      int lt=lowIndex;
      int gt=highIndex;
      int i=lowIndex+1;

      int pivotIndex=lowIndex;
      int pivotValue=input[pivotIndex];

      while (i<=gt){

          if (less(input[i],pivotValue)){
              exchange(input, i++, lt++);
          }
          else if (less (pivotValue, input[i])){
              exchange(input, i, gt--);
          }
          else{
              i++;
          }

      }

      sort (input, lowIndex, lt-1);
      sort (input, gt+1, highIndex);

  }

}

Dual Pivot

Optimized-DualPivot.png

package basics.sorting.quick;

import static basics.shuffle.KnuthShuffle.shuffle;
import static basics.sorting.utils.SortUtils.exchange;
import static basics.sorting.utils.SortUtils.less;

public class QuickSortDualPivot {

  public void sort (int[] input){
      //input=shuffle(input);
      sort (input, 0, input.length-1);
  }

  private void sort(int[] input, int lowIndex, int highIndex) {

      if (highIndex<=lowIndex) return;

      int pivot1=input[lowIndex];
      int pivot2=input[highIndex];

      if (pivot1>pivot2){
          exchange(input, lowIndex, highIndex);
          pivot1=input[lowIndex];
          pivot2=input[highIndex];
          //sort(input, lowIndex, highIndex);
      }
      else if (pivot1==pivot2){
          while (pivot1==pivot2 && lowIndex<highIndex){
              lowIndex++;
              pivot1=input[lowIndex];
          }
      }

      int i=lowIndex+1;
      int lt=lowIndex+1;
      int gt=highIndex-1;

      while (i<=gt){

          if (less(input[i], pivot1)){
              exchange(input, i++, lt++);
          }
          else if (less(pivot2, input[i])){
              exchange(input, i, gt--);
          }
          else{
              i++;
          }

      }

      exchange(input, lowIndex, --lt);
      exchange(input, highIndex, ++gt);

      sort(input, lowIndex, lt-1);
      sort (input, lt+1, gt-1);
      sort(input, gt+1, highIndex);

  }

}

 

Reference: Quicksorting – 3-way and Dual Pivot from our JCG partner Arun Manivannan at the Rerun.me blog.
Related Whitepaper:

Bulletproof Java Code: A Practical Strategy for Developing Functional, Reliable, and Secure Java Code

Use Java? If you do, you know that Java software can be used to drive application logic of Web services or Web applications. Perhaps you use it for desktop applications? Or, embedded devices? Whatever your use of Java code, functional errors are the enemy!

To combat this enemy, your team might already perform functional testing. Even so, you're taking significant risks if you have not yet implemented a comprehensive team-wide quality management strategy. Such a strategy alleviates reliability, security, and performance problems to ensure that your code is free of functionality errors.Read this article to learn about this simple four-step strategy that is proven to make Java code more reliable, more secure, and easier to maintain.

Get it Now!  

One Response to "Quicksorting – 3-way and Dual Pivot"

  1. exex zian says:

    I guess you should add this – http://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort

    As Java 7 uses Dual-Pivot Quicksort for primitives and TimSort for objects.

Leave a Reply


+ 9 = seventeen



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

15,153 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books