Home » Java » Core Java » Quicksorting – 3-way and Dual Pivot

About Arun Manivannan

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.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

and many more ....

One comment

  1. 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

Your email address will not be published. Required fields are marked *

*


seven − = 3

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Do you want to know how to develop your skillset and become a ...

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!
Get ready to Rock!
To download the books, please verify your email address by following the instructions found on the email we just sent you.

THANK YOU!

Close