Cyclic Sort

Cyclic sort is a technique used to efficiently sort a collection of numbers when the elements are within a specific range. It works by placing each number at its correct index, cycling through the array until all elements are in their right positions. This approach is especially useful for problems where the array contains elements in the range from 1 to n, where n is the length of the array.

When to use it

You can recognize problems that can be solved with cyclic sort if they meet one or more of these conditions:

1. The input contains numbers within a bounded range (1 to n)
2. The problem involves rearranging or finding specific patterns like missing, duplicate, or misplaced numbers in constant space.

Why use it

Cyclic sort is highly efficient for problems involving numbers within a specific range. It works in $O(n)$ time complexity and uses constant space, making it ideal for scenarios where both time and space optimizations are necessary. The idea of placing each number in its correct position simplifies the process of finding missing or duplicate numbers.

How it works

The key to cyclic sort is ensuring that each number is placed at the index corresponding to its value. The algorithm continuously swaps elements until all numbers are in their correct places. The core steps are:

1. Iterate through the array.
2. For each number, if it is not at its correct index (i.e., the index does not match its value), swap it with the number at its target index.
3. Repeat the process until all numbers are in their correct positions.

Example 1: Sorting an array of consecutive numbers

Given an array of numbers where each number is in the range from 1 to n, sort the array in-place (without using extra space) in $O(n)$ time. Below is an implementation of cyclic sort to do this.

Python
def cyclic_sort(nums):
    i = 0
    while i < len(nums): 
        # Since numbers are from 1 to n, the correct index for num is num-1
        correct_idx = nums[i] - 1 

        if nums[i] != nums[correct_idx]: 
            # Swap to place the number at the correct index
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1

    return nums

Example 2: Find the smallest missing positive number

Given an unsorted array of integers, find the smallest missing positive number. To solve this, we cyclic sort the array, then find the smallest index where the number is not correct.

Python
def find_smallest_missing_positive(nums):
    n = len(nums)

    # Cyclic sort to place numbers in their correct index
    i = 0
    while i < n:
        correct_idx = nums[i] - 1
        # Only swap if nums[i] is in the range [1, n] and not already in the correct position
        if 1 <= nums[i] <= n and nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1

    # Now find the first index where the number is not correct
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1  # The smallest missing positive number

    # If all positions are correct, return n + 1
    return n + 1

Examples

1. Find the missing number
   • Problem: Given an array containing numbers from 1 to n, find the one missing number.
   • Approach: Use cyclic sort to rearrange the array, then identify the index where the number is missing.
2. Find all duplicate numbers
   • Problem: Given an array of numbers from 1 to n where some numbers appear twice, find all duplicates.
   • Approach: After using cyclic sort, check for numbers that are not in their correct positions.
3. Find all numbers missing in an array
   • Problem: Given an array where numbers are from 1 to n, find all the numbers that are missing.
   • Approach: Use cyclic sort to place all elements in their correct positions, then identify the missing ones.