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[] = {2, 4, 5, 1, 3}
CPP
// 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;
}
Java
// Java program to implement cycle sort
import java.util.*;
import java.lang.*;
class GFG {
// Function sort the array using Cycle sort
public static 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) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
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]) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
writes++;
}
}
}
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 1, 8, 3, 9, 10, 10, 2, 4 };
int n = arr.length;
cycleSort(arr, n);
System.out.println("After sort : ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// Code Contributed by Mohit Gupta_OMG <(0_o)>
Python3
# 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)>
C#
// C# program to implement cycle sort
using System;
class GFG {
// Function sort the array using Cycle sort
public static 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) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
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]) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
writes++;
}
}
}
}
// Driver program to test above function
public static void Main()
{
int[] arr = { 1, 8, 3, 9, 10, 10, 2, 4 };
int n = arr.Length;
// Function calling
cycleSort(arr, n);
Console.Write("After sort : ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Nitin Mittal
Javascript
<script>
// Javascript program to implement cycle sort
// Function sort the array using Cycle sort
function cycleSort(arr, n)
{
// count number of memory writes
let writes = 0;
// traverse array elements and put it to on
// the right place
for (let cycle_start = 0; cycle_start <= n - 2; cycle_start++)
{
// initialize item as starting point
let item = arr[cycle_start];
// Find position where we put the item. We basically
// count all smaller elements on right side of item.
let pos = cycle_start;
for (let 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)
{
let temp = item;
item = arr[pos];
arr[pos] = temp;
writes++;
}
// Rotate rest of the cycle
while (pos != cycle_start)
{
pos = cycle_start;
// Find position where we put the element
for (let 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]) {
let temp = item;
item = arr[pos];
arr[pos] = temp;
writes++;
}
}
}
}
// Driver code
let arr = [ 1, 8, 3, 9, 10, 10, 2, 4 ];
let n = arr.length;
cycleSort(arr, n);
document.write("After sort : " + "<br/>");
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by susmitakundugoaldanga.
</script>
C++
#include <iostream>
using namespace std;
void cyclicSort(int arr[], int n){
int i = 0;
while(i < n)
{
// as array is of 1 based indexing so the
// correct position or index number of each
// element is element-1 i.e. 1 will be at 0th
// index similarly 2 correct index will 1 so
// on...
int correct = arr[i] - 1 ;
if(arr[i] != arr[correct]){
// if array element should be lesser than
// size and array element should not be at
// its correct position then only swap with
// its correct positioin or index value
swap(arr[i], arr[correct]) ;
}else{
// if element is at its correct position
// just increment i and check for remaining
// array elements
i++ ;
}
}
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = { 3, 2, 4, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Before sorting array: \n";
printArray(arr, n);
cyclicSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
Java
// java program to check implement cycle sort
import java.util.*;
public class MissingNumber {
public static void main(String[] args)
{
int[] arr = { 3, 2, 4, 5, 1 };
int n = arr.length;
System.out.println("Before sort :");
System.out.println(Arrays.toString(arr));
CycleSort(arr, n);
}
static void CycleSort(int[] arr, int n)
{
int i = 0;
while (i < n) {
// as array is of 1 based indexing so the
// correct position or index number of each
// element is element-1 i.e. 1 will be at 0th
// index similarly 2 correct index will 1 so
// on...
int correctpos = arr[i] - 1;
if (arr[i] < n && arr[i] != arr[correctpos]) {
// if array element should be lesser than
// size and array element should not be at
// its correct position then only swap with
// its correct positioin or index value
swap(arr, i, correctpos);
}
else {
// if element is at its correct position
// just increment i and check for remaining
// array elements
i++;
}
}
System.out.println("After sort : ");
System.out.print(Arrays.toString(arr));
}
static void swap(int[] arr, int i, int correctpos)
{
// swap elements with their correct indexes
int temp = arr[i];
arr[i] = arr[correctpos];
arr[correctpos] = temp;
}
}
// this code is contributed by devendra solunke
C#
using System;
public class GFG {
static public void Main()
{
// Code
int[] arr = { 3, 2, 4, 5, 1 };
int n = arr.Length;
Console.Write("Before sort : ");
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
CycleSort(arr, n);
}
static void CycleSort(int[] arr, int n)
{
int i = 0;
while (i < n) {
// as array is of 1 based indexing so the
// correct position or index number of each
// element is element-1 i.e. 1 will be at 0th
// index similarly 2 correct index will 1 so
// on...
int correctpos = arr[i] - 1;
if (arr[i] < n && arr[i] != arr[correctpos]) {
// if array element should be lesser than
// size and array element should not be at
// its correct position then only swap with
// its correct positioin or index value
swap(arr, i, correctpos);
}
else {
// if element is at its correct position
// just increment i and check for remaining
// array elements
i++;
}
}
Console.Write("After sort : ");
for (int index = 0; index < n; i++)
Console.Write(arr[index] + " ");
}
static void swap(int[] arr, int i, int correctpos)
{
// swap elements with their correct indexes
int temp = arr[i];
arr[i] = arr[correctpos];
arr[correctpos] = temp;
}
}
// this code is contributed by devendra solunke
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