Coding Pattern: Cyclic Sort

This is the 5th pattern of Grokking the Coding Interview: Patterns for Coding Questions. Cyclic sort is really good for dealing with arrays containing numbers in a given range. The cyclic sort pattern iterates over the array one number at a time and if the current number you’re iterating is not in the correct index, you swap it with the number at its correct index. Let’s see how to implement Cyclic Sort

Problem Statement

We are given an array containing ’n’ numbers in the range 1 to ’n’. Each number is unique. Write a function to sort the numbers in place in O(n) time and without any extra space.

Example 1:

[Input: [3, 1, 5, 4, 2]
Output: [1, 2, 3, 4, 5]

Example 2:

Input: [2, 6, 4, 3, 1, 5]
Output: [1, 2, 3, 4, 5, 6]

Example 3:

Input: [1, 5, 6, 4, 3, 2]
Output: [1, 2, 3, 4, 5, 6]

Solution

As we know, the input array contains numbers in the range of 1 to ’n’. We can use this fact to devise an efficient way to sort the numbers. Since all numbers are unique, we can try placing each number at its correct place, i.e., placing ‘1’ at index ‘0’, placing ‘2’ at index ‘1’, and so on.

To place a number at its correct index, we first need to find that number. If we first find a number and then place it at its correct place, it will take us O(N²), which is not acceptable.

Instead, what if we iterate the array one number at a time, and if the current number we are iterating is not at the correct index, we swap it with the number at its correct index. This way we will go through all numbers and place them in their correct indices, hence, sorting the whole array.

Let’s see the visual representation with the above-mentioned Example-2: Visual Representation of cycling sort

Code

Here is what our algorithm will look like-

def cyclic_sort(nums):
    start = 0

    while start < len(nums):
        swap = nums[start] - 1
        if nums[start] != nums[swap]:
            nums[start], nums[swap] = nums[swap], nums[start]

        else:
            start += 1

    return nums

Problems featuring cyclic sort pattern:

• Find the Missing Number (easy)
• Find the Smallest Missing Positive Number (medium)

How do I identify this pattern:

• They will be problems involving a sorted array with numbers in a given range
• If the problem asks you to find the missing/duplicate/smallest number in a sorted/rotated array

This article is inspired by: Grokking the Coding Interview: Patterns for Coding Questions