Cyclic Sort

Introduction

Cyclic Sort is a in-place, unstable sorting algorithm designed specifically for problems where the input array contains numbers in a range from 1 to 𝑛, with 𝑛 being the size of the array. The algorithm works by placing each element at its correct position in a single traversal.

How Cyclic Sort Works?

Initialize an index variable `i` to 0.

Set i = 0.

Loop until `i` is less than the size of the array

Calculate the correct position for the current element as idx = arr[i] - 1.
Check if the element at arr[i] is not at its correct position:
- If arr[i] != arr[idx], swap the elements at positions i and idx.
If arr[i] == arr[idx], move to the next element by incrementing i.

Repeat the above process until the entire array is traversed.

Implementation of Cyclic Sort

// cyclicsort.cpp
#include<iostream>
#include<vector>
using namespace std;
void cycleSort(vector<int> &arr){
    int i=0;
    while(i<arr.size()){
        int idx=arr[i]-1;
        if(arr[i]!=arr[idx]){
           swap(arr[i],arr[idx]);
        }
        else {
            i++;
        }
    }
}
int main(){
    vector<int>arr{3,5,2,1,4};
    cycleSort(arr);
    for(int &ele:arr){
        cout<<ele<<" ";
    }
}

#cycleSort.py
def cycleSort (arr):
    i=0
    while(i<len(arr)):
        idx=arr[i]-1
        if(arr[i]!=arr[idx]):
            arr[i],arr[idx]=arr[idx],arr[i]
        else:
            i=i+1
                     
arr=[3,5,1,2,4]
cycleSort(arr)
for ele in arr:
    print(ele)

function cycleSort(arr) {
    let i = 0;
    while(i < arr.length) {
        const idx = arr[i] - 1;
        if(arr[i] !== arr[idx]) {
            [arr[i], arr[idx]] = [arr[idx], arr[i]]; // ES6 swap
        } else {
            i++;
        }
    }
}

const arr = [3, 5, 1, 2, 4];
cycleSort(arr);
arr.forEach(ele => console.log(ele));

Time Complexity

Best Case: When the array is already sorted.
- The loop iterates through all elements exactly once without performing any swaps.
- Time Complexity : O(n)
Average Case: When the array elements are randomly shuffled.
- The loop iterates through all elements and places them into their correct position by swapping.
- Time Complexity : O(n)
Best Case: When the array is in reverse order.
- Every element is traversed and placed in its correct position, requiring at most 𝑂(𝑛) comparisons and swaps.
- Time Complexity : O(n)

Space Complexity

Since it is an in-place sorting algorithm, no auxiliary space is required.
Space Complexity : O(1)

Cyclic Sort

On this page