Skip to main content

Cyclic Sort Algorithm

Cyclic Sort is an efficient algorithm for solving problems involving numbers that are in a range from 1 to n or 0 to n. The key idea is to place each number at its correct index.

Algorithm Steps:​

  1. Traverse the array and place each number at its correct index.
  2. Continue until all elements are at their correct positions.
  3. Use a constant space complexity of O(1) and a time complexity of O(n).

Example: Finding the Missing Number​

We can apply Cyclic Sort to solve the Missing Number problem.

Problem:​

Given an array of n numbers ranging from 0 to n, find the missing number.

function findMissingNumber(arr) {

  const cyclicSort = (nums) => {
    let i = 0;
    while (i < nums.length) {
      const correctIndex = nums[i];
      if (nums[i] < nums.length && nums[i] !== nums[correctIndex]) {
        [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]; // Swap
      } else {
        i++;
      }
    }
  };

  cyclicSort(arr); // Sort the array using cyclic sort
  
  for (let j = 0; j < arr.length; j++) {
    if (arr[j] !== j) {
      return j; // Return the missing number
    }
  }
  
  return arr.length; // If no number is missing, the missing number is n
}

// Example usage:
const nums = [4, 0, 3, 1];
console.log(findMissingNumber(nums)); // Output: 2

Problems to Practice​