Algoritmos de ordenación
Supón que sobre una mesa hay varias tarjetas con números y queremos ordenarlas de menor a mayor. Vemos el resultado deseado, pero un ordenador necesita que le digamos exactamente qué dos tarjetas revisar y cuál mover. Vamos a construir esas instrucciones paso a paso, con una pequeña decisión cada vez.
01Un resultado ordenado necesita un método repetible
Una lista es una fila de elementos en un orden concreto. Aquí, cada elemento es una tarjeta. Su valor es el número que usamos para comparar; su posición indica dónde está dentro de la fila. Mover una tarjeta cambia su posición, no el número escrito en ella.
Nuestro requisito es preciso: cada tarjeta debe ser igual o menor que la siguiente, y ninguna tarjeta puede perderse ni añadirse. Los valores iguales pueden estar juntos. Un conjunto finito de instrucciones inequívocas para completar esta tarea es un algoritmo. Vamos a estudiar cinco algoritmos de ordenación: cinco formas distintas de llegar al mismo tipo de resultado.
En cada experimento, el dorado marca las tarjetas que participan en el paso actual. El verde marca las posiciones que ya no necesitarán cambiar. Las letras identifican las tarjetas originales, así que dos tarjetas con un 2 se pueden distinguir. Siguiente paso muestra una decisión y una explicación de su motivo; al continuar se ve el cambio que provoca. Atrás restaura el estado anterior, incluidos los contadores.
02Ordenamiento burbuja: llevar un valor grande a la derecha
Empieza mirando solo dos tarjetas vecinas. Si la de la izquierda es mayor, intercámbialas; si no, déjalas como están. Ahora avanza una posición a la derecha y repite la acción. Tras comparar el 5 con el 2, el 5 se mueve a la derecha. Cuando después se encuentra con el 7, el valor mayor que sigue avanzando pasa a ser el 7. Por eso, al recorrer de izquierda a derecha, el valor mayor queda en el extremo derecho.
Estas tarjetas son la entrada. Las letras se mueven con las tarjetas, así que podemos distinguirlas aunque sus valores coincidan.
Ahora podemos dejar quieta esa última posición y repetir solo sobre la parte incompleta más corta. ¿Por qué termina siempre? Cada pasada completada fija una posición más, así que con una lista finita no repetiremos para siempre. Si una pasada no hace ningún intercambio, es que cada pareja de vecinas ya estaba en orden. Una tarjeta es entonces igual o menor que su vecina, que a su vez es igual o menor que la siguiente, y así hasta el final: toda la lista está ordenada. Eso permite detenerse antes.
03Ordenamiento por selección: decidir una posición final cada vez
También podemos elegir la primera tarjeta de otra manera: revisar todas las tarjetas restantes y recordar el valor más pequeño visto hasta ahora. Empieza recordando la primera. Cuando aparezca un valor más pequeño, sustituye la elección recordada. Solo cuando se hayan revisado todas las tarjetas restantes intercambiamos ese mínimo hasta la primera posición incompleta.
Estas tarjetas son la entrada. Las letras se mueven con las tarjetas, así que podemos distinguirlas aunque sus valores coincidan.
El valor recordado es realmente un mínimo porque cada tarjeta revisada se comparó con él, y el valor recordado solo puede hacerse más pequeño. Tras colocarlo, todos los valores restantes son iguales o mayores. Repite el proceso con la parte restante. Fíjate en una diferencia con el ordenamiento burbuja: incluso una fila ya ordenada necesita todas esas revisiones, porque este método no tiene una regla de «sin intercambios, terminado».
04Ordenamiento por inserción: conservar la parte ya ordenada
Una sola tarjeta ya está ordenada. Toma la siguiente y compárala con su vecina de la izquierda. Si esa vecina es mayor, intercámbialas y revisa la nueva vecina izquierda. Detente al llegar al principio o ante una vecina igual o menor que la tarjeta elegida. Así hemos insertado una tarjeta en el lugar correcto sin alterar el orden de las demás.
Estas tarjetas son la entrada. Las letras se mueven con las tarjetas, así que podemos distinguirlas aunque sus valores coincidan.
¿Por qué basta con detenerse ahí? Todo lo que queda más a la izquierda ya estaba ordenado, así que es igual o menor que la vecina donde nos detuvimos. Todo lo que cruzamos era mayor que la tarjeta elegida y ya se ha movido a su derecha. Por tanto, ambos lados cumplen el orden requerido. La parte ordenada crece una tarjeta cada vez hasta incluir toda la fila.
05Ordenamiento por mezcla: usar dos tareas pequeñas ya completadas
Supón que ya tenemos dos filas ordenadas. Para encontrar la tarjeta más pequeña que aún no hemos tomado, basta con comparar las tarjetas delanteras de las dos filas: todo lo que hay después en cada fila es igual o mayor que su propia primera tarjeta. Copia la primera tarjeta más pequeña en una fila nueva, avanza el frente de esa fila y repite. Cuando una fila se queda vacía, añade las tarjetas restantes de la otra fila en su orden actual. Esta operación se llama mezcla.
¿De dónde salen esas dos filas ordenadas? Divide la fila original en dos partes y aplica la misma tarea de ordenación a cada parte. Sigue dividiendo hasta que cada parte tenga una sola tarjeta. Esas tareas mínimas ya están completas, así que ahora podemos combinar hacia arriba: las partes de una tarjeta forman partes ordenadas de dos, y luego partes ordenadas mayores. Reutilizar la misma tarea con una entrada más pequeña se llama recursión; aquí cada entrada más pequeña tiene un lugar visible en el proceso.
Estas tarjetas son la entrada. Las letras se mueven con las tarjetas, así que podemos distinguirlas aunque sus valores coincidan.
La fila auxiliar guarda copias mientras las dos partes originales siguen disponibles para su lectura. Cuando termina una mezcla, copia su resultado de vuelta. Por eso la pantalla muestra temporalmente copias de una tarjeta; no significa que la lista final gane elementos. Esta implementación usa almacenamiento adicional, y el conteo incluye las escrituras en ese almacenamiento y las de vuelta a la fila principal.
06Ordenamiento rápido: colocar en su posición final una tarjeta que divida
Elige una tarjeta como pivote: un valor que usamos para dividir los demás. En esta demostración elegimos la última tarjeta. Recorre las demás tarjetas y reúne a la izquierda los valores menores que el pivote. Mantén una frontera después de ese grupo de valores menores. Cuando aparezca un valor menor, intercámbialo con la posición de la frontera y desplaza la frontera un lugar a la derecha.
Cuando termine el recorrido, coloca el pivote en la frontera. Todo lo que queda a su izquierda es menor; todo lo que queda a su derecha es igual o mayor. Por tanto, el pivote ocupa una posición final válida. Puede que los dos lados aún no estén ordenados, pero ahora se pueden ordenar por separado con el mismo procedimiento. Cada tarea recursiva excluye su pivote, así que se hace más pequeña y termina en algún momento.
La franja bajo las tarjetas muestra los tres grupos durante el recorrido: ya revisadas y menores, ya revisadas y no menores y aún sin revisar. El pivote espera aparte al final. Antes de cada comparación, la línea blanca de la frontera cierra el grupo de las menores y la flecha señala la siguiente tarjeta sin revisar. Cuando se clasifica la última tarjeta, ya no quedan tarjetas sin revisar. Puedes retroceder un paso para ver exactamente qué grupo creció.
Estas tarjetas son la entrada. Las letras se mueven con las tarjetas, así que podemos distinguirlas aunque sus valores coincidan.
El nombre no promete que toda entrada sea rápida. Prueba con la fila ya ordenada. Elegir su último valor, el mayor, deja una parte izquierda casi completa y una parte derecha vacía. Hemos reducido la tarea en solo una tarjeta. Otras estrategias para elegir el pivote pueden evitar muchos de esos casos, pero no hacen inmune a ellos a esta demostración concreta de la última tarjeta.
07Contar el trabajo y preguntar qué importa para esta tarea
Una comparación de valores pregunta cuál de dos números es mayor o si son iguales. Una escritura en el arreglo guarda un elemento en una posición. En estos contadores, intercambiar dos posiciones distintas requiere dos escrituras en el arreglo; la asignación a una variable temporal no se cuenta. Estos conteos explican lo que hizo esta implementación. No son segundos, y una comparación y una escritura no tienen por qué costar lo mismo.
Sea el número de tarjetas. Para elegir la tarjeta de la primera posición, el ordenamiento por selección necesita comparaciones. La siguiente posición necesita comparaciones, y después el número requerido disminuye en uno por cada posición que se fija, hasta llegar a . Llamemos a la suma de todos esos números. Si escribimos la suma hacia delante y hacia atrás, se forman columnas que suman cada una. Por tanto , y se obtiene . El ordenamiento burbuja y el de inserción también alcanzan ese número cuando todos los valores son distintos y estrictamente decrecientes; con valores repetidos no tiene por qué ocurrir. Nuestro ordenamiento rápido también lo alcanza con valores ordenados y distintos.
Primero tomemos en el ordenamiento por mezcla. De pasamos a , luego a y después a : en total 3 niveles. En cada nivel de mezcla, la suma de todas las partes es de tarjetas, y al copiar una tarjeta se compara como mucho una vez. Por eso es una cota superior, no un número exacto. En general, si , hay niveles y el número de comparaciones no supera . La notación indica cuántas veces hay que duplicar desde 1 para llegar a . Para otros tamaños enteros positivos, el número de niveles se redondea hacia arriba. Este es el origen de la conocida cota de crecimiento .
Hay otro requisito que la altura de las barras no puede mostrar. Supón que los valores iguales representan a personas con la misma puntuación y que la lista original ya está ordenada por orden de llegada. Puede que queramos conservar ese orden de llegada. Una ordenación es estable si conserva el orden relativo original de los elementos con valores iguales. Sigue las letras de las tarjetas iguales. El ordenamiento burbuja y este método de inserción solo mueven tarjetas intercambiando vecinas. Para que dos tarjetas iguales inviertan su orden, tendrían que adelantarse la una a la otra, y eso obligaría a intercambiar directamente esas dos vecinas en algún paso. Nuestra regla nunca intercambia valores iguales, así que esa inversión no puede ocurrir. El ordenamiento por selección y nuestro ordenamiento rápido sí pueden mover una tarjeta por delante de varias otras en un solo intercambio; pueden cruzar una tarjeta igual sin comparar directamente ese par.
En el ordenamiento por mezcla empezamos con partes de una sola tarjeta, donde ninguna pareja igual puede invertirse. Supón que las dos partes más pequeñas ya conservan el orden original de sus tarjetas iguales. Tomar solo la primera tarjeta de cada parte conserva ese orden dentro de la parte. Si las tarjetas iguales vienen de partes distintas, la parte izquierda ya estaba antes que la derecha, así que tomar primero la izquierda cuando son iguales también conserva su orden. De este modo, cada mezcla conserva la propiedad, hasta completar la fila entera.
| Método mostrado aquí | Propiedad útil | Limitación |
|---|---|---|
| Burbuja | Estable; termina tras una pasada sin cambios | Muchos intercambios en orden inverso |
| Selección | Como mucho un intercambio por posición final | Sigue revisando todas las tarjetas restantes; no es estable |
| Inserción | Estable; recorrido corto cuando casi está ordenada | Un nuevo mínimo atraviesa todo el prefijo ya ordenado |
| Mezcla | Estable; dividir de forma equilibrada acota el trabajo | Usa una fila auxiliar y copia de vuelta |
| Ordenamiento rápido con el último pivote | Divide dentro de la fila original | No es estable; las entradas ordenadas o con valores iguales se dividen mal |
El procedimiento rápido no necesita una fila auxiliar como la del ordenamiento por mezcla, pero sí un registro de las tareas recursivas pendientes. Por eso, al elegir un método hay que considerar los datos, la estabilidad y el almacenamiento requeridos, y también el número de comparaciones. Para aprovechar el orden, continúa con la lección de búsqueda.
Continuar con la búsqueda08Comprueba si puedes explicar el siguiente paso
Leer el razonamiento
Compara el 4 con el 1 y los intercambia: 1, 4, 3, 2. Compara el 4 con el 3 y los intercambia: 1, 3, 4, 2. Compara el 4 con el 2 y los intercambia: 1, 3, 2, 4. El 4 final ya está fijo, pero el par central sigue desordenado.
Leer el razonamiento
El mínimo es 1C, así que el primer intercambio cambia 2A por 1C y el resultado es 1C, 2B, 2A. Los valores ya están ordenados, pero B aparece antes que A. Este único contraejemplo demuestra que esta implementación no es estable.
Leer el razonamiento
Compara los frentes 1 y 2: toma A. Compara 4 y 2: toma C. Compara 4 y 4: toma primero la tarjeta izquierda B. La fila izquierda queda vacía, así que añade D. Obtenemos 1A, 2C, 4B, 4D.
