En informática , un algoritmo de ordenación es un algoritmo que ordena los elementos de una lista . Los órdenes más utilizados son el orden numérico y el orden lexicográfico , tanto ascendente como descendente. Una ordenación eficiente es importante para optimizar la eficiencia de otros algoritmos (como los algoritmos de búsqueda y fusión ) que requieren que los datos de entrada estén en listas ordenadas. La ordenación también suele ser útil para canonizar datos y producir resultados legibles para humanos.
Formalmente, la salida de cualquier algoritmo de ordenación debe satisfacer dos condiciones:
Para lograr una eficiencia óptima, los datos de entrada deben almacenarse en una estructura de datos que permita el acceso aleatorio en lugar de una que solo permita el acceso secuencial . [ ¿Por qué? ]
Desde el comienzo de la informática, el problema de ordenamiento ha atraído una gran cantidad de investigaciones, quizás debido a la complejidad de resolverlo de manera eficiente a pesar de su enunciado simple y familiar. Entre los autores de los primeros algoritmos de ordenamiento alrededor de 1951 estaba Betty Holberton , quien trabajó en ENIAC y UNIVAC . [1] [2] El ordenamiento de burbuja se analizó ya en 1956. [3] Los algoritmos asintóticamente óptimos se conocen desde mediados del siglo XX; todavía se están inventando nuevos algoritmos, como el ampliamente utilizado Timsort que data de 2002, y el ordenamiento por biblioteca que se publicó por primera vez en 2006.
Los algoritmos de ordenamiento por comparación tienen un requisito fundamental de comparaciones Ω( n log n ) (algunas secuencias de entrada requerirán un múltiplo de n log n comparaciones, donde n es la cantidad de elementos en la matriz que se ordenará). Los algoritmos que no se basan en comparaciones, como el ordenamiento por conteo , pueden tener un mejor rendimiento.
Los algoritmos de ordenamiento son frecuentes en las clases introductorias de informática , donde la abundancia de algoritmos para el problema proporciona una introducción suave a una variedad de conceptos básicos de algoritmos, como la notación big O , algoritmos de divide y vencerás , estructuras de datos como montones y árboles binarios , algoritmos aleatorios , análisis de mejores, peores y promedios casos , compensaciones entre tiempo y espacio y límites superiores e inferiores .
La ordenación óptima (con la menor cantidad de comparaciones e intercambios) o rápida (es decir, teniendo en cuenta los detalles específicos de la máquina) de matrices pequeñas sigue siendo un problema de investigación abierto, con soluciones conocidas solo para matrices muy pequeñas (<20 elementos). De manera similar, la ordenación óptima (según diversas definiciones) en una máquina paralela es un tema de investigación abierto.
Los algoritmos de ordenación se pueden clasificar por:
Los algoritmos de ordenación estables ordenan los elementos iguales en el mismo orden en que aparecen en la entrada. Por ejemplo, en el ejemplo de ordenación de cartas de la derecha, las cartas se ordenan por su rango y se ignora su palo. Esto permite la posibilidad de múltiples versiones diferentes correctamente ordenadas de la lista original. Los algoritmos de ordenación estables eligen una de ellas, de acuerdo con la siguiente regla: si dos elementos se comparan como iguales (como las dos cartas de 5), entonces se conservará su orden relativo, es decir, si uno viene antes que el otro en la entrada, vendrá antes que el otro en la salida.
La estabilidad es importante para preservar el orden en múltiples ordenaciones del mismo conjunto de datos . Por ejemplo, supongamos que los registros de estudiantes que constan de nombre y sección de clase se ordenan de forma dinámica, primero por nombre y luego por sección de clase. Si se utiliza un algoritmo de ordenación estable en ambos casos, la operación de ordenación por sección de clase no cambiará el orden de los nombres; con una ordenación inestable, podría suceder que la ordenación por sección altere el orden de los nombres, lo que daría como resultado una lista de estudiantes no alfabética.
De manera más formal, los datos que se ordenan se pueden representar como un registro o una tupla de valores, y la parte de los datos que se utiliza para ordenar se denomina clave . En el ejemplo de las cartas, las cartas se representan como un registro (rango, palo) y la clave es el rango. Un algoritmo de ordenación es estable si, siempre que haya dos registros R y S con la misma clave, y R aparezca antes que S en la lista original, entonces R siempre aparecerá antes que S en la lista ordenada.
Cuando los elementos iguales son indistinguibles, como en el caso de los números enteros o, de manera más general, cualquier dato en el que el elemento entero es la clave, la estabilidad no es un problema. La estabilidad tampoco es un problema si todas las claves son diferentes.
Los algoritmos de ordenamiento inestables se pueden implementar especialmente para que sean estables. Una forma de hacerlo es extender artificialmente la comparación de claves, de modo que las comparaciones entre dos objetos con claves que, por lo demás, son iguales se decidan utilizando el orden de las entradas en la lista de entrada original como criterio de desempate. Sin embargo, recordar este orden puede requerir tiempo y espacio adicionales.
Una aplicación de los algoritmos de ordenamiento estable es ordenar una lista utilizando una clave primaria y una secundaria. Por ejemplo, supongamos que queremos ordenar una mano de cartas de forma que los palos estén en el orden tréboles (♣), diamantes ( ♦ ), corazones ( ♥ ), picas (♠), y dentro de cada palo, las cartas estén ordenadas por rango. Esto se puede hacer ordenando primero las cartas por rango (utilizando cualquier ordenamiento) y luego haciendo un ordenamiento estable por palo:
Dentro de cada palo, la ordenación estable conserva el ordenamiento por rango que ya se había realizado. Esta idea se puede extender a cualquier número de claves y se utiliza mediante la ordenación por radix . Se puede lograr el mismo efecto con una ordenación inestable utilizando una comparación de claves lexicográficas, que, por ejemplo, compara primero por palo y luego compara por rango si los palos son iguales.
Este análisis supone que la longitud de cada clave es constante y que todas las comparaciones, intercambios y otras operaciones pueden realizarse en tiempo constante.
Leyenda:
A continuación se muestra una tabla de ordenamientos de comparación . El análisis matemático demuestra que un ordenamiento de comparación no puede tener un mejor rendimiento que O ( n log n ) en promedio. [4]
La siguiente tabla describe algoritmos de ordenamiento de números enteros y otros algoritmos de ordenamiento que no son ordenamientos por comparación . Estos algoritmos no se limitan a Ω ( n log n ) a menos que cumplan con el modelo de máquina de acceso aleatorio de costo unitario como se describe a continuación. [12]
Samplesort se puede utilizar para paralelizar cualquiera de las ordenaciones sin comparación, distribuyendo eficientemente los datos en varios contenedores y luego pasando la ordenación a varios procesadores, sin necesidad de fusionar ya que los contenedores ya están ordenados entre sí.
Algunos algoritmos son lentos en comparación con los que se han analizado anteriormente, como el ordenamiento bogosort con un tiempo de ejecución ilimitado y el ordenamiento stooge que tiene un tiempo de ejecución O ( n 2,7 ). Estos ordenamientos se describen normalmente con fines educativos para demostrar cómo se calcula el tiempo de ejecución de los algoritmos. La siguiente tabla describe algunos algoritmos de ordenamiento que no son prácticos para su uso en la vida real en contextos de software tradicionales debido a un rendimiento extremadamente bajo o a requisitos de hardware especializados.
Los científicos informáticos teóricos han detallado otros algoritmos de clasificación que proporcionan una complejidad temporal mejor que O ( n log n ), asumiendo restricciones adicionales, entre ellas:
Si bien hay una gran cantidad de algoritmos de ordenamiento, en las implementaciones prácticas predominan unos pocos algoritmos. El ordenamiento por inserción se usa ampliamente para conjuntos de datos pequeños, mientras que para conjuntos de datos grandes se usa un ordenamiento asintóticamente eficiente, principalmente heapsort, merge sort o quicksort. Las implementaciones eficientes generalmente usan un algoritmo híbrido , que combina un algoritmo asintóticamente eficiente para el ordenamiento general con un ordenamiento por inserción para listas pequeñas en la parte inferior de una recursión. Las implementaciones altamente optimizadas usan variantes más sofisticadas, como Timsort (merge sort, insertion sort y lógica adicional), usado en Android , Java y Python , e introsort (quicksort y heapsort), usado (en formas variantes) en algunas implementaciones de ordenamiento de C++ y en .NET .
Para datos más restringidos, como números en un intervalo fijo, se utilizan ampliamente ordenaciones de distribución como la ordenación por conteo o la ordenación por radix. La ordenación de burbuja y sus variantes rara vez se utilizan en la práctica, pero se encuentran comúnmente en la enseñanza y en los debates teóricos.
Al ordenar objetos físicamente (como ordenar alfabéticamente documentos, exámenes o libros), las personas generalmente usan intuitivamente ordenaciones por inserción para conjuntos pequeños. Para conjuntos más grandes, las personas a menudo clasifican primero, como por letra inicial, y la clasificación múltiple permite una clasificación práctica de conjuntos muy grandes. A menudo, el espacio es relativamente barato, como al esparcir los objetos en el piso o en un área grande, pero las operaciones son costosas, en particular mover un objeto a una gran distancia: la localidad de referencia es importante. Las ordenaciones por fusión también son prácticas para objetos físicos, en particular porque se pueden usar dos manos, una para cada lista a fusionar, mientras que otros algoritmos, como heapsort o quicksort, no son adecuados para el uso humano. Otros algoritmos, como library sort , una variante de la ordenación por inserción que deja espacios, también son prácticos para el uso físico.
Dos de las ordenaciones más simples son la ordenación por inserción y la ordenación por selección, ambas eficientes con datos pequeños, debido a la baja sobrecarga, pero no eficientes con datos grandes. La ordenación por inserción es generalmente más rápida que la ordenación por selección en la práctica, debido a menos comparaciones y buen desempeño con datos casi ordenados, y por lo tanto es preferida en la práctica, pero la ordenación por selección usa menos escrituras, y por lo tanto se usa cuando el desempeño de escritura es un factor limitante.
La ordenación por inserción es un algoritmo de ordenación simple que es relativamente eficiente para listas pequeñas y listas mayoritariamente ordenadas, y se usa a menudo como parte de algoritmos más sofisticados. Funciona tomando elementos de la lista uno por uno e insertándolos en su posición correcta en una nueva lista ordenada de manera similar a cómo uno pone dinero en su billetera. [22] En matrices, la nueva lista y los elementos restantes pueden compartir el espacio de la matriz, pero la inserción es costosa, ya que requiere desplazar todos los elementos siguientes en uno. Shellsort es una variante de la ordenación por inserción que es más eficiente para listas más grandes.
La ordenación por selección es una ordenación por comparación en el lugar . Tiene una complejidad de O ( n 2 ), lo que la hace ineficiente en listas grandes y, en general, tiene un peor rendimiento que la ordenación por inserción similar . La ordenación por selección se destaca por su simplicidad y también tiene ventajas de rendimiento sobre algoritmos más complicados en ciertas situaciones.
El algoritmo encuentra el valor mínimo, lo intercambia con el valor en la primera posición y repite estos pasos para el resto de la lista. [23] No realiza más de n intercambios y, por lo tanto, es útil cuando el intercambio es muy costoso.
Los algoritmos de ordenamiento general prácticos casi siempre se basan en un algoritmo con una complejidad temporal media (y, en general, una complejidad en el peor de los casos) O( n log n ), de los cuales los más comunes son el heapsort, el merge sort y el quicksort. Cada uno de ellos tiene ventajas y desventajas, siendo la más importante que la implementación simple del merge sort utiliza O( n ) espacio adicional, y la implementación simple del quicksort tiene una complejidad en el peor de los casos O( n 2 ). Estos problemas se pueden resolver o mejorar a costa de un algoritmo más complejo.
Si bien estos algoritmos son asintóticamente eficientes en datos aleatorios, para lograr una eficiencia práctica en datos del mundo real se utilizan varias modificaciones. En primer lugar, la sobrecarga de estos algoritmos se vuelve significativa en datos más pequeños, por lo que a menudo se utiliza un algoritmo híbrido, que comúnmente cambia a la ordenación por inserción una vez que los datos son lo suficientemente pequeños. En segundo lugar, los algoritmos a menudo funcionan mal en datos ya ordenados o casi ordenados; estos son comunes en datos del mundo real y se pueden ordenar en tiempo O( n ) mediante algoritmos apropiados. Finalmente, también pueden ser inestables , y la estabilidad es a menudo una propiedad deseable en una ordenación. Por lo tanto, a menudo se emplean algoritmos más sofisticados, como Timsort (basado en la ordenación por fusión) o introsort (basado en quicksort, que vuelve a heapsort).
El ordenamiento por fusión aprovecha la facilidad de fusionar listas ya ordenadas en una nueva lista ordenada. Comienza comparando cada dos elementos (es decir, 1 con 2, luego 3 con 4...) e intercambiándolos si el primero debe venir después del segundo. Luego fusiona cada una de las listas resultantes de dos en listas de cuatro, luego fusiona esas listas de cuatro, y así sucesivamente; hasta que al final se fusionan dos listas en la lista ordenada final. [24] De los algoritmos descritos aquí, este es el primero que escala bien a listas muy grandes, porque su tiempo de ejecución en el peor de los casos es O( n log n ). También se aplica fácilmente a listas, no solo a matrices, ya que solo requiere acceso secuencial, no acceso aleatorio. Sin embargo, tiene una complejidad espacial adicional de O( n ) e involucra una gran cantidad de copias en implementaciones simples.
La ordenación por combinación ha experimentado un aumento relativamente reciente en popularidad para implementaciones prácticas, debido a su uso en el sofisticado algoritmo Timsort , que se utiliza para la rutina de ordenación estándar en los lenguajes de programación Python [25] y Java (a partir de JDK7 [26] ). La ordenación por combinación en sí es la rutina estándar en Perl [27] , entre otros, y se ha utilizado en Java al menos desde 2000 en JDK1.3 . [28]
Heapsort es una versión mucho más eficiente de la ordenación por selección . También funciona determinando el elemento más grande (o más pequeño) de la lista, colocándolo al final (o al principio) de la lista y luego continuando con el resto de la lista, pero logra esta tarea de manera eficiente mediante el uso de una estructura de datos llamada heap , un tipo especial de árbol binario . [29] Una vez que la lista de datos se ha convertido en un heap, se garantiza que el nodo raíz sea el elemento más grande (o más pequeño). Cuando se elimina y se coloca al final de la lista, el heap se reorganiza de modo que el elemento más grande restante se mueve a la raíz. Usando el heap, encontrar el siguiente elemento más grande toma un tiempo O(log n ), en lugar de O( n ) para un escaneo lineal como en la ordenación por selección simple. Esto permite que Heapsort se ejecute en un tiempo O( n log n ), y esta es también la complejidad del peor caso.
Quicksort es un algoritmo de divide y vencerás que se basa en una operación de partición : para particionar una matriz, se selecciona un elemento llamado pivote . [30] [31] Todos los elementos más pequeños que el pivote se mueven antes de él y todos los elementos más grandes se mueven después de él. Esto se puede hacer de manera eficiente en tiempo lineal y en el lugar . Las sublistas menor y mayor se ordenan recursivamente. Esto produce una complejidad de tiempo promedio de O( n log n ), con baja sobrecarga, y por lo tanto este es un algoritmo popular. Las implementaciones eficientes de quicksort (con partición en el lugar) son típicamente ordenaciones inestables y algo complejas, pero se encuentran entre los algoritmos de ordenación más rápidos en la práctica. Junto con su modesto uso del espacio O(log n ), quicksort es uno de los algoritmos de ordenación más populares y está disponible en muchas bibliotecas de programación estándar.
La advertencia importante sobre quicksort es que su rendimiento en el peor de los casos es O( n 2 ); si bien esto es poco común, en implementaciones ingenuas (eligiendo el primer o último elemento como pivote) esto ocurre para datos ordenados, que es un caso común. El problema más complejo en quicksort es, por lo tanto, elegir un buen elemento pivote, ya que las elecciones consistentemente malas de pivotes pueden dar como resultado un rendimiento O( n 2 ) drásticamente más lento, pero la buena elección de pivotes produce un rendimiento O( n log n ), que es asintóticamente óptimo. Por ejemplo, si en cada paso se elige la mediana como pivote, entonces el algoritmo funciona en O( n log n ). Encontrar la mediana, como por el algoritmo de selección de la mediana de las medianas , es sin embargo una operación O( n ) en listas no ordenadas y, por lo tanto, exige una sobrecarga significativa con la ordenación. En la práctica, la elección de un pivote aleatorio casi con certeza produce un rendimiento O( n log n ).
Si es importante garantizar un rendimiento de O( n log n ), existe una modificación sencilla para lograrlo. La idea, debida a Musser, es establecer un límite en la profundidad máxima de recursión. [32] Si se excede ese límite, entonces se continúa ordenando utilizando el algoritmo heapsort. Musser propuso que el límite debería ser , que es aproximadamente el doble de la profundidad máxima de recursión que uno esperaría en promedio con una matriz ordenada aleatoriamente.
Shellsort fue inventado por Donald Shell en 1959. [33] Mejora la ordenación por inserción moviendo elementos fuera de orden más de una posición a la vez. El concepto detrás de Shellsort es que la ordenación por inserción se realiza en tiempo , donde k es la distancia más grande entre dos elementos fuera de lugar. Esto significa que, generalmente, se realizan en O ( n 2 ), pero para datos que están mayormente ordenados, con solo unos pocos elementos fuera de lugar, se realizan más rápido. Entonces, al ordenar primero los elementos que están lejos y reducir progresivamente la brecha entre los elementos a ordenar, la ordenación final se calcula mucho más rápido. Una implementación se puede describir como organizar la secuencia de datos en una matriz bidimensional y luego ordenar las columnas de la matriz usando la ordenación por inserción.
La complejidad temporal del peor caso de Shellsort es un problema abierto y depende de la secuencia de espacios utilizada, con complejidades conocidas que van desde O ( n 2 ) a O ( n 4/3 ) y Θ( n log 2 n ). Esto, combinado con el hecho de que Shellsort está en el lugar , solo necesita una cantidad relativamente pequeña de código y no requiere el uso de la pila de llamadas , lo hace útil en situaciones donde la memoria es limitada, como en sistemas integrados y núcleos de sistemas operativos .
El método de ordenación de burbuja y sus variantes, como el método de ordenación en peine y el método de ordenación en cóctel , son algoritmos de ordenación sencillos y muy ineficientes. Se los suele ver en textos introductorios debido a su facilidad de análisis, pero rara vez se los utiliza en la práctica.
El método de ordenación por burbuja es un algoritmo de ordenación simple. El algoritmo comienza al principio del conjunto de datos. Compara los dos primeros elementos y, si el primero es mayor que el segundo, los intercambia. Continúa haciendo esto para cada par de elementos adyacentes hasta el final del conjunto de datos. Luego comienza nuevamente con los dos primeros elementos y repite hasta que no se hayan producido intercambios en la última pasada. [34] El tiempo promedio y el rendimiento en el peor de los casos de este algoritmo es O( n 2 ), por lo que rara vez se usa para ordenar conjuntos de datos grandes y desordenados. El método de ordenación por burbuja se puede usar para ordenar una pequeña cantidad de elementos (donde su ineficiencia asintótica no es una penalización alta). El método de ordenación por burbuja también se puede usar de manera eficiente en una lista de cualquier longitud que esté casi ordenada (es decir, los elementos no están significativamente fuera de lugar). Por ejemplo, si cualquier número de elementos está fuera de lugar por solo una posición (por ejemplo, 0123546789 y 1032547698), el intercambio de clasificación de burbuja los ordenará en la primera pasada, la segunda pasada encontrará todos los elementos en orden, por lo que la clasificación tomará solo 2 n tiempo.
[35]
Comb sort es un algoritmo de ordenación relativamente simple basado en el ordenamiento de burbuja y diseñado originalmente por Włodzimierz Dobosiewicz en 1980. [36] Más tarde fue redescubierto y popularizado por Stephen Lacey y Richard Box con un artículo de Byte Magazine publicado en abril de 1991. La idea básica es eliminar las tortugas , o valores pequeños cerca del final de la lista, ya que en un ordenamiento de burbuja estos ralentizan enormemente el ordenamiento. ( Los conejos , valores grandes alrededor del comienzo de la lista, no plantean un problema en el ordenamiento de burbuja). Esto se logra intercambiando inicialmente los elementos que están a cierta distancia entre sí en la matriz, en lugar de solo intercambiar elementos si son adyacentes entre sí, y luego reduciendo la distancia elegida hasta que esté operando como un ordenamiento de burbuja normal. Por lo tanto, si Shellsort puede considerarse como una versión generalizada del ordenamiento por inserción que intercambia elementos espaciados a cierta distancia entre sí, el ordenamiento en peine puede considerarse como la misma generalización aplicada al ordenamiento de burbuja.
El ordenamiento por intercambio a veces se confunde con el ordenamiento de burbuja, aunque de hecho los algoritmos son distintos. [37] [38] El ordenamiento por intercambio funciona comparando el primer elemento con todos los elementos que están por encima de él, intercambiando donde sea necesario, garantizando así que el primer elemento sea correcto para el ordenamiento final; luego procede a hacer lo mismo para el segundo elemento, y así sucesivamente. Carece de la ventaja que tiene el ordenamiento de burbuja de detectar en una pasada si la lista ya está ordenada, pero puede ser más rápido que el ordenamiento de burbuja por un factor constante (una pasada menos sobre los datos a ordenar; la mitad de comparaciones totales) en las peores situaciones. Como cualquier ordenamiento O( n 2 ) simple, puede ser razonablemente rápido sobre conjuntos de datos muy pequeños, aunque en general el ordenamiento por inserción será más rápido.
La ordenación por distribución se refiere a cualquier algoritmo de ordenación en el que los datos se distribuyen desde su entrada a múltiples estructuras intermedias que luego se reúnen y se colocan en la salida. Por ejemplo, tanto la ordenación por cubo como la ordenación por flash son algoritmos de ordenación basados en la distribución. Los algoritmos de ordenación por distribución se pueden utilizar en un solo procesador o pueden ser un algoritmo distribuido , en el que los subconjuntos individuales se ordenan por separado en diferentes procesadores y luego se combinan. Esto permite la ordenación externa de datos demasiado grandes para caber en la memoria de una sola computadora.
El ordenamiento por conteo es aplicable cuando se sabe que cada entrada pertenece a un conjunto particular, S , de posibilidades. El algoritmo se ejecuta en tiempo O(| S | + n ) y memoria O(| S |) donde n es la longitud de la entrada. Funciona creando una matriz de enteros de tamaño | S | y usando el i -ésimo bin para contar las ocurrencias del i- ésimo miembro de S en la entrada. Luego, cada entrada se cuenta incrementando el valor de su bin correspondiente. Después, se hace un bucle en la matriz de conteo para ordenar todas las entradas. Este algoritmo de ordenamiento a menudo no se puede usar porque S debe ser razonablemente pequeño para que el algoritmo sea eficiente, pero es extremadamente rápido y demuestra un gran comportamiento asintótico a medida que n aumenta. También se puede modificar para proporcionar un comportamiento estable.
El ordenamiento por cubos es un algoritmo de ordenamiento del tipo divide y vencerás que generaliza el ordenamiento por conteo al dividir una matriz en una cantidad finita de cubos. Luego, cada cubo se ordena individualmente, ya sea mediante un algoritmo de ordenamiento diferente o aplicando recursivamente el algoritmo de ordenamiento por cubos.
Una ordenación por categorías funciona mejor cuando los elementos del conjunto de datos se distribuyen uniformemente entre todos los categorías.
El ordenamiento por radix es un algoritmo que ordena números mediante el procesamiento de dígitos individuales. Se ordenan n números que constan de k dígitos cada uno en tiempo O( n · k ). El ordenamiento por radix puede procesar dígitos de cada número comenzando desde el dígito menos significativo (LSD) o comenzando desde el dígito más significativo (MSD). El algoritmo LSD primero ordena la lista por el dígito menos significativo mientras preserva su orden relativo utilizando un ordenamiento estable. Luego los ordena por el siguiente dígito, y así sucesivamente desde el menos significativo hasta el más significativo, terminando con una lista ordenada. Mientras que el ordenamiento por radix LSD requiere el uso de un ordenamiento estable, el algoritmo de ordenamiento por radix MSD no lo hace (a menos que se desee un ordenamiento estable). El ordenamiento por radix MSD en el lugar no es estable. Es común que el algoritmo de ordenamiento por conteo sea utilizado internamente por el ordenamiento por radix. Un enfoque de ordenamiento híbrido , como el uso del ordenamiento por inserción para contenedores pequeños, mejora significativamente el rendimiento del ordenamiento por radix.
Cuando el tamaño de la matriz que se va a ordenar se acerca o supera la memoria primaria disponible, de modo que se debe utilizar espacio de disco o de intercambio (mucho más lento), el patrón de uso de memoria de un algoritmo de ordenamiento se vuelve importante, y un algoritmo que podría haber sido bastante eficiente cuando la matriz cabía fácilmente en la RAM puede volverse poco práctico. En este escenario, el número total de comparaciones se vuelve (relativamente) menos importante, y el número de veces que se deben copiar o intercambiar secciones de memoria hacia y desde el disco puede dominar las características de rendimiento de un algoritmo. Por lo tanto, el número de pasadas y la localización de las comparaciones pueden ser más importantes que el número bruto de comparaciones, ya que las comparaciones de elementos cercanos entre sí ocurren a la velocidad del bus del sistema (o, con el almacenamiento en caché, incluso a la velocidad de la CPU ), que, comparada con la velocidad del disco, es prácticamente instantánea.
Por ejemplo, el popular algoritmo recursivo de ordenación rápida ofrece un rendimiento bastante razonable con una memoria RAM adecuada, pero debido a la forma recursiva en que copia partes de la matriz, resulta mucho menos práctico cuando la matriz no cabe en la memoria RAM, ya que puede provocar una serie de operaciones de copia o traslado lentos hacia y desde el disco. En ese escenario, puede ser preferible otro algoritmo, incluso si requiere más comparaciones totales.
Una forma de solucionar este problema, que funciona bien cuando se ordenan registros complejos (como en una base de datos relacional ) por un campo clave relativamente pequeño, es crear un índice en la matriz y luego ordenar el índice, en lugar de la matriz completa. (Una versión ordenada de la matriz completa se puede producir entonces con una sola pasada, leyendo desde el índice, pero a menudo incluso eso es innecesario, ya que tener el índice ordenado es suficiente). Debido a que el índice es mucho más pequeño que la matriz completa, puede caber fácilmente en la memoria donde la matriz completa no lo haría, eliminando efectivamente el problema del intercambio de discos. Este procedimiento a veces se llama "ordenación por etiquetas". [39]
Otra técnica para superar el problema del tamaño de la memoria es usar ordenamiento externo , por ejemplo, una de las formas es combinar dos algoritmos de una manera que aproveche la fuerza de cada uno para mejorar el rendimiento general. Por ejemplo, la matriz se puede subdividir en fragmentos de un tamaño que quepa en la RAM, el contenido de cada fragmento se puede ordenar usando un algoritmo eficiente (como quicksort ) y los resultados se pueden fusionar usando una fusión de k -way similar a la que se usa en merge sort . Esto es más rápido que realizar merge sort o quicksort sobre toda la lista. [40] [41]
Las técnicas también se pueden combinar. Para ordenar conjuntos de datos muy grandes que exceden ampliamente la memoria del sistema, incluso el índice puede necesitar ser ordenado usando un algoritmo o una combinación de algoritmos diseñados para funcionar razonablemente con la memoria virtual , es decir, para reducir la cantidad de intercambio requerido.
Los problemas relacionados incluyen la ordenación aproximada (ordenar una secuencia dentro de una cierta cantidad del orden correcto), la ordenación parcial (ordenar solo los k elementos más pequeños de una lista, o encontrar los k elementos más pequeños, pero desordenados) y la selección (calcular el k ésimo elemento más pequeño). Estos pueden resolverse de manera ineficiente mediante una ordenación total, pero existen algoritmos más eficientes, a menudo derivados de la generalización de un algoritmo de ordenación. El ejemplo más notable es quickselect , que está relacionado con quicksort . Por el contrario, algunos algoritmos de ordenación pueden derivarse de la aplicación repetida de un algoritmo de selección; quicksort y quickselect pueden verse como el mismo movimiento pivotante, que difiere solo en si uno recurre en ambos lados (quicksort, divide-y-conquistar ) o en un lado (quickselect, decrease-and-conquistar ).
Un tipo de algoritmo opuesto a un algoritmo de ordenación es un algoritmo de barajado . Estos son fundamentalmente diferentes porque requieren una fuente de números aleatorios. El barajado también se puede implementar mediante un algoritmo de ordenación, es decir, mediante una ordenación aleatoria: asignando un número aleatorio a cada elemento de la lista y luego ordenando en función de los números aleatorios. Sin embargo, esto generalmente no se hace en la práctica, y existe un algoritmo conocido, simple y eficiente para barajar: el barajado de Fisher-Yates .
Los algoritmos de ordenación son ineficaces para encontrar un orden en muchas situaciones. Por lo general, cuando los elementos no tienen una función de comparación confiable (preferencias de colaboración colectiva como los sistemas de votación ), las comparaciones son muy costosas ( deportes ) o cuando sería imposible comparar por pares todos los elementos para todos los criterios ( motores de búsqueda ). En estos casos, el problema suele denominarse clasificación y el objetivo es encontrar el "mejor" resultado para algunos criterios según las probabilidades inferidas a partir de comparaciones o clasificaciones. Un ejemplo común es el ajedrez, donde los jugadores se clasifican con el sistema de clasificación Elo y las clasificaciones se determinan mediante un sistema de torneo en lugar de un algoritmo de clasificación.
