Ordenación cíclica

Algoritmo de ordenación por comparación

La ordenación por ciclos es un algoritmo de ordenación inestable y local , una ordenación por comparación que teóricamente es óptima en términos de la cantidad total de escrituras en la matriz original , a diferencia de cualquier otro algoritmo de ordenación local. 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 otra clasificación, los elementos nunca se escriben en otro lugar de la matriz simplemente para sacarlos 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 completar una clasificación en el lugar.

Minimizar la cantidad de escrituras es útil cuando escribir en un conjunto de datos enorme es muy costoso, como sucede con las EEPROM como la memoria Flash , donde cada escritura reduce la vida útil de la memoria . ^{[ cita requerida ]}

Algoritmo

Para ilustrar la idea de la 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 la cantidad de elementos en toda la lista que sean menores que . Ahora ${\displaystyle x}$ ${\displaystyle x}$

1. Si el elemento ya está en la posición correcta, no haga nada.
2. Si no es así, lo escribiremos en la posición deseada. Esa posición está ocupada por un elemento diferente , que luego tenemos que mover a su posición correcta. Este proceso de desplazamiento de 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 para la lista "bdeac", al desplazar la primera letra b a su posición correcta:

Al repetir este proceso para cada elemento, se ordena la lista, con una única operación de escritura si y solo si un elemento no está ya en su posición correcta. Si bien calcular las posiciones correctas lleva tiempo para cada elemento individual, lo que da como resultado un algoritmo de tiempo cuadrático, se minimiza la cantidad de operaciones de escritura. ${\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, cuando intentamos mover un elemento a su posición correcta, es posible que esa posición ya esté ocupada por un . Simplemente intercambiarlos haría que el algoritmo se repita 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 la cantidad de escrituras en esa matriz que fueron necesarias para ordenarla.

Pitón

def  cycle_sort ( 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  rango ( 0 ,  len ( matriz )  -  1 ): elemento  =  matriz [ inicio_ciclo ] # Encuentra dónde colocar el artículo. pos  =  inicio_ciclo para  i  en  rango ( cycle_start  +  1 ,  len ( array )): si  matriz [ i ]  <  elemento : posición  +=  1 # Si el artículo ya está allí, esto no es un ciclo. si  pos  ==  cycle_start : continuar # De lo contrario, coloque el elemento allí o justo después de cualquier duplicado. mientras  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  rango ( cycle_start  +  1 ,  len ( array )): si  matriz [ i ]  <  elemento : posición  +=  1 # Coloque el artículo allí o justo después de cualquier duplicado. mientras  elemento  ==  matriz [ pos ]: posición  +=  1 matriz [ pos ],  elemento  =  elemento ,  matriz [ pos ] escribe  +=  1 devuelve  escrituras

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

plantilla < typename type_array >  void cycle_sort ( tipo_matriz * Matriz , int tamaño_matriz )    {para ( int inicio_ciclo = 0 ; inicio_ciclo < tamaño_matriz - 1 ; inicio_ciclo ++ )          {tipo_matriz elemento = Matriz [ inicio_ciclo ];   int pos = inicio_ciclo ;   para ( int i = inicio_ciclo + 1 ; i < tamaño_matriz ; i ++ )          si ( Matriz [ i ] < elemento )   pos += 1 ;  si ( pos == inicio_ciclo )   continuar ;mientras ( elemento == Matriz [ pos ])   pos += 1 ;  std :: swap ( Array [ pos ], elemento ); mientras ( pos != inicio_ciclo )   {pos = inicio_ciclo ;  para ( int i = inicio_ciclo + 1 ; i < tamaño_matriz ; i ++ )          si ( Matriz [ i ] < elemento )   pos += 1 ;  mientras ( elemento == Matriz [ pos ])   pos += 1 ;  std :: swap ( Array [ pos ], elemento ); }}}

Optimizaciones específicas para cada 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 el orden de tiempo Θ( n ² ) a tiempo Θ( n + k ), donde k es la cantidad 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 brinde el orden correcto.

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

Referencias

1. Sr:Ciklično sortiranje#Algoritam

Enlaces externos

^ "Cycle-Sort: 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