Cycle Sort Algorithm
The Cycle Sort Algorithm is a unique, in-place, and comparison-based sorting algorithm that is designed to minimize the number of writes to the input array. It operates on the principle of iterating through the elements of the array and positioning them at their correct location, one element at a time. Cycle Sort is particularly useful in situations where writes are expensive, such as with flash memory, because it minimizes the number of writes required to sort the data.
The algorithm works by first identifying cycles within the array, where a cycle is a sequence of elements that are out of place, and each element in the cycle needs to be moved to its correct position. For each cycle, the algorithm swaps the elements in the cycle until they are in their correct positions. The process is repeated by iterating through the array and finding the next cycle until all elements are in their correct positions. While Cycle Sort is not the most efficient sorting algorithm in terms of time complexity (with a worst-case time complexity of O(n^2)), its primary advantage lies in minimizing the number of writes to the input array, making it a suitable choice for specific applications.
// Sorting of array list using cycle sort
#include <stdio.h>
#include <stdlib.h>
// Displays the array, passed to this method
void display(int arr[], int n){
int i;
for(i = 0; i < n; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
// Swap function to swap two values
void swap(int *first, int *second){
int temp = *first;
*first = *second;
*second = temp;
}
// 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++;
}
}
}
}
// Driver program to test above function
int main()
{
int n; // Size of array elements
printf("Enter size of array:\n");
scanf("%d", &n); // E.g. 8
printf("Enter the elements of the array\n");
int i;
int arr[n];
for(i = 0; i < n; i++){
scanf("%d", &arr[i] );
}
printf("Original array: ");
display(arr, n);
cycleSort(arr, n);
printf("Sorted array: ");
display(arr, n);
return 0;
}
