Posteriormente a investigar con especialistas en esta materia, programadores de varias ramas y maestros dimos con la solución al problema y la dejamos plasmada en este post.
Solución:
El objetivo de Quicksort es encontrar un pivote que divida el array en dos piezas aproximadamente iguales. Ahí es donde obtienes el log(n) de.
Suponga que hay un array de tamaño n y en cada iteración puede dividir el array en partes iguales. Entonces tenemos:
T(n) = 2 * T(n / 2) + O(n)
= 4 * T(n/4) + 2 * O(n)
.
.
(log(n) steps)
.
.
= 2^log(n) * T(1) + log(n) * O(n)
= n * O(1) + O(n * log(n))
= O(n * log(n))
Ahora, si dividimos el array en tamaños dicen 1 y n-1, obtenemos:
T(n) = T(1) + T(n-1) + O(n) = T(n-1) + O(n)
= T(n-2) + O(n-1) + O(n)
= T(n-3) + O(n-2) + O(n-1) + O(n)
.
.
(n-1) steps
.
.
= T(1) + O(2) + O(3) + ... + O(n)
= O(1 + 2 + 3 + .... + n)
= O(n^2)
En el caso de que mencione, ambos de los siguientes no serán individualmente O(log(n)). Uno será O(1) y el otro sera T(n-1) Si el array está ordenado. Por lo tanto, obtendrías el O(n^2) complejidad.
quickSort(array, start, i-2); // should be constant time
quickSort(array, i, end); // should be T(n-1)
Y como @MarkRansom menciona a continuación, esto no es exclusivo de las matrices ordenadas. En general, si elige pivotes de tal manera que el array tiene particiones muy desiguales, se encontrará con las complejidades del peor de los casos. Por ejemplo, si el array no está ordenado, pero siempre eliges el máximo (o mínimo dependiendo de su implementación) para el pivote, se encontrará con el mismo problema.
QuickSort comienza moviendo todo lo que tiene un más alto valor que el valor pivote a la fin de la lista, y todo lo que tiene un más bajo valor para el comienzo de la lista.
Si el valor en su punto de pivote es el valor más bajo en la lista, entonces cada valor en la lista se moverá al final de la lista. Sin embargo, solo para determinar dónde mover todos esos valores se requiere O(n) trabaja. Si luego elige el segundo valor más bajo, y luego el tercer valor más bajo, etc., terminará haciendo O(n) trabaja n/2 veces. O(n²/2) simplifica a O(n²).
Por qué algunas personas sugieren tomar el primer elemento como un punto de pivote, otros dicen que elija el elemento del medio y algunos dirán que debe elegir el último elemento como su punto de pivote, ¿no sería diferente?
Todo es cuestión de intentar adivinar (sin escanear toda la lista) qué elemento es más probable que esté cerca del mediana de su conjunto de datos, lo que le brinda el mejor comportamiento posible.
- Si sus datos son totalmente aleatorios, no importa lo que elija: es igualmente probable que obtenga un buen punto de pivote y sus posibilidades de consecuentemente eligiendo el peor los puntos de pivote son muy delgados. Elegir el primer o el último valor es el mas simple opción que funciona.
- Si sus datos están preordenados (o en su mayoría), elegir el medio probablemente le dará uno de los mejores valores, mientras que elegir el primer o el último elemento le dará constantemente los peores puntos de pivote.
En la vida real, la probabilidad de tratar con datos que en su mayoría están preordenados es lo suficientemente alta como para que valga la pena la complejidad del código ligeramente mayor. Vale la pena leer la sección de Wikipedia sobre este tema.
A continuación se muestra una clasificación rápida que usa una mediana de 3 y limita la complejidad de la pila a O (log (n)) utilizando solo la recursividad en la parte más pequeña y luego retrocediendo para la parte más grande. En el peor de los casos, la complejidad del tiempo sigue siendo O (n ^ 2), pero esto requeriría una mediana de 3 para elegir repetidamente valores pequeños o grandes. La complejidad del tiempo se puede limitar a O (n log (n)) mediante el uso de la mediana de las medianas, pero la sobrecarga para esto hace que el caso promedio sea mucho más lento (me pregunto si termina más lento que el ordenamiento dinámico. Con la mediana de las medianas, definitivamente es más lento que el ordenamiento por combinación, pero un ordenamiento por combinación estándar necesita un segundo array del mismo tamaño o la mitad del tamaño del original array).
http://en.wikipedia.org/wiki/Median_of_medians
Introsort resuelve la complejidad de tiempo del peor de los casos al cambiar al ordenamiento de pila según el nivel de recursividad.
http://en.wikipedia.org/wiki/Introsort
typedef unsigned int uint32_t;
void QuickSort(uint32_t a[], size_t lo, size_t hi)
while(lo < hi)
size_t i = lo, j = (lo+hi)/2, k = hi;
uint32_t p;
if (a[k] < a[i]) // median of 3
std::swap(a[k], a[i]);
if (a[j] < a[i])
std::swap(a[j], a[i]);
if (a[k] < a[j])
std::swap(a[k], a[j]);
p = a[j];
i--; // Hoare partition
k++;
while (1)
while (a[++i] < p);
while (a[--k] > p);
if (i >= k)
break;
std::swap(a[i], a[k]);
i = k++;
// recurse on smaller part, loop on larger part
if((i - lo) <= (hi - k))
QuickSort(a, lo, i);
lo = k;
else
QuickSort(a, k, hi);
hi = i;