Ordenación y búsqueda

Los algoritmos de ordenación se agrupan según la operación con la que consiguen colocar los datos. Saber a qué familia pertenece cada uno ahorra memorizar: el comportamiento y la complejidad se deducen casi siempre del mecanismo.

Selección busca qué elemento va en la posición actual; inserción busca en qué posición va el elemento actual. Es la pareja que más se confunde y la distinción es exactamente esa.

La burbuja compara elementos adyacentes y los intercambia si están en el orden equivocado, de manera que en cada pasada el mayor de los que quedan va desplazándose hasta el final, como una burbuja que sube. Es O(n²), pero admite una mejora clásica: si en una pasada completa no hace falta ningún intercambio, es que los datos ya estaban ordenados y el algoritmo puede terminar ahí. Con esa comprobación su mejor caso baja a O(n).

La inserción directa recorre la secuencia y, por cada elemento, busca su hueco entre los que ya están ordenados a su izquierda, desplazando a la derecha los que sean mayores. También es O(n²) y también tiene mejor caso O(n) cuando los datos ya vienen ordenados, porque entonces ningún elemento se mueve. Es el algoritmo que mejor se comporta con listas casi ordenadas o muy pequeñas.

La selección directa busca el mínimo de toda la parte pendiente y lo intercambia con la primera posición sin colocar, luego el mínimo del resto, y así sucesivamente. Su peculiaridad es que siempre hace el mismo número de comparaciones, estén los datos como estén: es O(n²) en el mejor, el medio y el peor caso, sin excepción. A cambio, hace muy pocos intercambios, uno por pasada.

Burbuja e inserción bajan a O(n) si la entrada ya está ordenada; la selección no mejora nunca, porque para saber cuál es el mínimo tiene que mirarlos todos igualmente.

Mergesort aplica divide y vencerás: parte la lista por la mitad una y otra vez hasta llegar a trozos de un solo elemento, que ya están ordenados por definición, y luego fusiona esos trozos de dos en dos comparando sus cabezas. Como la partición es siempre por la mitad, su coste no depende de los datos: es O(n log n) en los tres casos. El precio lo paga en memoria, porque la fusión necesita un vector auxiliar del tamaño de los datos.

Quicksort también divide, pero de otra forma. Elige un elemento como pivote y reorganiza el resto dejando a la izquierda los menores y a la derecha los mayores, con lo que el pivote queda ya en su posición definitiva. Después se aplica lo mismo a cada mitad. En caso medio es O(n log n) y en la práctica es el más rápido de los generales, pero si el pivote elegido resulta ser siempre el menor o el mayor, las particiones quedan totalmente desequilibradas y el coste sube a O(n²). De ahí la importancia de la estrategia de elección del pivote: primero, último, central, aleatorio o mediana de tres.

funcion quicksort(v, izq, der):
    si izq >= der: salir
    p = particion(v, izq, der)   // deja el pivote en su posición definitiva
    quicksort(v, izq, p - 1)     // menores que el pivote
    quicksort(v, p + 1, der)     // mayores que el pivote

Heapsort se apoya en el montículo: mete todos los datos en un max-heap y después extrae n veces el máximo, que sale siempre por la raíz y deja el montículo reequilibrado. Cada extracción cuesta O(log n) y hay n extracciones, de donde sale su O(n log n) garantizado en el peor caso, que es su gran ventaja sobre quicksort. Además ordena sobre el propio array, sin memoria auxiliar.

Shell sort es una inserción por pasos: en lugar de comparar elementos contiguos, compara elementos separados por un salto que va reduciéndose hasta valer 1, momento en el que hace una inserción directa sobre datos ya casi colocados. Los saltos grandes mueven de golpe elementos que estaban muy lejos de su sitio, y por eso mejora a la inserción simple. Su complejidad depende de la secuencia de saltos que se elija.

Los algoritmos de distribución no comparan elementos entre sí: los reparten en cajones según algún criterio derivado del propio valor. Esa es su diferencia esencial con todos los anteriores.

Bucket sort (o bin sort) divide el rango de valores en intervalos y manda cada elemento al cajón que le corresponde: por ejemplo, un cajón para 0 a 99, otro para 100 a 199 y así sucesivamente. Después ordena el contenido de cada cajón, aplicando el mismo reparto de forma recursiva con intervalos más finos o usando otro algoritmo, y concatena los cajones en orden. Con datos bien repartidos es prácticamente lineal, O(n + k) siendo k el número de cajones; si todos los elementos caen en el mismo cajón, degenera a O(n²).

Radix sort ordena por cifras. Distribuye los números en diez cajones según un dígito, los recoge en orden y repite con el dígito siguiente. Si empieza por el dígito menos significativo se llama LSD, y si empieza por el más significativo, MSD. Su coste es O(n·k), donde k es el número de dígitos de los números a ordenar, así que no depende de comparaciones sino de la longitud de las claves.

Está demostrado que ningún algoritmo que ordene comparando elementos puede bajar de Omega(n log n) en el peor caso. Radix y bucket parecen contradecirlo, pero no comparan: por eso pueden ser lineales, a cambio de exigir claves con una estructura concreta (dígitos, rangos acotados).

Esta tabla es lo que más se pregunta del tema y lo que peor se retiene sin verlo junto. Conviene fijarse en la última columna: lo que distingue a quicksort de mergesort y heapsort no es el caso medio, que es el mismo, sino el peor caso.

Los dos únicos de esta lista con O(n log n) garantizado también en el peor caso son mergesort y heapsort. Quicksort no lo garantiza, y aun así suele ser el más rápido en la práctica porque sus constantes ocultas son muy pequeñas.

Además de por su mecanismo, los algoritmos de ordenación se clasifican por tres criterios que se preguntan por separado.

• Interno o externo: el interno trabaja con todos los datos cargados en memoria principal; el externo ordena volúmenes que no caben en memoria y tiene que apoyarse en fichero, leyendo y escribiendo por bloques.
• Natural: es natural el que aprovecha el orden que ya traen los datos, de modo que si la entrada está ordenada termina antes. La burbuja con detección de ordenado y la inserción directa lo son; la selección no, porque hace el mismo trabajo pase lo que pase.
• Estable: es estable el que conserva el orden relativo previo entre elementos con la misma clave. Si dos registros empatan, el que estaba antes sigue estando antes.

La estabilidad importa cuando se ordena por varios criterios encadenados. Si una lista de empleados se ordena primero por nombre y después por departamento con un algoritmo estable, dentro de cada departamento los empleados siguen apareciendo por nombre. Con un algoritmo no estable ese primer orden se pierde.

La búsqueda secuencial o lineal recorre los elementos uno a uno hasta encontrar el buscado o agotar la colección. No exige nada a los datos y es O(n).

La búsqueda binaria exige dos condiciones: que los datos estén ordenados y que se pueda acceder a cualquier posición de un salto. Cumplidas esas dos, mira el elemento central, lo compara con el buscado y descarta la mitad que no puede contenerlo. Repitiendo, el intervalo se reduce a la mitad en cada paso y el coste es O(log n).

funcion busquedaBinaria(v, x):
    izq = 0
    der = longitud(v) - 1
    mientras izq <= der:
        medio = (izq + der) div 2
        si v[medio] = x:   devolver medio
        si v[medio] < x:   izq = medio + 1
        si no:             der = medio - 1
    devolver -1          // no está

Esa misma idea se puede aplicar dentro de la inserción directa: en vez de buscar secuencialmente el hueco de cada elemento, se busca con búsqueda binaria. La variante se llama inserción binaria y reduce las comparaciones a O(n log n). Ahora bien, el algoritmo completo sigue siendo O(n²), porque una vez localizado el hueco hay que desplazar físicamente todos los elementos posteriores, y eso no lo arregla ninguna búsqueda.