Cycle Sort Algorithm
Cycle Sort is unstable, in-place comparison sorting algorithm designed to minimize the number of writes to the array. It is useful when write operations are expensive (for example, on EEPROM or flash memory).
How it works?
The algorithm places each element directly into its correct position by:
- Finding the position where the current element belongs.
- Swapping it into that position.
- Repeating the process for the displaced element until the cycle is complete.
Each cycle moves multiple elements into their correct positions with the minimum possible number of writes.
Algorithm
Assume an array arr[] contains n elements.
1. Start from the first element. 2. Count the number of elements smaller than the current element to determine its correct position in the sorted array. 3. If the element is already in its correct position, move to the next element. 4. Otherwise, place the element at its correct position and pick up the displaced element. 5. Repeat the process for the displaced element until the cycle is completed and the starting position is reached again. 6. Continue the same procedure for all remaining elements.
Each complete rotation of elements forms a cycle, which gives the algorithm its name.
Example: Cycle Sort
1. Outer Loop Start: Index 0: Initial array: {30, 20, 10, 40, 60, 50}.
Current Element: 30 at index 0.
Find Sorted Position: Count how many elements in the array are strictly smaller than 30 (10, 20 -> 2 elements). So, 30 belongs at index 2.
Action: 30 is not at index 2. We save the element currently at index 2 (10) into item and write 30 into index 2.
Array becomes: {30, 20, 30, 40, 60, 50} (item = 10)
Continue Cycle for item = 10:
- Count elements smaller than 10 -> 0 elements. So, 10 belongs at index 0.
- Write 10 into index 0.
- Array becomes: {10, 20, 30, 40, 60, 50}
Cycle 1 Complete.
2. Outer Loop: Index 1: Array: {10, 20, 30, 40, 60, 50}.
Current Element: 20 at index 1.
Find Sorted Position: Elements smaller than 20 -> 1 element (10). So, 20 belongs at index 1.
Action: 20 is already in its correct place. Skip.
3. Outer Loop: Index 2: Array: {10, 20, 30, 40, 60, 50}.
Current element: 30 at index 2.
Find sorted position: Elements smaller than 30 -> 2 elements (10, 20). So, 30 belongs at index 2.
Action: 30 is already in its correct place. Skip.
4. Outer Loop: Index 3: Array: {10, 20, 30, 40, 60, 50}.
Current element: 40 at index 3.
Find sorted position: Elements smaller than 40 -> 3 elements (10, 20, 30). So, 40 belongs at index 3.
Action: 40 is already in its correct place. Skip.
5. Outer Loop Start: Index 4: Array: {10, 20, 30, 40, 60, 50}.
Current element: 60 at index 4.
Find sorted position: Count elements smaller than 60 -> 5 elements (10, 20, 30, 40, 50). So, 60 belongs at index 5.
Action: 60 is not at index 5. We save the element at index 5 (50) into item and write 60 into index 5.
Array becomes: {10, 20, 30, 40, 60, 60} (item = 50)
Continue Cycle for item = 50:
- Count elements smaller than 50 -> 4 elements. So, 50 belongs at index 4.
- Write 50 into index 4.
- Array becomes: {10, 20, 30, 40, 50, 60}
Cycle 2 Complete.
6. Outer Loop: Index 5: Array: {10, 20, 30, 40, 50, 60}.
Current element: 60 at index 5 (last element).
Action: Reached the end of the array. Sort complete.
Implementation of Cycle Sort in Python/ Java/ C/ C++/ C#
Python
def cycle_sort(arr):
n = len(arr)
for start in range(n - 1):
element = arr[start]
# Find the correct position of the current element
pos = start
for i in range(start + 1, n):
if arr[i] < element:
pos += 1
# Element is already in the correct position
if pos == start:
continue
# Handle duplicate elements
while element == arr[pos]:
pos += 1
# Put the element into its correct position
if pos != start:
arr[pos], element = element, arr[pos]
# Rotate the remaining elements in the cycle
while pos != start:
pos = start
for i in range(start + 1, n):
if arr[i] < element:
pos += 1
while element == arr[pos]:
pos += 1
# Check before swapping to avoid unnecessary work
if element != arr[pos]:
arr[pos], element = element, arr[pos]
arr = [30, 20, 10, 40, 60, 50]
print("Before sorting: ")
print(arr)
cycle_sort(arr)
print("After applying Cycle Sort:")
print(arr)
Java
class Main {
/*function to implement to cycle sort*/
static void cycleSort(int a[], int n) {
int start, element, pos, temp, i;
/*Loop to traverse the array elements and place them on the correct
position*/
for (start = 0; start <= n - 2; start++) {
element = a[start];
/*position to place the element*/
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos++;
if (pos == start) /*if the element is at exact position*/
continue;
while (element == a[pos])
pos += 1;
if (pos != start) /*put element at its exact position*/ {
//swap(element, a[pos]);
temp = element;
element = a[pos];
a[pos] = temp;
}
/*Rotate rest of the elements*/
while (pos != start) {
pos = start;
/*find position to put the element*/
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos += 1;
/*Ignore duplicate elements*/
while (element == a[pos])
pos += 1;
/*put element to its correct position*/
if (element != a[pos]) {
temp = element;
element = a[pos];
a[pos] = temp;
}
}
}
}
static void print(int a[], int n) /*function to print array elements*/ {
int i;
for(i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
}
public static void main(String args[]) {
int[] a = {30, 20, 10, 40, 60, 50};
int n = a.length;
System.out.print("Before sorting: ");
print(a, n);
cycleSort(a, n);
System.out.print("\nAfter applying Cycle Sort: ");
print(a, n);
}
}
C
#include/*function to implement to cycle sort*/ void cycleSort(int a[], int n) { int start, element, pos, temp, i; /*Loop to traverse the array elements and place them on the correct position*/ for (start = 0; start <= n - 2; start++) { element = a[start]; /*position to place the element*/ pos = start; for (i = start + 1; i < n; i++) if (a[i] < element) pos++; if (pos == start) /*if the element is at exact position*/ continue; while (element == a[pos]) pos += 1; if (pos != start) /*put element at its exact position*/ { //swap(element, a[pos]); temp = element; element = a[pos]; a[pos] = temp; } /*Rotate rest of the elements*/ while (pos != start) { pos = start; /*find position to put the element*/ for (i = start + 1; i < n; i++) if (a[i] < element) pos += 1; /*Ignore duplicate elements*/ while (element == a[pos]) pos += 1; /*put element to its correct position*/ if (element != a[pos]) { temp = element; element = a[pos]; a[pos] = temp; } } } } void print(int a[], int n) /*function to print array elements*/ { int i; for(i = 0; i < n; i++) { printf("%d ",a[i]); } } int main() { int a[] = {30, 20, 10, 40, 60, 50}; int n = sizeof(a) / sizeof(a[0]); printf("Before sorting: "); print(a, n); cycleSort(a, n); printf("\n After applying Cycle Sort: "); print(a, n); return 0; }
C++
#includeusing namespace std; /*function to implement to cycle sort*/ void cycleSort(int a[], int n) { int start, element, pos, temp, i; /*Loop to traverse the array elements and place them on the correct position*/ for (start = 0; start <= n - 2; start++) { element = a[start]; /*position to place the element*/ pos = start; for (i = start + 1; i < n; i++) if (a[i] < element) pos++; if (pos == start) /*if the element is at exact position*/ continue; while (element == a[pos]) pos += 1; if (pos != start) /*put element at its exact position*/ { //swap(element, a[pos]); temp = element; element = a[pos]; a[pos] = temp; } /*Rotate rest of the elements*/ while (pos != start) { pos = start; /*find position to put the element*/ for (i = start + 1; i < n; i++) if (a[i] < element) pos += 1; /*Ignore duplicate elements*/ while (element == a[pos]) pos += 1; /*put element to its correct position*/ if (element != a[pos]) { temp = element; element = a[pos]; a[pos] = temp; } } } } void print(int a[], int n) /*function to print array elements*/ { int i; for(i = 0; i < n; i++) { cout<
C#
using System;
class CycleSort {
/*function to implement to cycle sort*/
static void cycleSort(int[] a, int n) {
int start, element, pos, temp, i;
/*Loop to traverse the array elements and place them on the correct position*/
for (start = 0; start <= n - 2; start++) {
element = a[start];
/*position to place the element*/
pos = start;
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos++;
if (pos == start) /*if the element is at exact position*/
continue;
while (element == a[pos])
pos += 1;
if (pos != start) /*put element at its exact position*/ {
//swap(element, a[pos]);
temp = element;
element = a[pos];
a[pos] = temp;
}
/*Rotate rest of the elements*/
while (pos != start) {
pos = start;
/*find position to put the element*/
for (i = start + 1; i < n; i++)
if (a[i] < element)
pos += 1;
/*Ignore duplicate elements*/
while (element == a[pos])
pos += 1;
/*put element to its correct position*/
if (element != a[pos]) {
temp = element;
element = a[pos];
a[pos] = temp;
}
}
}
}
static void print(int[] a, int n) /*function to print array elements*/ {
int i;
for(i = 0; i < n; i++) {
Console.Write(a[i] + " ");
}
}
static void Main() {
int[] a = {30, 20, 10, 40, 60, 50};
int n = a.Length;
Console.Write("Before sorting: ");
print(a, n);
cycleSort(a, n);
Console.Write("\nAfter applying Cycle Sort: ");
print(a, n);
}
}
Output:
Before sorting: 30 20 10 40 60 50 After applying Cycle Sort: 10 20 30 40 50 60
Complexity Analysis
Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n²) |
| Average Case | O(n²) |
| Worst Case | O(n²) |
Even if the array is already sorted, Cycle Sort must count the number of smaller elements for each position to determine whether an element is in its correct location. Therefore, the algorithm performs approximately the same number of comparisons in all cases, resulting in O(n²) time complexity.
Space Complexity
| Property | Value |
|---|---|
| Auxiliary Space | O(1) |
| Stable | No |
| In-place | Yes |
Cycle Sort uses only a few extra variables regardless of the input size, so its auxiliary space complexity is O(1).
Applications of Cycle Sort
- Situations where minimizing write operations is important.
- Flash memory and EEPROM-based storage systems.
- Memory-constrained environments.
- Finding the minimum number of swaps required to sort an array (conceptually related to cycle decomposition).
Subscribe to Tpoint Tech
We request you to subscribe our newsletter for upcoming updates.
We deliver comprehensive tutorials, interview question-answers, MCQs, study materials on leading programming languages and web technologies like Data Science, MEAN/MERN full stack development, Python, Java, C++, C, HTML, React, Angular, PHP and much more to support your learning and career growth.
Contact info
G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India
Follow us
