C ++ QuickSort Pivot Optimization

Actualmente, tengo una implementación básica del algoritmo de ordenación rápida para ordenar algunos números generados aleatoriamente. El ordenamiento es eficiente, más que el ordenamiento por fusión. Sin embargo, para conjuntos de números específicos (por ejemplo, números invertidos que deben ordenarse al revés), necesito optimizar el pivote.

int* partition (int* first, int* last); void quickSort(int* first, int* last) { if (last - first <= 1) return; int* pivot = partition(first, last); quickSort(first, pivot); quickSort(pivot + 1, last); } int* partition (int* first, int* last) { int pivot = *(last - 1); int* i = first; int* j = last - 1; for (;;) { while (*i < pivot && i = pivot && j > first) j--; if (i >= j) break; swap (*i, *j); } swap (*(last - 1), *i); return i; } 

Entonces, para este código, quiero usar un número aleatorio como pivote para el paso de partición, o usar la mediana de los elementos primero, medio y último como pivote.

¿Cómo haría esto?

Soy nuevo en la clasificación de algoritmos, y mi comprensión de ellos aún no está completa.

Solo cambia estas lineas:

  int pivot = *(last - 1); … swap ((last - 1), i); 

a algo como:

  int* pos = (first + rand(last - first)); int pivot = *pos; … swap (pos, i); 

o

  int* pos = mean_of_three((last - 1), (first), ((first + last) / 2)); int pivot = *pos; … swap (pos, i); 

donde mean_of_three toma 3 punteros y devuelve un puntero a la media.

Como ya ha mencionado, seleccionar el primer o último elemento de la matriz como pivote no es la mejor práctica y hace que el algoritmo caiga en O (n ^ 2). La mejor elección de algoritmo de selección de pivote depende de los datos que su progtwig pueda encontrar. Si existe la posibilidad de que los datos se ordenen o estén casi ordenados, entonces el pivote aleatorio es una muy buena opción (y muy fácil de implementar) para evitar el comportamiento O (n ^ 2). Por otro lado, el costo de seleccionar el elemento central en lugar del primero es mínimo y proporciona una protección bastante efectiva contra los datos ordenados.

Nuevamente, si está seguro de que sus datos no se ordenarán o casi se ordenarán, entonces la estrategia de partición de la mediana de tres parece ser la mejor.

 int PickPivotUsingMedian(int a[], int first, int last) { int mid = (first+ right)/2; if (a[mid ] < a[first]) swap(&a[first],&a[mid ]); if (a[last] < a[first]) swap(&a[first],&a[last]); if (a[last]< a[mid ]) swap(&a[mid ],&a[last]); swap(&a[mid], &a[last - 1]);//since the largest is already in the right. return a[last - 1]; } 

Elija un índice aleatorio dentro de los límites de su matriz y use ese elemento como el pivote.