Algoritmo de clasificación - Sorting algorithm

En informática , un algoritmo de clasificación es un algoritmo que pone los elementos de una lista en un orden . Los órdenes más utilizados son el orden numérico y el orden lexicográfico , ascendente o descendente. La clasificación eficiente es importante para optimizar la eficiencia de otros algoritmos (como los de búsqueda y combinación ) que requieren que los datos de entrada estén en listas ordenadas. La clasificación también suele ser útil para canonicalizar datos y producir resultados legibles por humanos.

Formalmente, la salida de cualquier algoritmo de clasificación debe satisfacer dos condiciones:

  1. La salida está en orden monótono (cada elemento no es más pequeño / más grande que el elemento anterior, según el orden requerido).
  2. La salida es una permutación (un reordenamiento, pero conservando todos los elementos originales) de la entrada.

Para 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 .

Historia y conceptos

Desde el comienzo de la informática, el problema de clasificación ha atraído una gran cantidad de investigación, quizás debido a la complejidad de resolverlo de manera eficiente a pesar de su simple y familiar declaración. Entre los autores de los primeros algoritmos de clasificación alrededor de 1951 se encontraba Betty Holberton , quien trabajó en ENIAC y UNIVAC . La clasificación de burbujas se analizó ya en 1956. Los algoritmos óptimos asintóticamente se conocen desde mediados del siglo XX; todavía se están inventando nuevos algoritmos, el Timsort ampliamente utilizado data de 2002 y la clasificación de biblioteca se publicó por primera vez en 2006.

Los algoritmos de ordenación 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 el número de elementos de la matriz que se ordenarán). Los algoritmos que no se basan en comparaciones, como el ordenamiento por conteo , pueden tener un mejor rendimiento.

Los algoritmos de clasificación prevalecen en las clases de introducción a la informática , donde la abundancia de algoritmos para el problema proporciona una introducción suave a una variedad de conceptos de algoritmos centrales, como la notación O grande , algoritmos de división y conquista , estructuras de datos como montones y árboles binarios , algoritmos aleatorios , mejor, peor y promedio caso de análisis, las compensaciones de tiempo-espacio y límites superior e inferior .

La clasificación de arreglos pequeños de manera óptima (en la menor cantidad de comparaciones e intercambios) o rápida (es decir, teniendo en cuenta los detalles específicos de la máquina) sigue siendo un problema de investigación abierto, con soluciones que solo se conocen para arreglos muy pequeños (<20 elementos). De manera similar, la clasificación óptima (según varias definiciones) en una máquina paralela es un tema de investigación abierto.

Clasificación

Los algoritmos de clasificación se pueden clasificar por:

  • Complejidad computacional
    • Comportamiento de caso mejor, peor y promedio en términos del tamaño de la lista. Para los algoritmos de clasificación en serie típicos, el buen comportamiento es O ( n  log  n ), con el ordenamiento paralelo en O (log 2  n ) y el mal comportamiento es O ( n 2 ). El comportamiento ideal para una ordenación en serie es O ( n ), pero esto no es posible en el caso promedio. La clasificación paralela óptima es O (log  n ).
    • Cambios por algoritmos "in situ".
  • Uso de memoria (y uso de otros recursos informáticos). En particular, algunos algoritmos de clasificación están " en el lugar ". Estrictamente, una clasificación en el lugar solo necesita memoria O (1) más allá de los elementos que se clasifican; a veces, la memoria adicional O (log  n ) se considera "en el lugar".
  • Recursión: algunos algoritmos son recursivos o no recursivos, mientras que otros pueden ser ambos (p. Ej., Combinación de ordenación).
  • Estabilidad: los algoritmos de clasificación estables mantienen el orden relativo de los registros con claves iguales (es decir, valores).
  • Si son o no un tipo de comparación . Una clasificación de comparación examina los datos solo comparando dos elementos con un operador de comparación.
  • Método general: inserción, intercambio, selección, fusión, etc. Los tipos de intercambio incluyen clasificación de burbujas y clasificación rápida. Los ordenamientos de selección incluyen ordenamiento cíclico y ordenamiento dinámico.
  • Si el algoritmo es en serie o en paralelo. El resto de esta discusión se concentra casi exclusivamente en algoritmos seriales y asume el funcionamiento en serie.
  • Adaptabilidad: si la clasificación previa de la entrada afecta el tiempo de ejecución. Se sabe que los algoritmos que tienen esto en cuenta son adaptativos .
  • En línea: un algoritmo como Insertion Sort que está en línea puede ordenar un flujo constante de entrada.

Estabilidad

Un ejemplo de tipo estable en naipes. Cuando las cartas se clasifican por rango con una clasificación estable, los dos 5 deben permanecer en el mismo orden en la salida clasificada en la que estaban originalmente. Cuando se clasifican con una clasificación no estable, los 5 pueden terminar en el lado opuesto. orden en la salida ordenada.

Los algoritmos de clasificación estables clasifican elementos iguales en el mismo orden en que aparecen en la entrada. Por ejemplo, en el ejemplo de clasificación de cartas de la derecha, las cartas se ordenan por rango y su palo se ignora. Esto permite la posibilidad de múltiples versiones diferentes ordenadas correctamente de la lista original. Los algoritmos de ordenación estable eligen uno de estos, de acuerdo con la siguiente regla: si dos elementos se comparan como iguales (como las dos 5 cartas), 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 varios tipos en el mismo conjunto de datos . Por ejemplo, digamos que los registros de estudiantes que constan de nombre y sección de clase se ordenan dinámicamente, primero por nombre y luego por sección de clase. Si se utiliza un algoritmo de clasificación estable en ambos casos, la operación de clasificación por sección de clase no cambiará el orden de los nombres; con una clasificación inestable, podría ser que la clasificación por sección mezcle el orden de los nombres, lo que da como resultado una lista no alfabética de estudiantes.

Más formalmente, los datos que se ordenan se pueden representar como un registro o tupla de valores, y la parte de los datos que se usa para ordenar se llama clave . En el ejemplo de la tarjeta, las tarjetas se representan como un registro (rango, palo) y la clave es el rango. Un algoritmo de clasificación es estable si siempre que hay dos registros R y S con la misma clave, y R aparece antes de S en la lista original, entonces R siempre aparecerá antes de S en la lista ordenada.

Cuando los elementos iguales son indistinguibles, como los números enteros, o más en general, cualquier dato en el que el elemento completo es la clave, la estabilidad no es un problema. La estabilidad tampoco es un problema si todas las claves son diferentes.

Los algoritmos de clasificación inestables se pueden implementar especialmente para que sean estables. Una forma de hacer esto es extender artificialmente la comparación de claves, de modo que las comparaciones entre dos objetos con claves iguales se decidan usando el orden de las entradas en la lista de entrada original como un desempate. Sin embargo, recordar este orden puede requerir tiempo y espacio adicionales.

Una aplicación para los algoritmos de clasificación estables es clasificar una lista usando una clave primaria y secundaria. Por ejemplo, supongamos que deseamos ordenar una mano de cartas de modo que los palos estén en el orden tréboles (♣), diamantes ( ), corazones ( ), espadas (♠), y dentro de cada palo, las cartas están ordenadas por rango. Esto se puede hacer primero clasificando las cartas por rango (usando cualquier tipo), y luego haciendo una clasificación estable por palo:

Clasificación de naipes usando estable sort.svg

Dentro de cada palo, el tipo estable conserva el orden por rango que ya estaba hecho. Esta idea se puede extender a cualquier número de claves y se utiliza mediante ordenación por radix . El mismo efecto se puede lograr con una clasificación inestable mediante el uso de una comparación de clave lexicográfica, que, por ejemplo, compara primero por palo y luego compara por rango si los palos son iguales.

Comparación de algoritmos

En estas tablas, n es el número de registros que se ordenarán. Las columnas "Mejor", "Promedio" y "Peor" dan la complejidad temporal en cada caso, bajo el supuesto de que la longitud de cada clave es constante y, por lo tanto, todas las comparaciones, intercambios y otras operaciones pueden realizarse en un tiempo constante. "Memoria" denota la cantidad de almacenamiento adicional necesario además del utilizado por la lista misma, bajo el mismo supuesto. Los tiempos de ejecución y los requisitos de memoria enumerados están dentro de la notación O grande , por lo que la base de los logaritmos no importa. La notación log 2 n significa (log n ) 2 .

Clases de comparación

A continuación se muestra una tabla de tipos de comparación . Una clasificación de comparación no puede funcionar mejor que O ( n log n ) en promedio.

Clases de comparación
Nombre Mejor Promedio Peor Memoria Estable Método Otras notas
Ordenación rápida No Fraccionamiento La ordenación rápida generalmente se realiza en el lugar con espacio de pila O (log n ) .
Combinar ordenación norte Fusión Altamente paralelizable (hasta O (log n ) utilizando el algoritmo de los tres húngaros).
Ordenación por combinación in situ - - 1 Fusión Se puede implementar como una ordenación estable basada en una fusión in situ estable.
Introsort No Partición y selección Utilizado en varias implementaciones de STL .
Heapsort 1 No Selección
Tipo de inserción norte 1 Inserción O ( n + d ) , en el peor de los casos sobre secuencias que tienen d inversiones .
Orden de bloque norte 1 Inserción y fusión Combine un algoritmo de fusión in situ basado en bloques con una ordenación de fusión ascendente .
Timsort norte norte Inserción y fusión Hace n-1 comparaciones cuando los datos ya están ordenados o ordenados al revés.
Orden de selección 1 No Selección Estable con espacio adicional, cuando se utilizan listas vinculadas o cuando se realiza como una variante de la ordenación por inserción en lugar de intercambiar los dos elementos.
Cubesort norte norte Inserción Hace n-1 comparaciones cuando los datos ya están ordenados o ordenados al revés.
Shellsort 1 No Inserción Tamaño de código pequeño.
Ordenamiento de burbuja norte 1 Intercambiar Diminuto tamaño de código.
Tipo de intercambio 1 Intercambiar Diminuto tamaño de código.
Tipo de árbol (equilibrado) norte Inserción Cuando se utiliza un árbol de búsqueda binario autoequilibrado .
Orden de ciclo 1 No Selección En el lugar con un número teóricamente óptimo de escrituras.
Orden de biblioteca norte No Inserción Similar a una ordenación de inserción con huecos. Requiere permutar aleatoriamente la entrada para garantizar límites de tiempo de alta probabilidad, lo que la hace no estable.
Clasificación de paciencia norte norte No Inserción y selección Encuentra todas las subsecuencias crecientes más largas en O ( n log n ) .
Smoothsort norte 1 No Selección Una variante adaptativa de heapsort basada en la secuencia de Leonardo en lugar de un montón binario tradicional .
Tipo de hebra norte norte Selección
Tipo de torneo norte No Selección Variación de Heapsort.
Tipo de coctelera norte 1 Intercambiar Una variante de Bubblesort que se ocupa bien de valores pequeños al final de la lista
Tipo de peine 1 No Intercambiar Más rápido que la clasificación de burbujas en promedio.
Tipo de gnomo norte 1 Intercambiar Diminuto tamaño de código.
Tipo impar-par norte 1 Intercambiar Se puede ejecutar fácilmente en procesadores paralelos.

Clases sin comparación

La siguiente tabla describe los algoritmos de clasificación de enteros y otros algoritmos de clasificación que no son tipos de comparación . Como tales, no se limitan a Ω ( n log n ) . Complejidades debajo asumen n elementos a ser ordenados, con teclas de tamaño k , tamaño dígitos d , y r el rango de números a ser clasificada. Muchos de ellos se basan en la suposición de que el tamaño de la clave es lo suficientemente grande como para que todas las entradas tengan valores de clave únicos y, por lo tanto, n ≪ 2 k , donde ≪ significa "mucho menos que". En el modelo de máquina de acceso aleatorio de costo unitario , los algoritmos con tiempo de ejecución de , como el ordenamiento por radix, aún toman un tiempo proporcional a Θ ( n log n ) , porque n está limitado a no ser más que , y un número mayor de elementos ordenar requeriría una k mayor para almacenarlos en la memoria.

Clases sin comparación
Nombre Mejor Promedio Peor Memoria Estable n ≪ 2 k Notas
Tipo de casillero - No se pueden ordenar los números no enteros.
Clasificación de cubos (llaves uniformes) - No Asume una distribución uniforme de elementos del dominio en la matriz.

Tampoco puede ordenar números no enteros

Clasificación de depósito (claves de números enteros) - Si r es , entonces la complejidad de tiempo promedio es .
Contando ordenar - Si r es , entonces la complejidad de tiempo promedio es .
Clasificación de LSD Radix No niveles de recursividad, 2 d para la matriz de recuento.

A diferencia de la mayoría de los tipos de distribución, esto puede ordenar números de coma flotante , números negativos y más.

Orden de Radix MSD - No La versión estable usa una matriz externa de tamaño n para contener todos los contenedores.

Al igual que la variante LSD, puede ordenar números no enteros.

MSD Radix Sort (en el lugar) - No No d = 1 para niveles de recursividad in situ , sin matriz de recuento.
Spreadsort norte No No Los asintóticos se basan en el supuesto de que n ≪ 2 k , pero el algoritmo no lo requiere.
Burstsort - No No Tiene mejor factor constante que la ordenación por radix para ordenar cadenas. Aunque depende un poco de las características específicas de las cadenas que se encuentran comúnmente.
Flashsort norte norte No No Requiere una distribución uniforme de elementos del dominio en la matriz para ejecutarse en tiempo lineal. Si la distribución está muy sesgada, entonces puede volverse cuadrática si la ordenación subyacente es cuadrática (generalmente es una ordenación por inserción). La versión local no es estable.
Tipo de cartero - - No Una variación del tipo de cubeta, que funciona de manera muy similar a MSD Radix Sort. Específico para las necesidades del servicio postal.

Samplesort se puede utilizar para paralelizar cualquiera de los tipos de no comparación, distribuyendo de manera eficiente los datos en varios depósitos y luego pasando la clasificación a varios procesadores, sin necesidad de fusionarlos, ya que los depósitos ya están ordenados entre sí.

Otros

Algunos algoritmos son lentos en comparación con los discutidos anteriormente, como el bogosort con tiempo de ejecución ilimitado y el tipo de títere que tiene un tiempo de ejecución O ( n 2.7 ). Estos tipos se describen generalmente con fines educativos para demostrar cómo se estima el tiempo de ejecución de los algoritmos. La siguiente tabla describe algunos algoritmos de clasificación que no son prácticos para el uso en la vida real en contextos de software tradicionales debido a un rendimiento extremadamente bajo o requisitos de hardware especializados.

Nombre Mejor Promedio Peor Memoria Estable Comparación Otras notas
Tipo de cuentas norte S S N / A No Funciona solo con números enteros positivos. Requiere hardware especializado para que funcione en tiempo garantizado . Existe la posibilidad de implementación de software, pero el tiempo de ejecución será , donde S es la suma de todos los números enteros a ordenar, en el caso de números enteros pequeños, se puede considerar lineal.
Tipo de panqueques simple - norte norte No El recuento es el número de volteretas.
Tipo de espagueti (encuesta) norte norte norte Votación Este es un algoritmo analógico de tiempo lineal para clasificar una secuencia de elementos, que requiere un espacio de pila O ( n ), y la clasificación es estable. Esto requiere n procesadores en paralelo. Ver análisis de # de clasificación de espaguetis .
Red de clasificación Varía Varía Varía Varía Varía (las redes de clasificación estables requieren más comparaciones) El orden de las comparaciones se establece de antemano en función de un tamaño de red fijo.
Clasificador bitónico paralelo paralelo no paralelo 1 No Una variación eficaz de las redes de clasificación.
Bogosort norte ilimitado (cierto), (esperado) 1 No Mezcla aleatoria. Se usa solo con fines de ejemplo, ya que incluso el tiempo de ejecución esperado en el mejor de los casos es terrible.
Tipo chiflado norte No Más lento que la mayoría de los algoritmos de clasificación (incluso los ingenuos) con una complejidad de tiempo de O ( n log 3 / log 1,5 ) = O ( n 2,7095 ... ) Puede estabilizarse y también es una red de clasificación .
Clasificación lenta norte No Un algoritmo de multiplicar y entregar, antónimo del algoritmo de dividir y conquistar .

Los científicos informáticos teóricos han detallado otros algoritmos de clasificación que proporcionan una complejidad de tiempo mejor que O ( n log n ) asumiendo restricciones adicionales, que incluyen:

  • El algoritmo de Thorup , un algoritmo aleatorio para ordenar claves de un dominio de tamaño finito, tomando O ( n log log n ) tiempo y O ( n ) espacio.
  • Un algoritmo de clasificación de enteros aleatorios que toma el tiempo esperado y el espacio O ( n ).

Algoritmos de clasificación populares

Si bien hay una gran cantidad de algoritmos de clasificación, en las implementaciones prácticas predominan algunos algoritmos. La ordenación por inserción se usa ampliamente para conjuntos de datos pequeños, mientras que para conjuntos de datos grandes se usa una ordenación 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 el ordenamiento por inserción para listas pequeñas en la parte inferior de una recursividad. Las implementaciones altamente ajustadas usan variantes más sofisticadas, como Timsort (ordenación por fusión, ordenación por inserción y lógica adicional), que se usa en Android, Java y Python, e introsort ( ordenación rápida y ordenación en memoria ), que se usa (en formas variantes) en alguna ordenación de C ++. implementaciones y en .NET.

Para datos más restringidos, como números en un intervalo fijo, se utilizan ampliamente los tipos de distribución , como el ordenamiento por conteo o el ordenamiento por base. La clasificación y las variantes de las burbujas rara vez se usan en la práctica, pero se encuentran comúnmente en la enseñanza y las discusiones teóricas.

Cuando se clasifican objetos físicamente (como alfabetizar trabajos, exámenes o libros), la gente generalmente usa intuitivamente ordenamientos de inserción para conjuntos pequeños. En el caso de conjuntos más grandes, la gente suele colocar primero el balde, por ejemplo, por la letra inicial, y el agrupamiento múltiple permite clasificar de forma práctica conjuntos muy grandes. A menudo, el espacio es relativamente barato, por ejemplo, al esparcir objetos en el piso o sobre un área grande, pero las operaciones son costosas, particularmente mover un objeto a una gran distancia; la localidad de referencia es importante. Los tipos de combinación también son prácticos para los objetos físicos, en particular porque se pueden usar dos manos, una para cada lista para combinar, mientras que otros algoritmos, como heapsort o quicksort, no son adecuados para el uso humano. Otros algoritmos, como el ordenamiento por biblioteca , una variante del ordenamiento por inserción que deja espacios, también son prácticos para uso físico.

Clases simples

Dos de los tipos más simples son el ordenamiento por inserción y el ordenamiento por selección, los cuales son eficientes en datos pequeños, debido a la baja sobrecarga, pero no eficientes en 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 rendimiento en datos casi ordenados y, por lo tanto, se prefiere en la práctica, pero la ordenación por selección usa menos escrituras y, por lo tanto, se usa cuando el rendimiento de escritura es un factor limitante.

Tipo de inserción

La ordenación por inserción es un algoritmo de ordenación simple que es relativamente eficiente para listas pequeñas y en su mayoría listas ordenadas, y a menudo se usa 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 similar a cómo ponemos dinero en nuestra billetera. En los arreglos, la nueva lista y los elementos restantes pueden compartir el espacio del arreglo, pero la inserción es costosa y requiere cambiar todos los elementos siguientes uno por uno. Shellsort (ver más abajo) es una variante del ordenamiento por inserción que es más eficiente para listas más grandes.

Orden de selección

La clasificación por selección es una clasificación por comparación in situ . Tiene una complejidad O ( n 2 ), lo que lo hace ineficaz en listas grandes y, en general, funciona peor que el tipo de inserción similar . El ordenamiento por selección se destaca por su simplicidad y también tiene ventajas de rendimiento sobre algoritmos más complicados en determinadas 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. No hace más de n intercambios y, por lo tanto, es útil cuando el intercambio es muy caro.

Clases eficientes

Los algoritmos prácticos de clasificación general casi siempre se basan en un algoritmo con una complejidad de tiempo promedio (y generalmente la complejidad del peor de los casos) O ( n log n ), de los cuales los más comunes son la clasificación en pila, la clasificación por combinación y la clasificación rápida. Cada uno tiene ventajas e inconvenientes, siendo el más significativo que la implementación simple de la ordenación por fusión utiliza un espacio adicional O ( n ), y la implementación simple de la ordenación rápida tiene una complejidad en el peor de los casos O ( n 2 ). Estos problemas pueden resolverse o mejorarse a costa de un algoritmo más complejo.

Si bien estos algoritmos son asintóticamente eficientes en datos aleatorios, para una eficacia práctica en datos del mundo real se utilizan varias modificaciones. Primero, la sobrecarga de estos algoritmos se vuelve significativa en datos más pequeños, por lo que a menudo se usa 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 los datos del mundo real y se pueden clasificar en O ( n ) tiempo mediante algoritmos apropiados. Finalmente, también pueden ser inestables , y la estabilidad es a menudo una propiedad deseable en cierto tipo. Por lo tanto, a menudo se emplean algoritmos más sofisticados, como Timsort (basado en el ordenamiento por fusión) o introsort (basado en el ordenamiento rápido, recurriendo al ordenamiento dinámico ).

Combinar ordenación

Combinar ordenación aprovecha la facilidad de combinar 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 viene 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 menos dos listas se fusionen en la lista ordenada final. De los algoritmos descritos aquí, este es el primero que escala bien a listas muy grandes, porque su peor tiempo de ejecución es O ( n log n ). También se aplica fácilmente a listas, no solo matrices, ya que solo requiere acceso secuencial, no acceso aleatorio. Sin embargo, tiene una complejidad adicional en el espacio O ( n ) e implica una gran cantidad de copias en implementaciones simples.

Merge sort 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 y Java (a partir de JDK7 ). Merge sort en sí es la rutina estándar en Perl , entre otros, y se ha utilizado en Java al menos desde 2000 en JDK1.3 .

Heapsort

Heapsort es una versión mucho más eficiente del ordenamiento 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 realiza esta tarea de manera eficiente mediante el uso de una estructura de datos llamada montón , un tipo especial de árbol binario . Una vez que la lista de datos se ha convertido en un montón, se garantiza que el nodo raíz es el elemento más grande (o más pequeño). Cuando se elimina y se coloca al final de la lista, el montón se reorganiza para que el elemento más grande restante se mueva a la raíz. Usando el montón, encontrar el siguiente elemento más grande toma O (log n ) tiempo, en lugar de O ( n ) para un escaneo lineal como en la ordenación de selección simple. Esto permite que Heapsort se ejecute en tiempo O ( n log n ), y esta también es la complejidad del peor de los casos.

Ordenación rápida

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 . Todos los elementos más pequeños que el pivote se mueven antes y todos los elementos mayores se mueven después. Esto se puede hacer de manera eficiente en tiempo lineal e in situ . Las sublistas menores y mayores se clasifican de forma recursiva. Esto produce una complejidad de tiempo promedio de O ( n log n ), con una sobrecarga baja y, por lo tanto, este es un algoritmo popular. Las implementaciones eficientes de clasificación rápida (con particiones in situ) suelen ser clasificaciones inestables y algo complejas, pero se encuentran entre los algoritmos de clasificación más rápidos en la práctica. Junto con su modesto uso de espacio O (log n ), quicksort es uno de los algoritmos de clasificación más populares y está disponible en muchas bibliotecas de programación estándar.

La advertencia importante sobre el ordenamiento rápido es que su peor desempeño es O ( n 2 ); aunque esto es raro, 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 el ordenamiento rápido es, por lo tanto, elegir un buen elemento de pivote, ya que las elecciones consistentemente malas de pivotes pueden resultar en un rendimiento de O ( n 2 ) drásticamente más lento , pero una buena elección de pivotes produce un rendimiento de 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 ). Sin embargo , encontrar la mediana, como por medio del algoritmo de selección de la mediana de las medianas , es una operación O ( n ) en listas no clasificadas y, por lo tanto, exige una sobrecarga significativa con la clasificación. En la práctica, la elección de un pivote aleatorio casi con certeza produce un rendimiento de O ( n  log  n ).

Shellsort

Un Shellsort, diferente del tipo de burbuja, mueve elementos a numerosas posiciones de intercambio .

Shellsort fue inventado por Donald Shell en 1959. Mejora el ordenamiento por inserción al mover 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 el tiempo, donde k es la mayor distancia entre dos elementos fuera de lugar. Esto significa que, en general, funcionan en O ( n 2 ), pero para los datos que en su mayoría están ordenados, con solo unos pocos elementos fuera de lugar, funcionan más rápido. Por lo tanto, al ordenar primero los elementos que están lejos y reducir progresivamente la brecha entre los elementos para 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 mediante la ordenación por inserción.

La complejidad de tiempo del peor caso de Shellsort es un problema abierto y depende de la secuencia de huecos 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 su lugar , solo necesita una cantidad relativamente pequeña de código y no requiere el uso de la pila de llamadas , hace que sea útil en situaciones en las que la memoria es escasa, como en los sistemas integrados. y núcleos del sistema operativo .

Clases y variantes de burbujas

La clasificación de burbujas y variantes como la clasificación de Shell y la clasificación de cóctel son algoritmos de clasificación simples y altamente ineficientes. Se ven con frecuencia en los textos introductorios debido a la facilidad de análisis, pero rara vez se utilizan en la práctica.

Ordenamiento de burbuja

Una clasificación de burbujas, un algoritmo de clasificación que recorre continuamente una lista, intercambiando elementos hasta que aparecen en el orden correcto.

La clasificación de burbujas es un algoritmo de clasificación simple. El algoritmo comienza al comienzo 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 de nuevo con los dos primeros elementos y se repite hasta que no se hayan producido cambios en la última pasada. El tiempo promedio de este algoritmo y el rendimiento en el peor de los casos es O ( n 2 ), por lo que rara vez se usa para clasificar conjuntos de datos grandes y desordenados. La clasificación de burbujas se puede utilizar para clasificar una pequeña cantidad de elementos (donde su ineficiencia asintótica no es una penalización alta). La clasificación de burbujas 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 en una sola posición (p. Ej., 0123546789 y 1032547698), el intercambio de clasificación de burbujas los pondrá en orden en el primer paso, el segundo paso encontrará todos los elementos en orden, por lo que el orden será toma solo 2 n tiempo.

Tipo de peine

La clasificación por peine es un algoritmo de clasificación relativamente simple basado en la clasificación por burbujas y diseñado originalmente por Włodzimierz Dobosiewicz en 1980. 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 una clasificación de burbuja estos ralentizan enormemente la clasificación. (Los conejos , valores grandes alrededor del comienzo de la lista, no plantean un problema en la clasificación de burbujas) Esto se logra intercambiando inicialmente elementos que están a cierta distancia entre sí en la matriz, en lugar de solo intercambiar elementos si están adyacentes a entre sí, y luego reduciendo la distancia elegida hasta que funcione como una especie de burbuja normal. Por lo tanto, si se puede pensar en Shellsort como una versión generalizada de la ordenación por inserción que intercambia elementos espaciados a cierta distancia entre sí, la ordenación en peine puede considerarse como la misma generalización aplicada a la ordenación por burbujas.

Tipo de intercambio

La clasificación de intercambio a veces se confunde con la clasificación de burbujas, aunque los algoritmos son de hecho distintos. La clasificación de 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 orden de clasificación final; luego procede a hacer lo mismo con el segundo elemento, y así sucesivamente. Carece de la ventaja que tiene la clasificación de burbujas de detectar en una pasada si la lista ya está ordenada, pero puede ser más rápido que la clasificación de burbujas por un factor constante (una pasada menos sobre los datos que se van a ordenar; la mitad de comparaciones totales) en situaciones en el peor de los casos. Como cualquier ordenamiento simple O ( n 2 ), puede ser razonablemente rápido en conjuntos de datos muy pequeños, aunque en general el ordenamiento por inserción será más rápido.

Tipo de distribución

La clasificación de distribución se refiere a cualquier algoritmo de clasificación donde los datos se distribuyen desde su entrada a múltiples estructuras intermedias que luego se recopilan y colocan en la salida. Por ejemplo, tanto cubo especie y flashsort son de distribución basados en algoritmos de ordenación. Los algoritmos de clasificación de distribución se pueden usar en un solo procesador, o pueden ser un algoritmo distribuido , donde los subconjuntos individuales se clasifican por separado en diferentes procesadores y luego se combinan. Esto permite la clasificación externa de datos demasiado grandes para caber en la memoria de una sola computadora.

Contando ordenar

El ordenamiento por recuento es aplicable cuando se sabe que cada entrada pertenece a un conjunto particular, S , de posibilidades. El algoritmo se ejecuta en la memoria O (| S | + n ) tiempo y O (| S |) donde n es la longitud de la entrada. Funciona creando una matriz entera de tamaño | S | y usar el i- ésimo bin para contar las apariciones del i- ésimo miembro de S en la entrada. Luego, cada entrada se cuenta incrementando el valor de su ubicación correspondiente. Luego, la matriz de conteo se recorre en bucle para organizar todas las entradas en orden. Este algoritmo de clasificación a menudo no se puede utilizar porque S necesita 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.

Tipo de cubo

La ordenación de cubos es un algoritmo de clasificación de divide y vencerás que generaliza la ordenación de conteo dividiendo una matriz en un número finito de cubos. Luego, cada depósito se clasifica individualmente, ya sea utilizando un algoritmo de clasificación diferente o aplicando de forma recursiva el algoritmo de clasificación de depósitos.

Una clasificación de depósito funciona mejor cuando los elementos del conjunto de datos se distribuyen uniformemente en todos los depósitos.

Orden de radix

La ordenación por radix es un algoritmo que ordena números procesando dígitos individuales. n números que constan de k dígitos cada uno se ordenan en O ( n · k ) tiempo. La clasificación por radix puede procesar dígitos de cada número, ya sea 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 usando un ordenamiento estable. Luego los ordena por el siguiente dígito, y así sucesivamente desde el menos significativo al más significativo, terminando con una lista ordenada. Mientras que la clasificación de base LSD requiere el uso de una clasificación estable, el algoritmo de clasificación de base MSD no lo requiere (a menos que se desee una clasificación estable). La ordenación por radix de MSD in situ no es estable. Es común que el algoritmo de ordenación de conteo sea ​​utilizado internamente por la ordenación de radix. Un enfoque de clasificación híbrido , como el uso de la clasificación por inserción para contenedores pequeños, mejora significativamente el rendimiento de la clasificación por radix.

Patrones de uso de memoria y clasificación de índices

Cuando el tamaño de la matriz que se va a clasificar se acerca o excede la memoria primaria disponible, de modo que se debe emplear un disco (mucho más lento) o espacio de intercambio, el patrón de uso de memoria de un algoritmo de clasificación se vuelve importante, y un algoritmo que podría haber sido bastante eficiente cuando la matriz encaja fácilmente en la RAM puede volverse poco práctica. 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, en comparación a la velocidad del disco, es prácticamente instantáneo.

Por ejemplo, el popular algoritmo de ordenación rápida recursiva proporciona un rendimiento bastante razonable con la RAM adecuada, pero debido a la forma recursiva en la que copia partes de la matriz, se vuelve mucho menos práctico cuando la matriz no cabe en la RAM, ya que puede provocar una serie de errores. operaciones de copia o movimiento lento hacia y desde el disco. En ese escenario, puede ser preferible otro algoritmo incluso si requiere comparaciones más totales.

Una forma de solucionar este problema, que funciona bien cuando los registros complejos (como en una base de datos relacional ) se ordenan por un campo clave relativamente pequeño, es crear un índice en la matriz y luego ordenar el índice, en lugar de todo el formación. (Se puede producir una versión ordenada de toda la matriz con una pasada, leyendo del índice, pero a menudo incluso eso es innecesario, ya que tener el índice ordenado es adecuado). Debido a que el índice es mucho más pequeño que la matriz completa, puede caben fácilmente en la memoria donde no lo haría todo el arreglo, eliminando efectivamente el problema de intercambio de disco. Este procedimiento a veces se denomina "clasificación de etiquetas".

Otra técnica para superar el problema del tamaño de la memoria es utilizar la clasificación externa ; por ejemplo, una de las formas es combinar dos algoritmos de manera que se 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 ordena mediante un algoritmo eficiente (como la clasificación rápida ) y los resultados se fusionan mediante una combinación de k- vías similar a la utilizada en fusionar ordenación . Esto es más rápido que realizar una ordenación combinada o una ordenación rápida en toda la lista.

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 memoria virtual , es decir, para reducir la cantidad de intercambio requerido.

Algoritmos relacionados

Los problemas relacionados incluyen la ordenación parcial (ordenando solo los k elementos más pequeños de una lista o, alternativamente, calculando los k elementos más pequeños, pero desordenados) y la selección (calculando el k- ésimo elemento más pequeño). Estos pueden resolverse de manera ineficiente mediante una clasificación total, pero existen algoritmos más eficientes, que a menudo se derivan de la generalización de un algoritmo de clasificación. El ejemplo más notable es la selección rápida , que está relacionada con la ordenación rápida . A la inversa, algunos algoritmos de clasificación se pueden derivar mediante la aplicación repetida de un algoritmo de selección; Quicksort y quickselect pueden verse como el mismo movimiento pivotante, difiriendo solo en si uno recurre en ambos lados (quicksort, divide y vencerás ) o en un lado (quickselect, disminuir y conquistar ).

Una especie de opuesto de un algoritmo de clasificación es un algoritmo de barajado . Estos son fundamentalmente diferentes porque requieren una fuente de números aleatorios. La mezcla también se puede implementar mediante un algoritmo de clasificación, es decir, mediante una clasificación aleatoria: asignando un número aleatorio a cada elemento de la lista y luego clasificando según los números aleatorios. Sin embargo, esto generalmente no se hace en la práctica, y existe un algoritmo simple y eficiente bien conocido para barajar: la baraja de Fisher-Yates .

Ver también

Referencias

Otras lecturas

enlaces externos