**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;
}
}
```

## Top comments (0)