Quicksort with 3-way partition

Question

What is QuickSort with a 3-way partition?

Uneven

Answer 1

Picture an array:

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

A two partition Quick Sort would pick a value, say 4, and put every element greater than 4 on one side of the array and every element less than 4 on the other side. Like so:

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

A three partition Quick Sort would pick two values to partition on and split the array up that way. Lets choose 4 and 7:

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

It is just a slight variation on the regular quick sort.

You continue partitioning each partition until the array is sorted. The runtime is technically nlog₃(n) which varies ever so slightly from regular quicksort's nlog₂(n).

Eccles

Now the interesting question is: "Under what conditions is a n-way QS better than a m-way QS?" – Curse

I suppose different partition amounts can work better in different cases. But 2 way seems to work well enough for me. – Eccles

Came across this post while doing my own research... I have to say I half agree with this answer. Yes, it is split into 3 partitions, but there is only ONE pivot, where each partition is either <,=,>. Doing the above partitioning doesn't seem to add any benefits above the standard 2 partition. Just my 2pence for whoever comes by googling. – Beetlebrowed

Edit: and now reading further there IS actually a dual-pivot partitioning algorithm, which is the current implementation in JDK7 which is apparently proven to be the most efficient strategy as of 2012. =) grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… – Beetlebrowed

@DarylTeo What do you mean there is only 1 pivot here? In my example I pick 4 and 7. Also, it's cool to see that this exercise I did for class forever ago has some real-world use. – Eccles

I meant that there are more than 1 partitioning algorithm. The 3 way partitioning (Bentley-McIlroy for example) only have 1 pivot, and is used to deal with duplicate keys. I was not aware of a dual pivot strategy, so I did research into it. =) So your comment helped me out. – Beetlebrowed

Indeed, 3-way partitioning can be 1-pivot or 2-pivot - see sorting-algorithms.com/quick-sort-3-way Was not aware about this before – Licketysplit

@jjnguy: log2 versus log3 doesn't sound like a good enough motive. Are there any other advantages, i.e. enhanced concurrency? Is it possible to run k-way quicksort on k threads? – Techy

@Techy You could fairly easily run k-way Quicksort on k threads. I'd imagine that you wouldn't gain much performance unless your data was huge. – Eccles

Regular quick sort's time is nlg(n) not lg(n). I think what you've mentioned here is Yaroslavskiy's dual pivot quicksort. 3-way quicksort is different java.dzone.com/articles/algorithm-week-quicksort-three – Shawanda

@v3ga thanks for pointing out my 5-year old mistake. I've updated it. Not sure about 3-way vs dual partition though. I think I provided the answer OP was looking for either way. – Eccles

I think you provided the answer he was looking for since both have 3 way partition. The single pivot 3 way version is used because qsort becomes O(n^2) if there are too many equal elements. JDK6 used 3 way quicksort (single pivot) and JDK7 uses dual pivot 3 way quicksort AFAIK. This thread is about the change. permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/… Providing the original papers for reference if anyone stumbles on this Question: skidmore.edu/~meckmann/2009Spring/cs206/papers/spe862jb.pdf iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf – Shawanda

@jinguy can't you describe more about this? I still confuse about this. Can you describe the full progress? (about the quicksort 3 ways, single pivot) Many thanks in advance! – Stratopause

@Stratopause You cannot have a 3 way quicksort with only 1 partition. I'm sure there are many other better online articles that can help you answer this better than I can now. My knowledge of algorithms peaked in '09. – Eccles

well thanks a lot, but I'm asking about the single pivot, not partition, well I searched and found a bunch of code, still struggling to visualize ==* – Stratopause

Just to clear up some confusion: In academic literature there is a binary partition, which splits the data into [<= v, >= v] (where v is a pivot). The pivot is usually swapped into the middle after the partitioning is complete. That's why it's only considered a binary scheme. There is a ternary scheme, which splits into [< v, = v, > v]. You can also do a ternary partition with two pivots, [<= u, >= u && <= v, >= v]. And finally a quintary partition [< u, = u, > u && < v, = v, > v]. Other schemes are typically implemented as combinations of these. – Influent

Partitioning on two pivots (either ternary or quintary) is faster only when 1/3rd of the data lies between the pivots, with high probability; otherwise, it will be about as fast as using a single pivot. For large inputs (> 1000) the pivots could be selected via random sampling to guarantee this property. For small inputs, the overhead of two pivots tends to outweigh the benefits. – Influent

Answer 2

http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

See also:

http://www.sorting-algorithms.com/quick-sort-3-way

I thought the interview question version was also interesting. It asks, are there four partition versions of quicksort...

Unders

This seems to be the correct answer. 3 way quick sort deals with performance when there are many duplicate keys. – Middelburg

Answer 3

I think the 3-way partition is by Djstrka.

Think about an array with elements { 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }.

Basically you set up 3 partitions: less than, equals to, and greater than a certain pivot. The equal-to partition doesn't need further sorting because all its elements are already equal.

---

For example, if we pick the first 3 as the pivot, then a 3-way partition using Dijkstra would arrange the original array and return two indices m1 and m2 such that all elements whose index is less than m1 will be lower than 3, all elements whose index is greater than or equal to m1 and less than or equal to m2 will be equal to 3, and all elements whose index is greater than m2 will be bigger than 3.

In this particular case, the resulting array could be { 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 }, and the values m1 and m2 would be m1 = 2 and m2 = 3.

Notice that the resulting array could change depending on the strategy used to partition, but the numbers m1 and m2 would be the same.

Dianthe

Answer 4

if you really grind out the math using Akra-Bazzi formula leaving the number of partitions as a parameter, and then optimize over that parameter, you'll find that e ( =2.718...) partitions gives the fastest performance. in practice, however, our language constructs, cpus, etc are all optimized for binary operations so the standard partitioning to two sets will be fastest.

Puduns

the standard partitioning to two sets will be fastest - citation needed – Umbel

Answer 5

I think it is related to the Dijkstra way of partitioning where the partition is of elemnts smaller, equal, and larger than the pivot. Only the smaller and larger partitions have to be sorted recursively. You can see an interactive visualization and play with it at the walnut. The colors I used there are red/white/blue because the method of partitioning is usually called "the dutch flag problem"

Ordinate

Answer 6

3 way quick sort basically partitions the array in 3 parts. First part is lesser than the pivot , Second part is equal to pivot and third part is greater than pivot.It is linear-time partition algorithm. This partition is similar to Dutch National Flag problem.

Alee

Answer 7

  //code to implement Dijkstra 3-way partitioning

  package Sorting;

  public class QuickSortUsing3WayPartitioning {

private int[]original;
private int length;
private int lt;
private int gt;

public QuickSortUsing3WayPartitioning(int len){
    length = len;
    //original = new int[length];

    original = {0,7,8,1,8,9,3,8,8,8,0,7,8,1,8,9,3,8,8,8};

}

public void swap(int a, int b){ //here indexes are passed
    int temp = original[a];
    original[a] = original[b];
    original[b] = temp;
}

public int random(int start,int end){
    return (start + (int)(Math.random()*(end-start+1)));
}

public void partition(int pivot, int start, int end){
    swap(pivot,start);  // swapping pivot and starting element in that subarray

    int pivot_value = original[start];
    lt = start;
    gt = end;

    int i = start;
    while(i <= gt) {

        if(original[i] < pivot_value) {
            swap(lt, i);
            lt++;
            i++;
        }

        if(original[i] > pivot_value) {
            swap(gt, i);
            gt--;
        }
        if(original[i] == pivot_value)
            i++;
    }
}

public void Sort(int start, int end){
    if(start < end) {

        int pivot = random(start,end); // choose the index for pivot randomly
        partition(pivot, start, end); // about index the array is partitioned

        Sort(start, lt-1);
        Sort(gt+1, end);

    }
}

public void Sort(){
    Sort(0,length-1);
}

public void disp(){
    for(int i=0; i<length;++i){
        System.out.print(original[i]+" ");
    }
    System.out.println();
}

public static void main(String[] args) {

    QuickSortUsing3WayPartitioning qs = new QuickSortUsing3WayPartitioning(20);
    qs.disp();

    qs.Sort();
    qs.disp();

}

}

Moslemism

why not initialize original in one line using {} notation ? Right now, it is ugly looking. – Uria

Please argue in the answer how it answers What is QuickSort with a 3-way partition?. This has also been called the "Dutch flag algorithm" - how about "dual pivot"? – Front

@Front this dual pivot a.k.a 3 way partitioning problem is a variant of famous "The dutch flag Algorithm" – Moslemism