algorithm - metodos - Quicksort con partición de 3 vías

quicksort explicacion

Question

¿Qué es QuickSort con una partición de 3 vías?

Answer 1

Creo que está relacionado con la forma de partición de Dijkstra donde la partición es de elementos más pequeños, iguales y más grandes que el pivote. Solo las particiones más pequeñas y más grandes tienen que ser ordenadas recursivamente. Puede ver una visualización interactiva y jugar con ella en el nogal . Los colores que utilicé allí son rojo / blanco / azul porque el método de partición se suele llamar "el problema de la bandera holandesa".

Answer 2

Creo que la partición de 3 vías es de Djstrka.

Piense en una matriz con elementos {3, 9, 4, 1, 2, 3, 15, 17, 25, 17}

básicamente, configura 3 particiones, menos de, igual a, y mayor que. Giro de partición, todos los elementos menores que el pivote, más todos los elementos mayores que el pivote. Mueves todos los elementos que son iguales al pivote en su lugar.

Answer 3

Imagen de una matriz:

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

Una clasificación rápida de dos particiones elegiría un valor, digamos 4, y colocaría cada elemento mayor a 4 en un lado del conjunto y cada elemento menos de 4 en el otro lado. Al igual que:

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

Una ordenación rápida de tres particiones seleccionaría dos valores para la partición y dividiría la matriz de esa manera. Permite elegir 4 y 7:

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

Es solo una pequeña variación en el orden rápido regular.

Continúa la partición de cada partición hasta que se ordena la matriz. El tiempo de ejecución es técnicamente nlog ₃ (n), que varía muy poco de nlog ₂ (n) de quicksort regular.

Answer 4

Si realmente elaboras las matemáticas con la fórmula Akra-Bazzi, dejando el número de particiones como parámetro y luego optimizas ese parámetro, verás que las particiones e (= 2.718 ...) ofrecen el mejor rendimiento. en la práctica, sin embargo, nuestros constructos de lenguaje, cpus, etc. están optimizados para operaciones binarias, por lo que la partición estándar para dos conjuntos será más rápida.

Answer 5

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

Ver también:

sorting-algorithms.com/quick-sort-3-way

Pensé que la versión de la entrevista también era interesante. Pregunta, ¿hay cuatro versiones de partición de quicksort ...

Answer 6

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

}

}