Cycle Sort || Java + DSA course || Blog 14

- September 22, 2022

We learnt about Sorting algorithms like bubble sort, insertion sort, selection sort in Blog 9 Sorting in Java. So why are we learning cycle sort in a new blog?

Cycle sort questions are asked in various tech interviews , in huge companies like Facebook, Amazon, Google...

For a quick overview, we will be learning:-

What is Cyclic sort?
How to solve
Code
Working of the code.

What is cyclic sort?

Cyclic sort is used on an array from 1 to n or from 0 to n. In 1 to n case, we know that our first value will be 1 followed by 2 3 4...n.

if we try to place it at index 0(in java, index of an array starts from 0) we know value is 1 which can be also said as index+1 = 0+1 = 1.

At index 1, 2 should be placed = index+1 = 1+1 = 2.

This should keep on happening till nth value becomes n+1.

If we want a formula for index, it is index = value - 1 since every value has index+1 index.

How to solve

Lets take array = {3,5,1,2,4}

Correct index value should be arr[i]-1

We will check if our arr at index i is != arr[correct index value]

For this example, arr[i] = 3 now and arr[correct index value] will be 2.

It means 3 should be at index 2. So if they are not same then swap them together

now are array will be {1,5,3,2,4}

Now we will again check whether now are arr[i] is at a right position. We don't want to change i until arr[i] has the correct value.

arr[i] =1, arr[correct index value] = 0, so now 0th index has right value , so we will increment our i. i++.

At the end, we will print the data:-

Code

public class Cyclic {
    public static void main(String[] args) {
        int[] arr ={3,5,1,2,4};
        cyclicsort(arr);
    }
    static void cyclicsort(int[] arr){
        int i=0;//to use as an index
        while(i<arr.length){//run it till n times
             int id = arr[i]-1;//index =  value-1
             if(arr[id] != arr[i]){//if not equal
                //swaping
                int temp = arr[i];
                arr[i] = arr[id];
                arr[id] = temp;
             }else{
                i++;//increment the value, check for other index values
             }
        }
        //print the answer
        System.out.println("The sorted array is : ");
        for(int j=0;j<arr.length;j++){

            System.out.print(arr[j] + " ");
        }
        System.out.println();
    }

}