Understanding Cycle Sort Algorithm: Step-by-Step in JavaScript ??

Cycle sort is an in-place, unstable sorting algorithm that is particularly useful when sorting arrays containing elements with a small range of values. It was developed by W. D. Jones and published in 1963.

The basic idea behind cycle sort is to divide the input array into cycles, where each cycle consists of elements that belong to the same position in the sorted output array. The algorithm then performs a series of swaps to place each element in its correct position within its cycle, until all cycles are complete and the array is sorted.

• Start with an unsorted array of n elements.
• Initialize a variable, cycleStart, to 0.
• For each element in the array, compare it with every other element to its right. If there are any elements that are smaller than the current element, increment cycleStart.
• If cycleStart is still 0 after comparing the first element with all other elements, move to the next element and repeat step 3.
• Once a smaller element is found, swap the current element with the first element in its cycle. The cycle is then continued until the current element returns to its original position.
• Repeat steps 3-5 until all cycles have been completed.

function cycleSort(arr, n) {
  let writes = 0;
  for (let cycle_start = 0; cycle_start <= n - 2; cycle_start++) {
    let item = arr[cycle_start];
    let pos = cycle_start;
    for (let i = cycle_start + 1; i < n; i++) if (arr[i] < item) pos++;
    if (pos == cycle_start) continue;
    while (item == arr[pos]) pos += 1;
    if (pos != cycle_start) {
      let temp = item;
      item = arr[pos];
      arr[pos] = temp;
      writes++;
    }
    while (pos != cycle_start) {
      pos = cycle_start;
      for (let i = cycle_start + 1; i < n; i++) if (arr[i] < item) pos += 1;
      while (item == arr[pos]) pos += 1;
      if (item != arr[pos]) {
        let temp = item;
        item = arr[pos];
        arr[pos] = temp;
        writes++;
      }
    }
  }
  return arr;
}

const arr = [64, 25, 12, 22, 11];
const n = arr.length;
console.log('Original Array:', arr);
const sortedArr = cycleSort(arr, n);
console.log('Sorted Array:', sortedArr);