Improvement in CycleSort algorithm

[hammadsaedi]

File: master/src/main/java/algorithm/CountingSortSnippet.java

Description:

The cycle sort algorithm has a bug in the following line:

if (arr[i] < n && arr[i] != arr[correctpos])

The bug is that the condition arr[i] < n is not necessary. The algorithm should simply check if the element at i is not in its correct position.

Workaround:

To fix the bug, simply remove the condition arr[i] < n from the following line:

if (arr[i] < n && arr[i] != arr[correctpos])

The corrected line is:

if (arr[i] != arr[correctpos])

Proposed fix:

I propose that we make the following change to the cycleSort() method:

public static int[] cycleSort(int[] arr) {
  int n = arr.length;
  int i = 0;
  while (i < n) {
    int correctpos = arr[i] - 1;
    if (arr[i] != arr[correctpos]) {
      int temp = arr[i];
      arr[i] = arr[correctpos];
      arr[correctpos] = temp;
    } else {
      i++;
    }
  }
  return arr;
}

This change will fix the bug and make the algorithm more efficient.

[hammadsaedi]

@iluwatar pls check this out :)

[hammadsaedi]

@iluwatar I've done this. You can check PR here:
#195