Programa de Python para ordenación cíclica

Cycle sort es un algoritmo de clasificación in situ , un algoritmo de clasificación inestable , una clasificación de comparación que es teóricamente óptima en términos del número total de escrituras en la array original.

• Es óptimo en términos de número de escrituras de memoria. Minimiza la cantidad de escrituras de memoria para ordenar (cada valor se escribe cero veces, si ya está en su posición correcta, o se escribe una vez en su posición correcta).
• Se basa en la idea de que la array a ordenar se puede dividir en ciclos. Los ciclos se pueden visualizar como un gráfico. Tenemos n Nodes y un borde dirigido desde el Node i al Node j si el elemento en el índice i-ésimo debe estar presente en el índice j-ésimo en la array ordenada. Ciclo en arr[] = {4, 5, 2, 1, 5} Ciclo en arr[] = {4, 3, 2, 1}

Consideramos uno por uno todos los ciclos. Primero consideramos el ciclo que incluye el primer elemento. Encontramos la posición correcta del primer elemento, lo colocamos en su posición correcta, digamos j. Consideramos el valor antiguo de arr[j] y encontramos su posición correcta, seguimos haciendo esto hasta que todos los elementos del ciclo actual se colocan en la posición correcta, es decir, no volvemos al punto de inicio del ciclo.

# Python program to implement cycle sort
 
def cycleSort(array):
  writes = 0
   
  # Loop through the array to find cycles to rotate.
  for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]
     
    # Find where to put the item.
    pos = cycleStart
    for i in range(cycleStart + 1, len(array)):
      if array[i] < item:
        pos += 1
     
    # If the item is already there, this is not a cycle.
    if pos == cycleStart:
      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 != cycleStart:
       
      # Find where to put the item.
      pos = cycleStart
      for i in range(cycleStart + 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
   
#  driver code
arr = [1, 8, 3, 9, 10, 10, 2, 4 ]
n = len(arr)
cycleSort(arr)
 
print("After sort : ")
for i in range(0, n) :
    print(arr[i], end = \' \')
 
# Code Contributed by Mohit Gupta_OMG <(0_o)>

Producción:

After sort : 
1 2 3 4 8 9 10 10 

Complejidad de Tiempo : O(n ² )
Espacio Auxiliar : O(1)

¡ Consulte el artículo completo sobre Cycle Sort para obtener más detalles!