## DEV Community

Prashant Mishra

Posted on • Updated on

# Circular sorting algorithm

Circular sorting
Pre-requisite : elements of the array should be between 1 to length of the array
In `Circular Sorting` elements are placed at their natural indexs
Example:`if the array is [5,4,2,1,3] => [1,2,3,4,5]`

``````class Solution {
public List<Integer> findDuplicates(int[] nums){
int i =0,n  = nums.length;
while(i<n){
int j = nums[i]-1;
if(nums[i]!=nums[j]){
swap(nums,i,j);
}
else i++;
}

}
public void swap(int[] nums,int i ,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
``````

Usage:

• Its useful in identifying duplicates in the array

• It can also be used to find missing elements in the array

Example : Finding missing element in the array of length `n` where the elements of the array are in the range `0<=element<=n`

``````class Solution {
public int missingNumber(int[] nums) {
int i =0,n = nums.length;
// circular sorting
while(i<n){
int  j = nums[i]-1;
if(j<0) {i++ ; continue;}
else if(nums[i]!=nums[j]) swap(nums,i,j);
else i++;
}
int missing = 0;
for(int k = 0;k<nums.length;k++){
if(k!=nums[k]-1){ missing = k+1; break;}
}
return missing;

}
public void swap(int[] nums,int i,int j){
int temp  = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
``````