CAPÍTULO 5: ALGORITMOS DE SORTEO AVANZADOS
En el capítulo 4, introducimos algoritmos que sortean n números reales en una complejidad de tiempo entre Ω(n) y O(n2).
En este capítulo introduciremos 3 algoritmos avanzados, de los cuales uno de ellos, MergeSort no sortea in place [1], con un tiempo asintótico de Θ(n log n).
HeapSort hace uso de un Heap para sortear n números in place en Θ(n log n) y QuickSort, que igualmente actúa in place, pero para sortear n números tarda en worst case O(n2).
QuickSort
Pese a tener una complejidad de tiempo O(n2), QuickSort es un algoritmo muy popular y en varios casos la opción más practica puesto que es muy eficiente en su caso medio (Average Case) y los factores escondidos en esa complejidad son bastante pequeños, es por esto por lo que QuickSort tiene ventaja como algoritmo in place.
El principio de QuickSort lo resumimos de la siguiente manera:
- Escoger un elemento como pivot. (el pivot será el elemento que se sorteara en cada llamado de la función
preparePartition(…), en nuestra implementación escogemos el último elemento y recorremos el array desde atrás, pero también se puede escoger cualquiera, de hecho para que el algoritmo funcione óptimamente, debería escogerse un elemento aleatorio para cada llamado de la funciónpreparePartition(…)) - Partir el array en 3 partes: Primera parte donde todos los elementos son menores que el pivot (sin importar el orden). Segunda parte donde se encuentra únicamente el pivot ya sorteado. Tercera parte donde todos los elementos aquí son más grandes o iguales al pivot.
- Ahora aplicamos recursivamente Quicksort de nuevo para la primera y la tercera parte.
Entendiendo PreparePartition(...)
Esta función es la parte más importante del algoritmo y se llamara para cada parte del array recursivamente mediante la función quicksort(…):
- Escogemos el último elemento del array como pivot. (Línea 10)
- Nuestro pointer
pde ayuda lo colocamos a una posición después del último elemento. (Línea 12) - Recorriendo de derecha a izquierda el array para cada elemento:
Si este elemento es mayor o igual que nuestro pivot, corremos nuestropde ayuda una posición a la izquierda e intercambiamos este elemento con el elemento a donde apunta nuestrop. - Después de recorrer toda esa partición, intercambiamos el último elemento (nuestro pivot) con el elemento apuntado por
p.
Implementación de QuickSort
namespace QuickSort {
void swap(int& a, int& b) {
int h = b;
b = a;
a = h;
}
void preparePartition(int a[], int f, int l, int& p) {
// Use the last element as Pivot-Element
int pivot = a[l];
//set the pointer to the next to the last element
p = l + 1;
//go throgh the array backwards
for (int i = l; i >= f; i--) {
if (a[i] >= pivot) {
p--;
swap(a[i], a[p]);
}
}
// Pivot on the rigth Pos.
swap(a[l], a[p]);
}
void quicksort(int a[], int f, int l) {
int part;
if (f < l) {
preparePartition(a, f, l, part);
quicksort(a, f, part - 1);
quicksort(a, part + 1, l);
}
}
}
Ejemplo: Animación sorteando con QuickSort
Análisis de la complejidad de QuickSort
El número de pasos que efectúa QuickSort está ligado a la elección del elemento pivot.
Continua en la parte 2 siguiendo este enlace:
https://thewhitecode.com/blog/3913
___________
[1] Un algoritmo sortea In place, cuando solo un numero constante de elementos del input array son sorteados fuera de este.
[2] El elemento con el índex más alto en el array entre los valores que aún no están sorteados.
[3] Al colocar un nuevo elemento en la raíz, tenemos que asegurarnos que el Heap siga siendo válido, bajando por el árbol recursivamente y acomodando este valor en una posición donde se cumplan las condiciones del Heap, en este caso MaxHeap.
[4] Largest permanece como índice intacto, pues la función swap cambia solo el elemento que está bajo este índice.
El Manual de los algoritmos y las estructuras de datos.
Este capítulo ha sido solo uno de 9 capítulos en total del libro.
Descarga el manual directamente desde este enlace:
https://leanpub.com/elmanualdelosalgoritmosylasestructurasdedatos
marcus.thompson
En producción mi regla es simple: casi nunca necesitas QuickSort a mano. Los stdlibs (intro sort: quick para datos grandes, insertion para subarreglos pequeños, heap como fallback anti-DoS) ya hacen ese trabajo. El valor de esta comparativa está en entender por qué cada uno se degradó en el caso que le tocó — eso es lo que te deja depurar un P99 raro a las 3 a.m.
marcus.thompson
Esto es exactamente lo que pasa en producción: Go y Rust usan variantes de introsort/quickselect en sus std::sort por el mismo motivo que mencionas arriba — quicksort promedio O(n log n) con constantes pequeñas, pero con el worst case que hay que tapar con un fallback a heapsort. Buen material de lectura, me queda la duda de si el capítulo 4 (complejidades Θ(n)) está en la serie o solo en el libro.
emilybuilds
Lo que más me gustó del análisis es que la complejidad está ligada a la elección del pivot, no al algoritmo en sí: el mismo QuickSort es Θ(n log n) en promedio y Θ(n²) en el peor caso. Como científica de datos lo traduzco así: la varianza del pivot es el enemigo. Ya leí la parte 1 de los algoritmos de la serie y espero con muchas ganas la comparación MergeSort vs HeapSort de la parte 2, que es donde se ve el tradeoff memoria vs in-place.
danielweber
La implementación en C++ es clara y PreparePartition explicado línea por línea vale oro. Mi objeción como estudiante de sistemas: elegir SIEMPRE el último elemento como pivot es el peor caso con arrays ya ordenados — O(n²) garantizado. En la práctica (y en los libros de texto) se usa median-of-three o pivot aleatorio, y de ahí sale IntroSort (el que usa std::sort de libstdc++). Ojalá la parte 2 lo mencione, porque es la pregunta de seguimiento que SIEMPRE te hacen.