Algoritmos de ordenación
Ordenar es el ejemplo de manual para aprender a medir algoritmos: todos hacen lo mismo, pero unos tardan el cuadrado del número de datos y otros n log n. Con mil datos la diferencia apenas se nota; con un millón, es la diferencia entre medio segundo y varias horas.
Los métodos sencillos (burbuja, selección e inserción) se entienden en cinco minutos y son los que se piden en los exámenes de primero. Los rápidos (mergesort, quicksort, heapsort) usan divide y vencerás o un montículo. En la práctica se usa el de la biblioteca (Arrays.sort, sorted, Array.prototype.sort), que combina varios; pero saber cómo funcionan explica por qué Arrays.sort de objetos es estable y el de int no.
Los algoritmos
Ordenación por burbuja
Recorre el array comparando cada pareja de vecinos y los intercambia si están al revés: en cada pasada el mayor que queda «sube» al final como una burbuja. Sencillo, estable y O(n²).básico2 ejerciciosOrdenación por selección
En cada pasada busca el menor de la parte sin ordenar y lo intercambia con el primero de esa parte. Siempre O(n²) comparaciones, pero como mucho n − 1 intercambios. No es estable.básico2 ejerciciosOrdenación por inserción
Toma cada elemento y lo inserta en su sitio dentro de la parte ya ordenada de su izquierda, desplazando los mayores. O(n²) en general, pero casi O(n) si los datos ya vienen casi ordenados.básico2 ejerciciosMergesort (ordenación por mezcla)
Parte el array por la mitad, ordena cada mitad con la misma idea y mezcla las dos mitades ordenadas en una. Siempre O(n log n) y estable, a cambio de un array auxiliar.intermedio2 ejerciciosQuicksort (ordenación rápida)
Elige un pivote, deja a su izquierda los menores y a su derecha los mayores (el pivote queda en su sitio) y repite con cada lado. O(n log n) de media sin memoria extra; O(n²) con pivotes malos.intermedio2 ejerciciosHeapsort (ordenación por montículo)
Convierte el array en un montículo de máximos, un árbol guardado en el propio array con el mayor siempre en la raíz, y saca el mayor una y otra vez al final. O(n log n) siempre y sin memoria extra.avanzado2 ejerciciosCounting sort (ordenación por cuentas)
Ordena enteros de un rango pequeño sin compararlos: cuenta cuántos hay de cada valor y los coloca en orden según esas cuentas. O(n + k), lineal, y estable; es la base del radix sort.intermedio2 ejercicios
Cuál elegir
| Algoritmo | Mejor | Medio | Peor | Memoria extra | Estable |
|---|---|---|---|---|---|
| Ordenación por burbuja | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Ordenación por selección | O(n²) | O(n²) | O(n²) | O(1) | No |
| Ordenación por inserción | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Mergesort (ordenación por mezcla) | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí |
| Quicksort (ordenación rápida) | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heapsort (ordenación por montículo) | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort (ordenación por cuentas) | O(n + k) | O(n + k) | O(n + k) | O(k) | Sí |
Estable: los elementos iguales conservan su orden original (importa al ordenar por varias claves). k es el tamaño del rango de valores en counting sort.