Introduction

Cyclic Sort is a pattern that deals with sorting problems in arrays with a specific range of numbers. It's an in-place sorting algorithm with a time complexity of O(N), where N is the number of elements in the array.

Overview

The Cyclic Sort Pattern is used to sort an array containing a range of numbers from 1 to N (or 0 to N-1) where some elements are missing, and there are no duplicates. The pattern works by placing each element in its correct position in the sorted array, utilizing the cyclic nature of the array.

The cyclic sort algorithm is an in-place sorting algorithm. This means that no external data structure (such as a list or heap) is required to perform the cycle sort operation.

Example:

Let's understand the Cyclic Sort Pattern with an example in C++:

Consider we have an array nums of size n, with elements ranging from 1 to n. We will use the Cyclic Sort Pattern to sort the array.

#include <iostream>
#include <vector>

void cyclicSort(std::vector<int>& nums) {
    int i = 0;
    while(i < nums.size()) {
        if(nums[i] != i + 1) {
            std::swap(nums[i], nums[nums[i] - 1]);
        } else {
            i++;
        }
    }
}

int main() {
    std::vector<int> nums = {3, 1, 5, 4, 2};

    cyclicSort(nums);

    std::cout << "Sorted Array: ";
    for(auto num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Illustration:

Original Array: [3, 1, 5, 4, 2]

Iteration 1: [1, 3, 5, 4, 2]
Iteration 2: [1, 2, 5, 4, 3]
Iteration 3: [1, 2, 3, 4, 5]

Sorted Array: [1, 2, 3, 4, 5]

Complexity Analysis

• The time complexity of the above algorithm is O(n). Although we are not incrementing the index i when swapping the numbers, this will result in more than n iterations of the loop, but in the worst-case scenario, the while loop will swap a total of n-1 numbers and once a number is at its correct index, we will move on to the next number by incrementing i. So overall, our algorithm will take O(n) + O(n-1) which is asymptotically equivalent to O(n).
• The algorithm runs in constant space O(1).

How to Identify this Pattern?

1. Elements in a Specific Range:
   1. The elements in the array are typically within a specific range, often from 1 to N.
2. Unsorted Array:
   1. The array is unsorted or partially sorted.
3. Unique Elements:
   1. The array contains unique elements.

Problems Featuring Cyclic Sort Pattern

1. Find the Missing Number.
2. Find the Smallest Missing Positive Number.