Orden de ciclo - Cycle sort

Orden de ciclo
	Ejemplo de clasificación cíclica ordenando una lista de números aleatorios.
Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	Θ ( n 2 )
Rendimiento en el mejor de los casos	Θ ( n 2 )
Rendimiento medio	Θ ( n 2 )
Complejidad espacial en el peor de los casos	Θ ( n ) total, Θ ( 1 ) auxiliar

Ciclo especie es una, en el lugar inestable algoritmo de ordenación , una especie de comparación que es teóricamente óptimo en términos del número total de escrituras en el original conjunto , a diferencia de cualquier otro en el lugar algoritmo de ordenación. Se basa en la idea de que la permutación que se va a clasificar 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 el número mínimo de sobrescrituras necesarias para una ordenación in situ completa.

Minimizar el número de escrituras es útil cuando realizar escrituras en un gran conjunto de datos es muy costoso, como con 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 ocurrirá en la lista ordenada simplemente contando el número de elementos en la lista completa que son más pequeños que . Ahora ${\ Displaystyle a}$ ${\ Displaystyle a}$

Si el elemento ya está en la posición correcta, no haga nada.
Si no es así, lo escribiremos en la posición deseada. Esa posición está habitada por un elemento b 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 a . Esto completa un ciclo.

Ciclo de desplazamiento para la lista "bdeac", al cambiar 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 no está ya 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, se deben abordar dos cuestiones:

Al calcular las posiciones correctas, debemos asegurarnos de no contar dos veces el primer elemento del ciclo.
Si hay elementos duplicados presentes, podríamos intentar mover un elemento a a su posición correcta, que ya está habitada por un a . Simplemente intercambiarlos haría que el algoritmo se ciclara indefinidamente. En cambio, tenemos que insertar el elemento después de cualquiera de sus duplicados .

La siguiente implementación de Python realiza una ordenación cíclica en una matriz, contando el número de escrituras en esa matriz que fueron necesarias para ordenarla.

def cycle_sort(array) -> int:
    """Sort an array in place and return the number of writes."""
    writes = 0

    # Loop through the array to find cycles to rotate.
    for cycle_start in range(0, len(array) - 1):
        item = array[cycle_start]

        # Find where to put the item.
        pos = cycle_start
        for i in range(cycle_start + 1, len(array)):
            if array[i] < item:
                pos += 1

        # If the item is already there, this is not a cycle.
        if pos == cycle_start:
            continue

        # Otherwise, put the item there or right after any duplicates.
        while item == array[pos]:
            pos += 1

        array[pos], item = item, array[pos]
        writes += 1

        # Rotate the rest of the cycle.
        while pos != cycle_start:
            # Find where to put the item.
            pos = cycle_start
            for i in range(cycle_start + 1, len(array)):
                if array[i] < item:
                    pos += 1

            # Put the item there or right after any duplicates.
            while item == array[pos]:
                pos += 1
            array[pos], item = item, array[pos]
            writes += 1

    return writes

Optimizaciones específicas de la situación

Cuando la matriz contiene solo duplicados de un número relativamente pequeño 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 Θ ( n ² ) tiempo a Θ ( n + k ) tiempo , donde k es el número total de hashes. La matriz termina ordenada en el orden de los hash, 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, cree 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 una búsqueda de tabla de suma acumulativa y hash de tiempo constante en lugar de una búsqueda lineal .

Referencias

enlaces externos

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

Languages

In other projects