Cyclic Sort

An in-place sorting algorithm for a specific range

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?

1

Initialize an index variable `i` to 0.

2

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.
3

Repeat the above process until the entire array is traversed.

Implementation of Insertion 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<<" ";
}
}

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)