Quicksort con 3-way partizione

StackOverflow https://stackoverflow.com/questions/941447

  •  06-09-2019
  •  | 
  •  

Domanda

Che cosa è Costituto con un 3-way partizione?

È stato utile?

Soluzione

Immagine un array: 

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

Un due partizioni rapido Ordina sarebbe scegliere un valore, diciamo 4, e mettere ogni elemento superiore a 4 su un lato della matrice e ogni elemento inferiore a 4 sul lato opposto. In questo modo: 

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

tre partizione diretti Ordina sarebbe scegliere due valori di partizione sul e dividere la matrice in quel modo. Consente di scegliere 4 e 7: 

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

E 'solo una leggera variazione sul regolare quick sort.

Si continua divisione di ogni partizione fino a quando l'array è ordinato. Il runtime è tecnicamente nlog 3 (n) che cambia leggermente da nlog di quicksort regolare 2 (n).

Altri suggerimenti

se davvero macinare la matematica utilizzando Akra-Bazzi formula lasciando il numero di partizioni come parametro, e quindi ottimizzare su tale parametro, ci si accorge che e (= 2.718 ...) partizioni dà le prestazioni più veloci. in pratica, tuttavia, la nostra costrutti del linguaggio, cpu, ecc sono tutti ottimizzati per le operazioni binarie in modo che il partizionamento standard per due set sarà più veloce.

Penso che il 3-way partizione è da Djstrka.

Pensare a una matrice con elementi { 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }.

Praticamente puoi impostare 3 partizioni:minore di, uguale a, maggiore di un certo pivot.Il pari-per la partizione non ha bisogno di ulteriore differenziazione perché tutti i suoi elementi sono già uguali.

Per esempio, se prendiamo il primo 3 come il perno, quindi un 3-way partizione utilizzando Dijkstra vorresti organizzare l'array originale e ritorno due indici m1 e m2 tale che tutti gli elementi il cui indice è inferiore a m1 sarà inferiore 3, tutti gli elementi il cui indice è maggiore o uguale a m1 e inferiore o uguale a m2 saranno pari a 3, e tutti gli elementi il cui indice è maggiore di m2 sarà più grande di 3.

In questo caso particolare, la matrice risultante potrebbe essere { 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 }, e i valori m1 e m2 sarebbe m1 = 2 e m2 = 3.

Si noti che la matrice risultante potrebbe cambiare a seconda della strategia utilizzata per la partizione, ma i numeri m1 e m2 sarebbe lo stesso.

Credo che è legato al modo in cui Dijkstra della partizione in cui la partizione è di elemnts minore, uguale, e più grande del pivot. Solo le partizioni più piccole e più grandi devono essere ordinati in modo ricorsivo. È possibile vedere una visualizzazione interattiva e giocare con lui a noce . I colori che ho usato ci sono rosso / bianco / blu perché il metodo di partizionamento viene di solito chiamato "il problema olandese flag"

3 modo rapido suddivide sorta fondamentalmente la matrice in 3 parti. Prima parte è minore del pivot, seconda parte è uguale a ruotare e la terza parte è maggiore di pivot.It è algoritmo partizione lineare-tempo. Questa partizione è simile al problema olandese Bandiera Nazionale. 

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

}

}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top