educative.io

Educative

Cyclic Sort doesnt work for the test case 5,2,1,2,5,1

The very first cyclic problem is not working for the test case.
Input: 5 2 1 2 5 1
Result: 1 2 5 2 5 1
If all of the elements contains duplicates

Cyclic Sort Method:
public static void sort(int[] nums) {

int i = 0;

while (i < nums.length) {

  int j = nums[i] - 1;

  if (nums[i] != nums[j])

    swap(nums, i, j);

  else

    i++;

}

}

Hi @Srinim

The solution will not work for the array containing duplicate elements as it is a simpler and easy implementation of the cyclic sort. Duplicate values are not handled here which is also elaborated in the solution as " As we know, the input array contains numbers from the range 1 to n. We can use this fact to devise an efficient way to sort the numbers. Since all numbers are unique, we can try placing each number at its correct place,".