Quicksort con partición de 3 vías

Question

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

Answer 1

imagen una matriz:

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

dos particiones Ordenación rápida escogería un valor, por ejemplo 4, y poner todos los elementos superior a 4 en un lado de la matriz y cada elemento de menos de 4 en el otro lado. De esta manera:

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

tres partición Ordenación rápida recogería dos valores de partición en la matriz y se separaron de esa manera. Vamos a elegir 4 y 7:

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

Es sólo una ligera variación en la ordenación rápida regular.

Se 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 ligeramente de nlog de quicksort regulares ₂ (n).

Answer 2

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

Vea también:

http://www.sorting-algorithms.com/quick-sort- 3 vías

Me pareció la versión pregunta de la entrevista también fue interesante. Se pregunta, hay cuatro versiones de partición de la clasificación rápida ...

Answer 3

si realmente moler a cabo los cálculos utilizando fórmula Akra-Bazzi dejando el número de particiones como un parámetro, y luego optimizar sobre ese parámetro, se encuentra que el correo (= 2,718 ...) particiones da el rendimiento más rápido. En la práctica, sin embargo, nuestro construcciones del lenguaje, CPU, etc están optimizados para operaciones binarias por lo que la partición estándar para dos conjuntos será más rápido.

Answer 4

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

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

Básicamente se establecieron 3 particiones: menor que, igual a, y mayor que un cierto pivote. La partición igual a no necesita clasificando porque todos sus elementos ya son iguales aún más.

---

Por ejemplo, si tomamos la primera 3 como el pivote, a continuación, una partición de 3 vías usando Dijkstra arreglaría la matriz original y volver dos índices m1 y m2 de tal manera que todos los elementos cuyo índice es inferior a m1 será menor que 3, todos los elementos cuyo índice es mayor que o igual a m1 y menor o igual a m2 será igual a 3, y todos los elementos cuyo índice es mayor que m2 será más grande que 3.

En este caso particular, la matriz resultante se puede { 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 }, y los valores m1 y m2 sería m1 = 2 y m2 = 3.

Tenga en cuenta que la matriz resultante podría cambiar dependiendo de la estrategia utilizada para la partición, pero los números m1 y m2 sería el mismo.

Answer 5

Creo que está relacionado con la forma de Dijkstra partición donde la partición es de elemnts menor, igual, y mayor que el pivote. Sólo las particiones más pequeñas y más grandes tienen que ser ordenados de forma recursiva. Se puede ver una visualización interactiva y jugar con él en la nuez . Los colores que utilicé no son de color rojo / blanco / azul porque el método de partición se suele llamar "el problema holandés de la bandera"

Answer 6

3 manera rápida especie básicamente divide el array en 3 partes. La primera parte es menor que el pivote, segunda parte es igual a pivotar y tercera parte es mayor que pivot.It es algoritmo de partición en tiempo lineal. Esta partición es similar al problema de la bandera nacional holandesa.

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

}

}