Algoritmo de clasificación

Un algoritmo de ordenación es, en informática o matemáticas , un algoritmo que permite organizar una colección de objetos según una determinada relación de orden . Los objetos a clasificar son elementos de un conjunto provisto de un orden total . Por ejemplo, es común ordenar los números enteros según la relación de orden habitual "es menor o igual que". Los algoritmos de clasificación se utilizan en muchas situaciones. Son particularmente útiles para muchos algoritmos más complejos , incluidos algunos algoritmos de búsqueda , como la búsqueda dicotómica.. También se pueden utilizar para formatear datos canónicamente o hacerlos más legibles para el usuario.

La colección a ordenar se da a menudo en forma de matriz , para permitir el acceso directo a los diferentes elementos de la colección, o en forma de lista , que puede resultar más adecuada para ciertos algoritmos y para el uso de la programación funcional .

Un buen número de algoritmos de ordenación proceden de comparaciones sucesivas y, por tanto, pueden definirse independientemente del conjunto al que pertenecen los elementos y de la relación de orden asociada. El mismo algoritmo se puede utilizar, por ejemplo, para clasificar números reales de acuerdo con la relación de orden habitual "es menor o igual que" y cadenas de caracteres de acuerdo con el orden lexicográfico . Estos algoritmos se prestan naturalmente a una implementación polimórfica .

Los algoritmos de clasificación a menudo se estudian en cursos de algoritmos para introducir conceptos como complejidad algorítmica o terminación .

Criterios de clasificación

La clasificación de los algoritmos de ordenación es muy importante, porque permite elegir el algoritmo más adecuado al problema tratado, teniendo en cuenta las limitaciones que impone. Las principales características que distinguen a los algoritmos de ordenación, además de su principio de funcionamiento, son la complejidad temporal , la complejidad espacial y el carácter estable.

Principio de funcionamiento

Se hace una distinción entre los algoritmos que proceden de comparaciones sucesivas entre elementos, conocidos como "clasificación por comparación", de los algoritmos más especializados que hacen suposiciones restrictivas sobre la estructura de los datos que se van a clasificar (por ejemplo, la clasificación por conteo, aplicable solo si los datos se toman en un conjunto acotado conocido de antemano).

Los algoritmos de clasificación por comparación leen las entradas solo por medio de una función de comparación binaria o ternaria (cuando el caso de igualdad se trata de manera diferente). Todavía existen diferentes principios operativos dentro de esta clase: algunos algoritmos de clasificación por comparación proceden por inserciones sucesivas, otros por fusión, otros por selección.

En ausencia de detalles, el término "algoritmo de clasificación" generalmente significa un algoritmo de clasificación que procede de comparaciones.

Complejidad algorítmica

• La complejidad del tiempo ( promedio o en el peor de los casos ) mide el número de operaciones elementales para clasificar una colección de elementos. Este es un criterio importante para comparar algoritmos de clasificación, ya que es una estimación directa del tiempo de ejecución del algoritmo. En el caso de los algoritmos de clasificación por comparación, la complejidad del tiempo se asimila con mayor frecuencia al número de comparaciones realizadas, realizándose la comparación y el posible intercambio de dos valores en tiempo constante.
• La complejidad espacial ( en promedio o en el peor de los casos ) representa, por su parte, la cantidad de memoria que necesitará el algoritmo para ejecutarse. Esto puede depender, como el tiempo de ejecución, del tamaño de la entrada. Es común que las complejidades espaciales promedio y en el peor de los casos sean las mismas. Este es a menudo implícitamente el caso cuando se da una complejidad sin más indicaciones.

La complejidad del tiempo se observa a menudo y se expresa en función del número de elementos que se ordenarán utilizando notaciones de Landau y . T{\ Displaystyle T}no{\ Displaystyle n} O{\ Displaystyle O}Θ{\ Displaystyle \ Theta}

Algunos algoritmos de ordenación simples tienen una complejidad en tiempo cuadrático, es decir , mientras que otros, más desarrollados, tienen una complejidad casi lineal . T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}T(no)=O(noIniciar sesión⁡(no)){\ Displaystyle T (n) = O (n \ log (n))}

La complejidad de tiempo promedio de un algoritmo basado en una función de comparación no puede ser mejor que . Por lo tanto, se dice que los tipos que solo requieren comparaciones en promedio son óptimos. Este resultado constituye un límite inferior asintótico, pero también mostramos que el número exacto de comparaciones necesarias se reduce en . O(noIniciar sesión⁡(no)){\ Displaystyle O (n \ log (n))}O(noIniciar sesión⁡(no)){\ Displaystyle O (n \ log (n))}⌈Iniciar sesión2⁡(no!)⌉{\ Displaystyle \ lceil \ log _ {2} (n!) \ rceil}

Demostración

El problema de clasificación consiste en, dada una serie de elementos de un conjunto totalmente ordenado (por ejemplo proporcionado con el orden usual), en la determinación de una permutación de tal manera que está ordenada. tu=(tu1,tu2,...,tuno){\ Displaystyle u = (u_ {1}, u_ {2}, \ dots, u_ {n})}NO{\ Displaystyle \ mathbb {N}}σ{\ Displaystyle \ sigma}1,...,no{\ Displaystyle 1, \ dots, n}(tuσ(1),...,tuσ(no)){\ Displaystyle (u _ {\ sigma (1)}, \ dots, u _ {\ sigma (n)})}

Por simplicidad, se supone que todos los elementos que se van a clasificar son distintos, lo que hace que la permutación sea única. El resultado sigue siendo cierto a fortiori en el caso general. σ{\ Displaystyle \ sigma}

Un algoritmo de clasificación mediante comparaciones sucesivas se modela como un árbol binario . Cada nodo del árbol corresponde a una comparación entre dos elementos y , y comprende dos hijos que representan las siguientes dos posibles comparaciones en función del resultado del primero. tuI{\ Displaystyle u_ {i}}tuj{\ Displaystyle u_ {j}}

Cada ejecución del algoritmo en una permutación de puede asociarse con la ruta que va de la raíz a la hoja correspondiente a esta ejecución; dos entradas diferentes están necesariamente asociadas con dos caminos diferentes. El número de permutaciones de elementos distintos de dos en dos es que el número de hojas del árbol es mayor o igual a este valor. tu{\ Displaystyle u}no{\ Displaystyle n}no!{\ Displaystyle n!}

Límite inferior para la complejidad del peor de los casos

Tenga en cuenta la altura del árbol ( es decir, su profundidad máxima, que corresponde al número de comparaciones en el peor de los casos ). El número máximo de hojas en un árbol de altura binaria es . h{\ Displaystyle h}h{\ Displaystyle h}2h{\ Displaystyle 2 ^ {h}}

Por lo tanto, es: . Por un lado . Por otro lado, usando la fórmula de Stirling , obtenemos asintóticamente . 2h≥no!{\ Displaystyle 2 ^ {h} \ geq n!}h≥⌈Iniciar sesión2⁡(no!)⌉{\ Displaystyle h \ geq \ lceil \ log _ {2} (¡n!) \ rceil}h≥no⋅Iniciar sesión2⁡(no)-no/en⁡2=Θ(noIniciar sesión⁡no){\ Displaystyle h \ geq n \ cdot \ log _ {2} (n) -n / \ ln 2 = \ Theta (n \, \ log n)}

El hecho de que haya géneros muestra por otro lado que es posible tener asintóticamente . Por lo tanto, este límite proporciona la complejidad mínima en el peor de los casos de un algoritmo de clasificación por comparaciones. no⋅Iniciar sesión2⁡(no){\ Displaystyle n \ cdot \ log _ {2} (n)}h≤no⋅Iniciar sesión2⁡(no){\ Displaystyle h \ leq n \ cdot \ log _ {2} (n)}

Límite inferior de complejidad media

Dado un árbol binario , denotamos la profundidad promedio de las hojas de . Si todas las permutaciones de los elementos de entrada son igualmente probables, entonces el número promedio de comparaciones del tipo con un árbol de comparación es . A{\ Displaystyle A}F(A){\ Displaystyle F (A)}A{\ Displaystyle A}A{\ Displaystyle A}F(A){\ Displaystyle F (A)}

Para un número fijo de nodos, los árboles minimizadores son los árboles binarios completos (es decir, aquellos cuyas hojas están en el último o penúltimo nivel). De hecho, en un árbol incompleto, hay una hoja profunda y una hoja profunda como máximo . Colgando la primera hoja a la segunda, obtenemos un árbol como . F{\ Displaystyle F}A{\ Displaystyle A}h{\ Displaystyle h}h-2{\ Displaystyle h-2}A′{\ Displaystyle A '}F(A′)<F(A){\ Displaystyle F (A ') <F (A)}

La función toma el mismo valor para todos los árboles binarios completos con hojas. Cualquiera de ellos y su altura. Todas las hojas son al menos profundas , por lo que la profundidad promedio de las hojas es al menos (nuevamente usando la propiedad ). F{\ Displaystyle F}no!{\ Displaystyle n!}A{\ Displaystyle A}h{\ Displaystyle h}h-1{\ Displaystyle h-1}h-1=Ω(noIniciar sesión⁡no){\ Displaystyle h-1 = \ Omega (n \, \ log n)}2h≥no!{\ Displaystyle 2 ^ {h} \ geq n!}

Sin embargo, para ciertos tipos de datos (números enteros, cadenas de caracteres de tamaño limitado), existen algoritmos que son más eficientes en términos de tiempo de ejecución, como la clasificación por recuento o la clasificación por base . Estos algoritmos no utilizan la comparación entre elementos (el límite n · log (n) no se aplica a ellos), pero requieren suposiciones sobre los objetos a clasificar. Por ejemplo, la ordenación por conteo y la ordenación por base se aplican a los enteros que sabemos que pertenecen al conjunto [1, m ] con una suposición adicional para la ordenación por base de que m es una potencia de 2 (c 'es decir, de la forma 2k ).

Clasificación en su lugar

Se dice que un ordenamiento está en su lugar si solo usa un número muy limitado de variables y modifica directamente la estructura que está ordenando. Esto requiere el uso de una estructura de datos adaptada (una matriz, por ejemplo). Este personaje puede ser muy importante si no tienes mucha memoria.

Sin embargo, en general, los datos en sí no se mueven, sino que solo se modifican las referencias (o punteros ) a ellos.

Clasificación estable

Se dice que un género es estable si conserva el orden inicial de los elementos que el orden considera iguales. Para definir esta noción, es necesario que la colección a ordenar esté ordenada de cierta manera (que es a menudo el caso de muchas estructuras de datos , por ejemplo, para listas o arreglos).

Ejemplo:

Definamos la relación de orden definida sobre los pares de enteros por ssi , que permite ordenar dos pares según su primer valor. ≼{\ Displaystyle \ preccurlyeq}(a,B)≼(vs,D){\ Displaystyle (a, b) \ preccurlyeq (c, d)}a≤vs{\ Displaystyle a \ leq c}

Es decir una lista de parejas de números enteros que se desea ordenar según la relación previamente definida. L=[(4,1);(3,2);(3,3);(5,4)]{\ Displaystyle L = [(4.1); (3.2); (3.3); (5.4)]}≼{\ Displaystyle \ preccurlyeq}

Dado que y son iguales para la relación , llamar a un algoritmo de ordenación con entrada puede conducir a dos salidas diferentes: (3,2){\ Displaystyle (3,2)}(3,3){\ Displaystyle (3.3)}≼{\ Displaystyle \ preccurlyeq}L{\ Displaystyle L}

• L1=[(3,2);(3,3);(4,1);(5,4)]{\ Displaystyle L_ {1} = [(3.2); (3.3); (4.1); (5.4)]}
• L2=[(3,3);(3,2);(4,1);(5,4)]{\ Displaystyle L_ {2} = [(3.3); (3.2); (4.1); (5.4)]}

L1{\ Displaystyle L_ {1}}y ambos se ordenan de acuerdo con , pero solo conservan el orden relativo. En , aparece antes , por lo tanto, un algoritmo de clasificación que se hubiera tomado como entrada y devuelto como salida sería inestable. L2{\ Displaystyle L_ {2}}≼{\ Displaystyle \ preccurlyeq}L1{\ Displaystyle L_ {1}}L2{\ Displaystyle L_ {2}}(3,3){\ Displaystyle (3.3)}(3,2){\ Displaystyle (3,2)}L{\ Displaystyle L}L2{\ Displaystyle L_ {2}}

Los algoritmos de clasificación inestable se pueden reelaborar específicamente para hacerlos estables, sin embargo, esto puede ser a expensas de la velocidad y / o puede requerir espacio de memoria adicional.

Entre los algoritmos que se enumeran a continuación, los tipos estables son: el tipo de burbuja , el tipo de inserción y el tipo de combinación . Los otros algoritmos requieren memoria adicional para almacenar el orden inicial de los elementos. O(no){\ Displaystyle O (n)}

Clasificación interna y externa

Una clasificación interna se lleva a cabo completamente en la memoria central, mientras que una clasificación externa utiliza archivos en una memoria masiva para clasificar volúmenes que son demasiado grandes para poder caber en la memoria central. Ciertos tipos de clasificación, como la clasificación por fusión o la clasificación por distribución, se adaptan fácilmente al uso de la memoria externa. Otros algoritmos, en cambio, acceden a los datos de tal manera que no se prestan a este uso porque requeriría realizar constantemente lecturas / escrituras entre la memoria principal y la externa.

Clasificación paralela

Ciertos algoritmos permiten aprovechar las capacidades multitarea de la máquina. Cabe señalar también que determinados algoritmos, en particular los que funcionan por inserción, pueden iniciarse sin conocer todos los datos a ordenar; luego podemos ordenar y producir los datos para ordenarlos en paralelo.

Comparación de algoritmos

La siguiente tabla permite comparar diferentes algoritmos de clasificación procediendo mediante comparaciones. y representa el número de elementos que se van a ordenar. Todas las complejidades deben interpretarse utilizando una O mayúscula de Landau . Se supone que las operaciones básicas como comparaciones e intercambios se pueden realizar en tiempo constante. no{\ Displaystyle n}

Tabla comparativa de tipos usando comparaciones

apellido	Caso óptimo	Caso medio	Peor de los casos	Complejidad espacial	Estable
Ordenación rápida	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	no2{\ Displaystyle n ^ {2}}	Iniciar sesión⁡no{\ Displaystyle \ log n}en promedio, en el peor de los casos; Variante de Sedgewick: el peor de los casosno{\ Displaystyle n} Iniciar sesión⁡no{\ Displaystyle \ log n}	No
Combinar ordenación	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	no{\ Displaystyle n}	sí
Ordenar por montón	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	1{\ Displaystyle 1}	No
Ordenar por inserción	no{\ Displaystyle n}	no2{\ Displaystyle n ^ {2}}	no2{\ Displaystyle n ^ {2}}	1{\ Displaystyle 1}	sí
Introsort	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	Iniciar sesión⁡no{\ Displaystyle \ log n}	No
Ordenar por selección	no2{\ Displaystyle n ^ {2}}	no2{\ Displaystyle n ^ {2}}	no2{\ Displaystyle n ^ {2}}	1{\ Displaystyle 1}	No
Timsort	no{\ Displaystyle n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	no{\ Displaystyle n}	sí
Clasificación de conchas	no{\ Displaystyle n}	noIniciar sesión2⁡no{\ Displaystyle n \ log ^ {2} n} o no3/2{\ Displaystyle n ^ {3/2}}	noIniciar sesión2⁡no{\ Displaystyle n \ log ^ {2} n}para la secuencia de espaciado más conocida	1{\ Displaystyle 1}	No
Clasificación de burbujas	no{\ Displaystyle n}	no2{\ Displaystyle n ^ {2}}	no2{\ Displaystyle n ^ {2}}	1{\ Displaystyle 1}	sí
Clasificación de árboles	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n} (árbol equilibrado)	no{\ Displaystyle n}	sí
Smoothsort	no{\ Displaystyle n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	1{\ Displaystyle 1}	No
Clasificación de cócteles	no{\ Displaystyle n}	no2{\ Displaystyle n ^ {2}}	no2{\ Displaystyle n ^ {2}}	1{\ Displaystyle 1}	sí
Clasificación de peine	no{\ Displaystyle n}	noIniciar sesión⁡no{\ Displaystyle n \ log n}	no2{\ Displaystyle n ^ {2}}	1{\ Displaystyle 1}	No
Tipo par-impar	no{\ Displaystyle n}	no2{\ Displaystyle n ^ {2}}	no2{\ Displaystyle n ^ {2}}	1{\ Displaystyle 1}	sí

Ejemplos de algoritmos de clasificación

Ordenar por comparación

Algoritmos rápidos

• Clasificar combinación ( combinación de clasificación ) - en todos los casos; estable; no está en su lugar por defecto. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}Este algoritmo se basa en el principio de "divide y vencerás" . Para una entrada determinada, el algoritmo la divide en dos partes de tamaños similares, ordena cada una de ellas utilizando el mismo algoritmo y luego fusiona las dos partes ordenadas. Es adecuado para implementaciones de listas y tablas. Es utilizado en particular por el algoritmo híbrido Timsort .
• Clasificación rápida ( clasificación rápida ): en promedio y, en el mejor de los casos, en el peor de los casos; inestable; en su lugar en la variante Sedgewick. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}Este método se basa en el principio de "divide y vencerás" . Se elige un valor como pivote y los elementos menores que el pivote se disocian, mediante intercambios sucesivos, de los elementos mayores que el pivote; cada uno de estos dos subconjuntos se clasifica de la misma manera. La complejidad se puede hacer casi independiente de los datos utilizando un pivote aleatorio o aplicando una permutación aleatoria a la matriz antes de ordenarla.
• Ordenar por montón ( clasificación de montón ) - en todos los casos; en su lugar pero inestable. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}Esta es una mejora en la clasificación por selección . La idea es la misma (insertar los elementos uno por uno en una estructura ya ordenada), pero el algoritmo usa una estructura de montón , a menudo implementada por medio de una matriz. Este algoritmo funciona muy bien junto con Quick Sort. De hecho, es eficaz cuando se sospecha que los datos se acercan al peor de los casos (cuadrático) del tipo rápido.
• Introsort - en todos los casos; inestable pero en su lugar. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}Es un híbrido de clasificación rápida y clasificación de pilas .
• Ordenar árbol : en promedio, peor de los casos, mejor de los casos. ; ni estable ni en su lugar. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}T(no)=O(no){\ Displaystyle T (n) = O (n)}La idea es insertar los elementos uno por uno en un árbol de búsqueda binario , luego leer el árbol según una ruta en profundidad. Este tipo es uno de los más lentos (entre los tipos rápidos) y uno de los más intensivos en memoria debido a la estructura de árbol binario que se debe manejar. Es posible hacerlo casi lineal en todos los casos Manteniendo un árbol equilibrado ( cf Tree AVL ).
• Smoothsort - en promedio y en el peor de los casos, en el mejor de los casos; en su lugar pero inestable. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}T(no)=O(no){\ Displaystyle T (n) = O (n)}Ordenar inspirado en la clasificación de montones , pero que utiliza un árbol no invertido . Esta clasificación es muy rápida para conjuntos que ya están casi ordenados.

Para un algoritmo de clasificación inestable dado, es fácil obtener una variante estable mediante el uso de una matriz adicional para almacenar el orden inicial de los elementos. Sin embargo, el algoritmo resultante no está implementado.

Algoritmos moderadamente rápidos

• Clasificación de concha ( clasificación de concha ): para la serie de pasos y para la serie de pasos  ; inestable; en su lugar. T(no)=O(noIniciar sesión2⁡no){\ Displaystyle T (n) = O (n \ log ^ {2} n)}2pag3q{\ Displaystyle 2 ^ {p} 3 ^ {q}}T(no)=O(no3/2){\ Displaystyle T (n) = O (n ^ {3/2})}2k-1{\ Displaystyle 2 ^ {k} -1}Esta clasificación se basa en la clasificación por inserción de las subsecuencias de la entrada obtenida al separar los elementos separados por un paso constante, para una secuencia de pasos predefinidos. La complejidad varía según la elección de esta suite. No sabemos de una serie de donaciones .O(noIniciar sesión⁡no){\ Displaystyle O (n \ log n)}
• Clasificar combinación ( combinación de clasificación ) - en todos los casos; estable; no está en su lugar por defecto. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}Este algoritmo se basa en el principio de "divide y vencerás" . Para una entrada determinada, el algoritmo la divide en dos partes de tamaños similares, ordena cada una de ellas utilizando el mismo algoritmo y luego fusiona las dos partes ordenadas. Es adecuado para implementaciones de listas y tablas. Es utilizado en particular por el algoritmo híbrido Timsort .
• Clasificación rápida ( clasificación rápida ): en promedio y, en el mejor de los casos, en el peor de los casos; inestable; en su lugar en la variante Sedgewick. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}Este método se basa en el principio de "divide y vencerás" . Se elige un valor como pivote y los elementos menores que el pivote se disocian, mediante intercambios sucesivos, de los elementos mayores que el pivote; cada uno de estos dos subconjuntos se clasifica de la misma manera. La complejidad se puede hacer casi independiente de los datos utilizando un pivote aleatorio o aplicando una permutación aleatoria a la matriz antes de ordenarla.
• Ordenar por montón ( clasificación de montón ) - en todos los casos; en su lugar pero inestable. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}Esta es una mejora en la clasificación por selección . La idea es la misma (insertar los elementos uno por uno en una estructura ya ordenada), pero el algoritmo usa una estructura de montón , a menudo implementada por medio de una matriz. Es interesante utilizar esta clasificación si se sospecha que los datos que se van a clasificar serán a menudo casos cuadráticos para la clasificación rápida.
• Introsort - en todos los casos; inestable pero en su lugar. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}Este es un algoritmo híbrido que utiliza los algoritmos de ordenación rápida y ordenación en montón .
• Ordenar árbol : en promedio, peor de los casos, mejor de los casos. ; ni estable ni en su lugar. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}T(no)=O(no){\ Displaystyle T (n) = O (n)}La idea es insertar los elementos uno por uno en un árbol de búsqueda binario , luego leer el árbol según una ruta en profundidad. Este tipo es uno de los más lentos (entre los tipos rápidos) y uno de los más intensivos en memoria debido a la estructura de árbol binario que se debe manejar. Es posible hacerlo casi lineal en todos los casos manteniendo un árbol equilibrado ( cf Tree AVL ).
• Smoothsort - en promedio y en el peor de los casos, en el mejor de los casos; en su lugar pero inestable. T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}T(no)=O(no){\ Displaystyle T (n) = O (n)}Ordenar inspirado en la clasificación de montón , pero que utiliza un árbol no invertido. Esta clasificación es muy rápida para conjuntos que ya están casi ordenados.
• Clasificación de peine ( clasificación de peine ): en el mejor de los casos, en promedio y en el peor de los casos; inestable pero en su lugar. T(no)=O(no){\ Displaystyle T (n) = O (n)}T(no)=O(noIniciar sesión⁡no){\ Displaystyle T (n) = O (n \ log n)}T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}Esta es una variante más eficiente de clasificación de burbujas , no solo comparando elementos consecutivos. Podemos decir que es para ordenar por burbujas lo que para Shell es para ordenar por inserción .

Para un algoritmo de clasificación inestable dado, es fácil obtener una variante estable mediante el uso de una matriz adicional para almacenar el orden inicial de los elementos. Sin embargo, el algoritmo resultante no está implementado. ence trabajando en listas).

• Es, en cada iteración, identificar el más pequeño de los elementos que aún no están ordenados e intercambiarlo con el primero de ellos. Esta clasificación es rápida para entradas pequeñas y está codificada de forma concisa.
• Clasificación por inserción : en promedio y en el peor de los casos, en el mejor de los casos; estable y en su lugar. T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}T(no)=O(no){\ Displaystyle T (n) = O (n)}Este es el tipo que se usa a menudo de forma natural para clasificar los naipes: los valores se insertan uno tras otro en una lista ordenada (inicialmente vacía). Suele ser el más rápido y el más utilizado para clasificar entradas pequeñas. También es eficaz para las entradas que ya están casi ordenadas.
• Clasificación de burbujas : en promedio y en el peor de los casos, en el mejor de los casos; estable y en su lugar. T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}T(no)=O(no){\ Displaystyle T (n) = O (n)}El algoritmo consiste en recorrer la entrada de principio a fin y, para cada par de elementos consecutivos, invertirlos si están mal ordenados. Esta operación se repite hasta que se ordena la estructura (sin inversión durante la última pasada). Este algoritmo es ineficaz y rara vez se utiliza en la práctica; su interés es principalmente educativo.
• Cóctel de clasificación : en promedio y en el peor de los casos, en el mejor de los casos; estable y en su lugar. T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}T(no)=O(no){\ Displaystyle T (n) = O (n)}Esta es una variante de clasificación de burbujas en la que la entrada se atraviesa alternativamente en ambas direcciones. Si permite abordar de forma más eficaz algunos casos problemáticos de clasificación de burbujas, sigue siendo esencialmente similar a este último y el interés vuelve a ser fundamentalmente educativo.
• Tipo par-impar : en promedio y en el peor de los casos, en el mejor de los casos; estable y en su lugar. T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}T(no)=O(no){\ Displaystyle T (n) = O (n)}Esta es una variante de la clasificación de burbujas, que funciona comparando sucesivamente todos los elementos de índice pares con los elementos de índice impares que los siguen, y luego viceversa. Por lo tanto, comenzaremos comparando el primer elemento con el segundo, el tercero con el cuarto, etc., luego compararemos el segundo elemento con el tercero, el cuarto con el quinto, etc. La operación se repite hasta que se ordena la estructura.

Algoritmos lentos

Estos algoritmos tienen una complejidad asintótica y, por lo tanto, se consideran lentos para entradas cuyo tamaño es superior a unas pocas decenas de elementos. O(no2){\ Displaystyle O (n ^ {2})}

• Ordenar por selección - en todos los casos; en el sitio ; inestable por defecto (se puede hacer estable, pero preferiblemente trabajando en listas).T(no)=O(no2){\ Displaystyle T (n) = O (n ^ {2})}

Algoritmos muy lentos

Estos algoritmos tienen una complejidad asintótica peor que , que es la complejidad de los algoritmos más intuitivos. O(no2){\ Displaystyle O (n ^ {2})}

• Clasificación estúpida : no termina en el peor de los casos, el promedio y el mejor de los casos; inestable pero en su lugar. T(no)=O(no!){\ Displaystyle T (n) = O (n!)}T(no)=O(no){\ Displaystyle T (n) = O (n)}La clasificación estúpida consiste en comprobar si los elementos están ordenados y si no, mezclando aleatoriamente los elementos y luego repitiendo la operación.
• Clasificador de títeres ( tipo títere ) - o aproximadamente  ; inestable y no en su lugar . T(no)=O(noIniciar sesión⁡3Iniciar sesión⁡1,5){\ Displaystyle T (n) = O (n ^ {\ frac {\ log 3} {\ log 1,5}})}O(no2,71){\ Displaystyle O (n ^ {2.71})}Esta clasificación consiste en intercambiar el primer y último elemento si es necesario, luego ordenar de forma recursiva los primeros dos tercios, luego los dos últimos, luego los dos primeros de la matriz nuevamente.

Ordena usando la estructura de datos

• Contando ordenar o ordenar por conteo ( contar ordenando ): Algoritmo lineal, T (n) = O (n), estable pero requiere el uso de una segunda lista de la misma longitud que la lista para ser ordenada. Su uso depende de la condición de que los valores a ordenar sean números naturales cuyos extremos conocemos;
• Ordenar por base (orden de base ): también es un orden lineal bajo ciertas condiciones (menos restrictivo que para ordenar por conteo), T (n) = O (n), estable pero también requiere el uso de una segunda lista de los mismos length como lista para ordenar;
• Clasificación de paquetes ( clasificación de cubos ): estable y linealmente compleja , se supone que los datos que se van a clasificar se distribuyen uniformemente en un intervalo real .T(no)=O(no){\ Displaystyle T (n) = O (n)}[a,B[{\ Displaystyle [a, b [}

Clases externas

Los algoritmos de clasificación también deben adaptarse de acuerdo con las configuraciones de computadora en las que se utilizan. En los ejemplos citados anteriormente, se asume que todos los datos están presentes en la memoria principal (o accesibles en la memoria virtual). La situación se vuelve más compleja si se quiere ordenar volúmenes de datos mayores que la memoria principal disponible (o si se busca mejorar la ordenación optimizando el uso de la jerarquía de la memoria).

Estos algoritmos a menudo se basan en un enfoque bastante similar al de la clasificación por fusión . El principio es el siguiente:

• dividir el volumen de datos que se clasificarán en subconjuntos de tamaño más pequeño que la memoria rápida disponible;
• ordenar cada subconjunto en la memoria principal para formar "monotonías" (subconjuntos ordenados);
• interclasificación de monotonías.

Elección empírica de un algoritmo de clasificación

Existen muchos algoritmos, pero algunos se utilizan mucho más que otros en la práctica. La ordenación por inserción a menudo se elogia para datos pequeños, mientras que los algoritmos asintóticamente eficientes como la ordenación por combinación , la ordenación en pila o la ordenación rápida se utilizarán para datos más grandes.

Hay implementaciones finamente optimizadas, que a menudo son algoritmos híbridos . Por tanto, Timsort utiliza los métodos de clasificación por fusión e inserción , y es utilizado por Android , Java y Python, entre otros  ; Introsort , que combina ordenación rápida y ordenación de montón , se usa en algunas implementaciones de ordenación de C ++ .

La comparación empírica de algoritmos no es fácil en la medida en que se tienen en cuenta muchos parámetros: tamaño de los datos, orden de los datos, hardware utilizado, tamaño de la RAM, etc. Por ejemplo, las pruebas realizadas sobre datos extraídos al azar no necesariamente representan de manera muy fiel los comportamientos obtenidos con datos reales.

Acceso a RAM

Para comparar diferentes algoritmos, es importante tener en cuenta el tamaño de los datos que se van a clasificar, así como la cantidad de RAM disponible. Cuando no hay suficiente RAM para almacenar datos, la computadora recurrirá al uso de memoria externa, lo que resultará en tiempos de acceso significativamente más largos.

En esta situación, los algoritmos que funcionan sucesivamente en partes más pequeñas de la entrada (que, por ejemplo, se fusionarán más adelante) tenderán a funcionar mejor que los algoritmos como quicksort, que realizarán más acceso a la memoria externa.

También es posible evitar tales situaciones, por ejemplo, asociando los datos a clasificar con claves más pequeñas y clasificando estas claves directamente en la RAM. Cuando el tamaño de los datos sea realmente grande, se utilizará un algoritmo de clasificación externo para minimizar el número de accesos a la memoria externa.

Asuntos relacionados

Entre los problemas cercanos a la ordenación, podemos mencionar el ordenamiento parcial  (in) , que consiste, por fijo, en ordenar los elementos más pequeños, o el problema de selección , que consiste en encontrar el -ésimo elemento más pequeño de la entrada. Si bien ordenar la entrada completa puede resolver estos problemas, existen soluciones más sutiles y menos costosas. Este es el caso, por ejemplo, de la selección rápida , que tiene similitudes con la clasificación rápida . k{\ Displaystyle k}k{\ Displaystyle k}k{\ Displaystyle k}

A la inversa, podemos intentar construir algoritmos que mezclen aleatoriamente la entrada que se les da; este es el caso, por ejemplo, de la mezcla Fisher-Yates .

Otro problema es ordenar una matriz que ya está casi ordenada (este es el caso de big data donde los algoritmos convencionales están descalificados). Esto puede rehabilitar algoritmos como la clasificación por inserción .

Historia

La creación de la primera rutina de clasificación se atribuye a Betty Holberton , durante la Segunda Guerra Mundial.

Apéndices

Notas y referencias

1. http://www.site.uottawa.ca/~kiringa/courses10/csi3530/ch13_extsort_csi3530-10.ppt
2. http://www.umiacs.umd.edu/research/EXPAR/papers/3670.html
3. Podemos hacer que el ordenamiento por mezcla una especie en su lugar y siempre en , pero el algoritmo hace más copias y es más complicado de programarO(noIniciar sesión⁡no){\ Displaystyle O (n \ log n)}
4. Conozca a los programadores de ENIAC, los pioneros de la industria del software , intel.fr, junio de 2016

Bibliografía

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein ( traducción del  inglés), Algoritmos  : Conferencia con ejercicios 957 y 158 problemas , Dunod ,2010[ detalle de la edición ]
• Christine Froidevaux , Marie-Claude Gaudel y Michèle Soria , Tipos de datos y algoritmos , McGraw-Hill,1990, 577  p. ( ISBN  978-2-7042-1217-0 , aviso BnF n o  FRBNF35070753 , leer en línea ) , cap.  dieciséis

enlaces externos

• Tesis de síntesis sobre algoritmos de clasificación
• Archivo sobre algoritmos de clasificación y su complejidad (e implementación en varios idiomas)
• Ilustración dinámica de varios tipos (requiere Java)
• (es) Ilustración dinámica de varios tipos
• (es) "  Visualización de algoritmos de clasificación  " , visualización de diferentes tipos utilizando colores
• En el sitio de Interstices, documento sobre los algoritmos de clasificación con un subprograma de Java

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">