Ordenar por ciclos

Algoritmo de clasificación de comparación

La clasificación cíclica es un algoritmo de clasificación inestable e in situ , una clasificación de comparación que es teóricamente óptima en términos del número total de escrituras en la matriz original , a diferencia de cualquier otro algoritmo de clasificación in situ. Se basa en la idea de que la permutación que se va a ordenar se puede factorizar en ciclos , que se pueden rotar individualmente para dar un resultado ordenado.

A diferencia de casi cualquier otro tipo, los elementos nunca se escriben en otra parte de la matriz simplemente para apartarlos del camino de la acción. Cada valor se escribe cero veces, si ya está en su posición correcta, o se escribe una vez en su posición correcta. Esto coincide con la cantidad mínima de sobrescrituras necesarias para una clasificación in situ completa.

Minimizar la cantidad de escrituras es útil cuando escribir en un conjunto de datos enorme es muy costoso, como ocurre con las EEPROM como la memoria Flash , donde cada escritura reduce la vida útil de la memoria .

Algoritmo

Para ilustrar la idea de ordenación cíclica, considere una lista con elementos distintos. Dado un elemento , podemos encontrar el índice en el que aparecerá en la lista ordenada simplemente contando el número de elementos en la lista completa que son menores que . Ahora ${\displaystyle x}$ ${\displaystyle x}$

1. Si el elemento ya está en la posición correcta, no hagas nada.
2. Si no es así, lo escribiremos en la posición prevista. Esa posición la habita un elemento diferente , que luego tenemos que mover a su posición correcta. Este proceso de desplazar elementos a sus posiciones correctas continúa hasta que un elemento se mueve a la posición original de . Esto completa un ciclo. ${\displaystyle y}$ ${\displaystyle x}$

Ciclo de desplazamiento de la lista "bdeac", al desplazar la primera letra b a su posición correcta:

Repetir este proceso para cada elemento ordena la lista, con una sola operación de escritura si y solo si un elemento aún no está en su posición correcta. Si bien calcular las posiciones correctas lleva tiempo para cada elemento, lo que da como resultado un algoritmo de tiempo cuadrático, el número de operaciones de escritura se minimiza. ${\displaystyle O(n)}$

Implementación

Para crear una implementación funcional a partir del esquema anterior, es necesario abordar dos cuestiones:

1. Al calcular las posiciones correctas, debemos asegurarnos de no contar dos veces el primer elemento del ciclo.
2. Si hay elementos duplicados presentes, cuando intentamos mover un elemento a su posición correcta, es posible que esa posición ya esté ocupada por un archivo . Simplemente intercambiarlos haría que el algoritmo funcionara en ciclos indefinidamente. En cambio, tenemos que insertar el elemento después de cualquiera de sus duplicados . ${\displaystyle x}$ ${\displaystyle x}$

La siguiente implementación de Python ^{[1] [ referencia circular ]} realiza una ordenación cíclica en una matriz, contando el número de escrituras en esa matriz que fueron necesarias para ordenarla.

Pitón

def  sort_ciclo ( matriz )  ->  int : """Ordena una matriz en su lugar y devuelve el número de escrituras.""" escribe  =  0 # Recorre la matriz para encontrar ciclos para rotar. # Tenga en cuenta que el último elemento ya estará ordenado después de los primeros n-1 ciclos. para  Cycle_start  en el  rango ( 0 ,  len ( matriz )  -  1 ): elemento  =  matriz [ ciclo_inicio ] # Encuentra dónde colocar el artículo. pos  =  inicio_ciclo para  i  en  el rango ( cycle_start  +  1 ,  len ( matriz )): si  matriz [ i ]  <  elemento : posición  +=  1 # Si el artículo ya está ahí, esto no es un ciclo. si  pos  ==  ciclo_inicio : continuar # De lo contrario, coloque el elemento allí o justo después de cualquier duplicado. mientras que  elemento  ==  matriz [ pos ]: posición  +=  1 matriz [ pos ],  elemento  =  elemento ,  matriz [ pos ] escribe  +=  1 # Girar el resto del ciclo. mientras  pos  ! =  inicio_ciclo : # Encuentra dónde colocar el artículo. pos  =  inicio_ciclo para  i  en  el rango ( cycle_start  +  1 ,  len ( matriz )): si  matriz [ i ]  <  elemento : posición  +=  1 # Coloque el elemento allí o justo después de cualquier duplicado. mientras que  elemento  ==  matriz [ pos ]: posición  +=  1 matriz [ pos ],  elemento  =  elemento ,  matriz [ pos ] escribe  +=  1 volver  escribe

La siguiente implementación escrita en C++ simplemente realiza una clasificación cíclica de matrices.

plantilla <nombretipotipo_array>​​​  void Cycle_sort ( type_array * Array , int array_size )    {para ( int ciclo_inicio = 0 ; ciclo_inicio < array_size - 1 ; ciclo_inicio ++ )          {type_array elemento = Matriz [ cycle_start ];   int pos = inicio_ciclo ;   para ( int i = inicio_ciclo + 1 ; i < tamaño_matriz ; i ++ )          si ( matriz [ i ] < elemento )   posición += 1 ;  si ( pos == inicio_ciclo )   continuar ;mientras ( elemento == Matriz [ pos ])   posición += 1 ;  intercambiar ( matriz [ pos ], elemento ); mientras ( pos ! = inicio_ciclo )   {pos = inicio_ciclo ;  para ( int i = inicio_ciclo + 1 ; i < tamaño_matriz ; i ++ )          si ( matriz [ i ] < elemento )   posición += 1 ;  mientras ( elemento == Matriz [ pos ])   posición += 1 ;  intercambiar ( matriz [ pos ], elemento ); }}}

Optimizaciones específicas de la situación

Cuando la matriz contiene solo duplicados de una cantidad relativamente pequeña de elementos, una función hash perfecta de tiempo constante puede acelerar enormemente la búsqueda de dónde colocar un elemento ¹ , cambiando la clasificación de tiempo Θ( n ² ) a Θ( n + k ). tiempo, donde k es el número total de hashes. La matriz termina ordenada en el orden de los hashes, por lo que es importante elegir una función hash que le proporcione el orden correcto.

Antes de ordenar, cree un histograma , ordenado por hash, contando el número de apariciones de cada hash en la matriz. Luego crea una tabla con la suma acumulada de cada entrada en el histograma. La tabla de suma acumulativa contendrá la posición en la matriz de cada elemento. El lugar adecuado de los elementos se puede encontrar mediante un hash de tiempo constante y una búsqueda en la tabla de suma acumulativa en lugar de una búsqueda lineal .

Referencias

1. Sr:Ciklično sortiranje#Algoritam

enlaces externos

^ "Clasificación cíclica: un método de clasificación lineal", The Computer Journal (1990) 33 (4): 365-367.

• Fuente original de la variante sin restricciones.
• Cyclesort: un pequeño y curioso algoritmo de clasificación