Quicksort mit 3-Wege-Partition

Question

Was ist QuickSort mit einer 3-Wege-Partition?

Answer 1

Bild ein Array:

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

A zwei Partition Quicksort Wert auswählen würde, sagen 4 und setzt jedes Element größer als 4 auf einer Seite des Arrays und jedes Element weniger als 4 auf der anderen Seite. Wie so:

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

A drei Partition Quicksort würde zwei Werte holen auf partitionieren und teilen das Array auf diese Weise. Wählen Sie 4 und 7:

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

Es ist nur eine leichte Variation der regulären schnellen Sortierung.

Sie fahren mit der Partitionierung jeder Partition fort, bis das Array sortiert ist. Die Laufzeit ist technisch nlog (n), die so leicht von normalen Quicksort nlog (n) variiert.

Answer 2

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

Siehe auch:

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

Ich dachte, die Interview-Frage Version auch interessant war. Es fragt are there four partition versions of quicksort ...

Answer 3

Wenn Sie wirklich die Mathematik mit Akra-Bazzi formula grinden die Anzahl der Partitionen als Parameter verlassen und dann über diesen Parameter optimieren, finden Sie, dass e (= 2.718 ...) Partitionen die schnellste Leistung bietet. In der Praxis sind jedoch unsere Sprachkonstrukte, CPUs usw. für binäre Operationen optimiert, so dass die Standardpartitionierung auf zwei Sätze am schnellsten ist.

Answer 4

Ich thoguht die 3-Wege-Partition ist von Djstrka.

Denken Sie über ein Array mit Elementen {3, 9, 4, 1, 2, 3, 15, 17, 25, 17}

grundsätzlich Sie 3 Partitionen eingerichtet, kleiner als, gleich zu sein, und einem größeren als. Partition pivot, alle Elemente kleiner als der Drehpunkt plus alle Elemente größer als der Drehpunkt Sie verschieben alle Elemente, die dem Drehpunkt entsprechen.

Answer 5

//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(); 

} 

} 

Answer 6

Ich denke, es ist mit der Dijkstra Art der Partitionierung verbunden, wo die Partition von Elementen kleiner, gleich und größer als der Drehpunkt ist. Nur die kleineren und größeren Partitionen müssen rekursiv sortiert werden. Sie können eine interaktive Visualisierung sehen und damit unter the walnut spielen. Die Farben, die ich dort verwendete, sind rot/weiß/blau, weil die Methode der Partitionierung normalerweise "das niederländische Flaggenproblem" genannt wird