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 

Una partición dos rápido Ordenado sería escoger un valor, por ejemplo 4, y poner todos los elementos superior a 4 en un lado de la matriz y cada elemento menos de 4 en el otro lado. De este modo:

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

Un tres partición rápido Ordenado recogerían dos valores de partición en la matriz y dividir 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 normal.

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 de quicksort regular (n).

Answer 2

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

Consulte también:

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

pensé que la versión pregunta de la entrevista también fue interesante. Se pide, are there four partition versions of quicksort ...

Answer 3

si realmente calcula los cálculos usando Akra-Bazzi formula dejando el número de particiones como parámetro, y luego optimiza sobre ese parámetro, encontrará 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 4

I thoguht la partición de 3 vías es por Djstrka.

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

básicamente el conjunto que hasta 3 particiones, menor que, igual a, y una 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 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

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. 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 the walnut. 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"