Clasificación estable (estable) : clasificación , que no cambia el orden relativo de los elementos ordenados que tienen las mismas claves, mediante el cual se produce la clasificación.
La estabilidad es una característica muy importante de un algoritmo de clasificación, pero, sin embargo, casi siempre se puede lograr alargando las claves originales con información adicional sobre su orden original. A pesar de la aparente necesidad implícita en el nombre, la estabilidad no es en absoluto necesaria para la clasificación correcta y la mayoría de las veces no se observa, ya que casi siempre se requiere memoria y tiempo adicionales para asegurarla.
Al ordenar registros de la forma [apellido, nombre, patronímico] por apellido, los valores clave para Ivanov Sergey e Ivanov Ivan serán los mismos, por lo que la clasificación estable no intercambiará a Sergey e Ivan ( Python 3 , timsort sort [1] ):
registros = [ { 'apellido' : 'Ivanov' , 'nombre' : 'Sergey' , 'patronímico' : 'Mikhailovich' ,}, { 'apellido' : 'Ivanov' , 'nombre' : 'Ivan' , ' patronímico' : 'Borisovich' ,}, { 'apellido' : 'Abramov' , 'nombre' : 'Yuri' , 'patronímico' : 'Petrovich' ,}, ] registros . sort ( key = lambda x : x [ 'last name' ]) # sort by key "last name" for r in records : print ( ' %-12s %-12s %-12s ' % ( r [ 'last name' ] , r [ 'nombre de pila' ], r [ 'patronímico' ]))Como resultado, los registros se ordenarán solo por apellido, manteniendo el orden original entre los registros con el mismo apellido:
Abramov Yuri Petrovich Ivanov Serguéi Mijáilovich Ivanov Iván BorisovichLa clasificación, que es el principal elemento de costo de la transformación de Burroughs-Wheeler , debe ser robusta.
A continuación, se encuentran descripciones de algoritmos de clasificación robustos con un tiempo de ejecución no peor que O( n log 2 n ) (excepto en los peores casos en el algoritmo que usa partición estable). En todo pseudocódigo, un par de barras // significa un comentario al final de la línea, como en C++.
Con este algoritmo de clasificación, la matriz inicial primero se divide recursivamente en partes hasta que cada parte de la matriz contenga uno o cero elementos (la reducción a la mitad se realiza en cada paso de recursividad). Después de eso, las partes resultantes en pares se "fusionan". La complejidad general del algoritmo es O( n log n ), y el algoritmo requiere O( n ) memoria adicional para almacenar las matrices fusionadas.
Este algoritmo es similar al algoritmo quicksort . Al igual que en el algoritmo de clasificación rápida, en este algoritmo la matriz inicial se divide en dos partes: en una, todos los elementos son menores o iguales que algún elemento pivote, y en la otra, son mayores o iguales. Después de eso, las partes separadas de la matriz se ordenan recursivamente de la misma manera. La diferencia entre este algoritmo y el algoritmo de clasificación rápida es que utiliza una partición estable en lugar de una inestable. A continuación se muestra la implementación de este algoritmo en pseudocódigo:
Ordenar(a[1..n]) si (n > 1) entonces N ← a[ 1 ]; m ← ParticiónEstable(a[1..n], N); Ordenar(a[1..m]); Ordenar(a[m+1..n]); ParticiónEstable(a[1..n], N) si ( n > 1 ) entonces metro ← ⌊ n/2 ⌋; m1 ← ParticiónEstable(a[1..m], N); m2 ← m+ParticiónEstable(a[m+1..n], N); Rotar(a[m1..m2], m); retorno(m1 + (m2-m)); más si(a[1] < N) entonces retorno(1); más volver(0)Procedimiento de rotación:
Rotar(a[1..n], m) if( n > m > 1 ) //la matriz tiene al menos dos elementos y el cambio tiene sentido cambio ← min; //número de posiciones a cambiar mcd ← mcd(m-1, n); //MCD es el máximo común divisor para i ← 0 a mcd-1 hacer cabeza ← i+1; headVal ← a[cabeza]; cabeza actual ←; siguiente ← cabezal+cambio; mientras (siguiente ≠ cabeza) hacer a[actual] ← a[siguiente]; actual ← siguiente; siguiente ← siguiente+cambio; si (siguiente> n) siguiente ← siguiente-n; a[actual] ← headVal;Se necesitan operaciones elementales O ( n log n ) para particionar la matriz de manera sostenible . Dado que la "profundidad" del descenso recursivo realizado es O(log n ) en promedio, la complejidad general del algoritmo es O( n log² n ). En este caso, el algoritmo requerirá memoria de pila O(log n ) para realizar la recursión, aunque en el peor de los casos, la complejidad total es O( n ² log n ) y se requiere memoria O( n ).
Todos los algoritmos que se describen a continuación se basan en fusionar matrices ya ordenadas sin usar memoria adicional más allá de la memoria de pila O(log²n ) (esta es la llamada condición de memoria mínima [2] ) y difieren solo en el algoritmo de fusión. El siguiente es el pseudocódigo de los algoritmos (los algoritmos de combinación, el procedimiento de combinación, se proporcionan por separado para cada método):
Ordenar(a[1..n]) si ( n > 1 ) entonces m ← n/2 ; Ordenar(a[1..m]); Ordenar(a[m+1..n]); Fusionar(a[1..n], m); Algoritmo de PrattEn el algoritmo de Pratt, dos elementos α y β se encuentran en matrices ordenadas , que son las medianas de una matriz que consta de elementos de ambas matrices. Entonces todo el arreglo se puede representar como aαbxβy . Después de eso, se lleva a cabo un cambio cíclico de elementos, como resultado de lo cual obtenemos la siguiente secuencia: axβαby . Además, el algoritmo de combinación se repetirá recursivamente para las matrices ax y by.
Fusionar(a[1..n], m) if(m ≠ 1 and m ≠ n) //esta condición significa que el arreglo debe tener al menos 2 elementos if( n-1 > 2 ) //el caso en que hay exactamente dos elementos debe considerarse por separado si ( m-1 > nm ) Límite izquierdo←1; LímiteDerecha←m; while( leftBound < rightBound ) do //buscar medianas en este bucle m1 ← (Límite Izquierdo+Límite Derecho)/2; m2 ← BuscarPrimeraPosición(a[m..n], a[ m1 ]); //implementación del procedimiento FindFirstPosition ver siguiente. párrafo si ( m1 + (m2-m) > n/2 ) entonces límite derecho ← m1-1; más límite izquierdo ← m1+1; Rotar(a[m1..m2], m); Fusionar(a[1..m1+(m2-m)], m1); Fusionar(a[m1+(m2-m)+1..n], m2); más si(a[m] < a[1]) a[m]⟷a[1];Cambiar elementos requiere operaciones de elementos O( n ) y memoria adicional O(1), mientras que encontrar medianas en dos matrices ya ordenadas requiere operaciones de elementos O(log² n ) y memoria adicional O(1). Dado que hay pasos de recursión O(log n ), la complejidad de dicho algoritmo de combinación es O( n log n ), y la complejidad general del algoritmo de clasificación es O( n log² n ). En este caso, el algoritmo requerirá memoria de pila O(log² n ).
Algoritmo sin búsqueda de medianasPuede deshacerse de la búsqueda de medianas en el algoritmo anterior de la siguiente manera. En la mayor de las dos matrices, seleccione el elemento central α (el elemento pivote). A continuación, en la matriz más pequeña, busque la posición de la primera aparición de un elemento mayor o igual que α. Llamémoslo β. Después de eso, los elementos se desplazan cíclicamente, como en el algoritmo de Pratt ( aαbxβy → axβαby ), y las partes obtenidas se fusionan recursivamente. El pseudocódigo del algoritmo de fusión se proporciona a continuación.
Fusionar(a[1..n], m) if(m ≠ 1 and m ≠ n) //esta condición significa que el arreglo debe tener al menos 2 elementos if( n-1 > 2 ) //el caso cuando exactamente dos elementos tienen que ser considerados por separado si ( m-1 > nm ) m1 ← (m+1)/2 ; m2 ← BuscarPrimeraPosición(a[m..n], a[ m1 ]); más m2 ← (n+m)/2 ; m1 ← BuscarÚltimaPosición(a[1..m], a[ m2 ]); Rotar(a[m1..m2], m); Fusionar(a[1..m1+(m2-m)], m1); Fusionar(a[m1+(m2-m)+1..n], m2); más si(un[ m ] < un[ 1 ]) un[ m ]⟷a[ 1 ];Los procedimientos FindFirstPosition y FindLastPosition son casi idénticos al procedimiento de búsqueda binaria:
BuscarPrimeraPosición(a[1..n], x) límite izquierdo ← 1; Límite derecho ← n; actual ← 1; while(LímiteIzquierdo <LímiteDerecho) hacer actual ← ⌊(Límite izquierda+Límite derecha)/2⌋; si (a [ actual ] < x) entonces límite izquierdo ← actual+1 más límite derecho ← actual; retorno (actual); BuscarÚltimaPosición(a[1..n], x) límite izquierdo ← 1; Límite derecho ← n; actual ← 1; while(LímiteIzquierdo <LímiteDerecho) hacer actual ← ⌊(Límite izquierda+Límite derecha)/2⌋; si ( x < a [ actual ] ) entonces límite derecho ← actual; más límite izquierdo ← actual+1 retorno (actual);A diferencia del algoritmo de Pratt, en este algoritmo la partición puede ser sustancialmente desigual. Pero incluso en el peor de los casos, el algoritmo dividirá todo el rango [ a .. y ] en una proporción de 3:1 (si todos los elementos del segundo rango son mayores o menores que el de referencia y ambos rangos tienen el mismo número de elementos). Esto garantiza un número logarítmico de pasos de recurrencia al fusionar cualquier matriz. Por lo tanto, obtenemos que, al igual que en el algoritmo de Pratt, la complejidad del algoritmo de fusión es O( n log n ), la complejidad del algoritmo de clasificación es O( n log² n ) y la memoria requerida es O(log² n ).
Clasificación estable sin memoria adicional en tiempo O ( n log n )| Algoritmos de clasificación | |
|---|---|
| Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
| Intercambio | |
| Elección | |
| inserciones | |
| fusión | |
| sin comparaciones | |
| híbrido | |
| Otro | |
| poco práctico | |