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 anterior 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.
C++
// C++ program to implement cycle sort
#include <iostream>
using namespace std;
// Function sort the array using Cycle sort
void cycleSort (int arr[], int n)
{
// count number of memory writes
int writes = 0;
// traverse array elements and put it to on
// the right place
for (int cycle_start=0; cycle_start<=n-2; cycle_start++)
{
// initialize item as starting point
int item = arr[cycle_start];
// Find position where we put the item. We basically
// count all smaller elements on right side of item.
int pos = cycle_start;
for (int i = cycle_start+1; i<n; i++)
if (arr[i] < item)
pos++;
// If item is already in correct position
if (pos == cycle_start)
continue;
// ignore all duplicate elements
while (item == arr[pos])
pos += 1;
// put the item to it\'s right position
if (pos != cycle_start)
{
swap(item, arr[pos]);
writes++;
}
// Rotate rest of the cycle
while (pos != cycle_start)
{
pos = cycle_start;
// Find position where we put the element
for (int i = cycle_start+1; i<n; i++)
if (arr[i] < item)
pos += 1;
// ignore all duplicate elements
while (item == arr[pos])
pos += 1;
// put the item to it\'s right position
if (item != arr[pos])
{
swap(item, arr[pos]);
writes++;
}
}
}
// Number of memory writes or swaps
// cout << writes << endl ;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 8, 3, 9, 10, 10, 2, 4 };
int n = sizeof(arr)/sizeof(arr[0]);
cycleSort(arr, n) ;
cout << "After sort : " <<endl;
for (int i =0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
Producción:
After sort : 1 2 3 4 8 9 10 10
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar : O(1)
¡ Consulte el artículo completo sobre Cycle Sort para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA