Cyclic Sort

Cyclic Sort is a simple and efficient in-place sorting algorithm. It operates by identifying the misplaced elements and then placing them at the correct position in the sorted array. The algorithm is based on the fact that the numbers in the array are within a certain range.

Cyclic Sort is called as such because it cycles through the array and places each element in its correct position. The complexity of this algorithm is O(n) since each element is placed once and only once.

How does it work?

The Cyclic Sort algorithm consists of the following steps:

1. Step 1 − Initialize the i variable to 0.

2. Step 2 − Traverse through the array from 0 to n-1.

3. Step 3 − Compare the current element (arr[i]) with the expected element (i+1).

4. Step 4 − If the current element is not equal to the expected element, swap the current element with the element at position arr[i] - 1.

5. Step 5 − Repeat above steps until the entire array is sorted.

Let's consider an example of how Cyclic Sort works:

Input array: [3, 5, 2, 1, 4]

1st Pass:
[1, 5, 2, 3, 4]
[1, 2, 5, 3, 4]
[1, 2, 3, 5, 4]
[1, 2, 3, 4, 5]

Output array: [1, 2, 3, 4, 5]

As we can see from the example above, the cyclic sort algorithm starts with the first element and compares it with the expected element. The expected element in this case is i+1, which means that the first expected element is 1. Here the correct index of element 3 is 2 i.e i-1 , So we place the element at its correct index and hence the process repeats.

If the current element is not equal to the expected element, then the current element is swapped with the element at position arr[i] - 1. This is because we assume that the array contains a set of distinct integers ranging from 1 to n. Therefore, the element that is misplaced can be found at position arr[i] - 1.

Implementation

Here's an implementation of the cyclic sort algorithm in Java :

public static void cyclic(int [] arr){
int i=0;
while(i<arr.length){
int correct= arr[i]-1;
if(arr[i] != arr[correct]){
int temp=arr[i];
arr[i]= arr[correct];
arr[correct]=temp;
}
else{
i++;
}
}

In this implementation, we initialize the i variable to 0 and traverse the array from 0 to n-1. We compare each element with its expected position and swap if necessary. Then, we move to the next element until the entire array is sorted.

Conclusion

One important thing to note is that the algorithm is only applicable when the input array contains distinct integers within a certain range. However, if the input array contains duplicates or elements outside the range, the algorithm will not provide the correct output.

Cyclic Sort is a great algorithm to use when we are dealing with a small and fixed range of integers. It can be used to sort things like grades, ages, or any other data that falls within a specific range. It is also a good algorithm to use when we have limited memory or need to sort an array in-place.

Overall, the Cyclic Sort algorithm is a useful tool to have in your programming toolkit.