Quicksort with 3-way partition

问题:

What is QuickSort with a 3-way partition?

回答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).

回答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...

回答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.

回答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.

回答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"

回答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.

回答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();

}

}