cycle sort Algorithm

It works by swapping the value of element by comparing with the index position

Even wondered why Cycle sort and When to use it ?

Note→ if u have to sort numbers staring from 1 to n just use cycle sort

Cycle Sort - Time and Space Complexity

Time Complexity

• Best Case: O(n2)

• Worst Case: O(n2)

• Average Case: O(n2)

This complexity arises because, for each element, the algorithm may have to perform multiple swaps to place it in the correct position.

Space Complexity

• Space: O(1)

Since Cycle Sort does not require any additional data structures beyond a few variables for swapping, it has constant space complexity.

Simple Algorithm for Cycle Sort

Cycle Sort Algorithm:

1. Start from the first index and initialize the position of the element (pos) to its current index (i).

2. For each element, count how many elements are smaller than it to determine its correct position.

3. If the element is already in the correct position, continue to the next element.

4. Otherwise, place the element in its correct position by swapping it.

5. Repeat the process to fix all misplaced elements in the current cycle

                                        <-Algorithm ->
Suppose we have Array: [3, 5, 2, 1, 4]

Step 1: Start with index 0 (value 3).
Step 2: Count elements smaller than 3 — (values 2, 1) 
        Correct position of 3 = index 2
Step 3: Swap value at index 0 with index 2. 
        New array = [2, 5, 3, 1, 4]

Step 4: Repeat for all indices until sorted.
Final Array: [1, 2, 3, 4, 5]

Code For Cycle Sorting

import java.util.*;

public class Main {
    public static void main(String args[]) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {5, 3, 1, 2, 4};

        System.out.println("Performing cyclic sort on arr1:");
        cyclicSort(arr1);
        System.out.println(Arrays.toString(arr1));

        System.out.println("Performing cyclic sort on arr2:");
        cyclicSort(arr2);            //Driver code for cyclic sort
        System.out.println(Arrays.toString(arr2));
    }

    static void swap(int[] array, int num1, int num2) {
        int temp = array[num1];
        array[num1] = array[num2];
        array[num2] = temp;
    }

    static void cyclicSort(int[] array) {         //cyclic sort starts    
        int i = 0;                //putting i=0 as we want loop to run if elements in array is greater than 0
        while (i < array.length) {   
            int correctIndex = array[i] - 1;    //did this as loop is indexed from 0 to n and we have to compare index with value
            //suppose {1,2,3} 1 has index-> 0, 2 has index->1 .index is always 1 less than value 
            if (array[i] != array[correctIndex]) {
                swap(array, i, correctIndex);
            } else {
                i++; //if element equals to index if block will take place and we will be going to else block which says to increment value of i so comparrision of next index in array can take place   
            }
        }
    }
}