Skip to main content

Cyclic Sort

Cyclic Sort: 
  • Missing/Repeated/Duplicate Numbers
  • Unsorted Array
  • Permutation/Sequence
  • In-place Sorting
  • Unique Elements
  • Indices/Positions
  • Range of Numbers
  • Fixed Range/Constant Range
  • Modifying Indices/Positions
  • Array Shuffling
  • Swapping Elements
  • Array Partitioning

  • Range of Numbers: The problem involves an array containing a permutation of numbers from 1 to N, where N is the length of the array or a known upper bound. The numbers in the array are expected to be consecutive integers starting from 1.

  • Missing Numbers or Duplicates: The problem requires finding missing numbers or duplicates within the given array. Typically, the array may have some missing numbers or duplicates, disrupting the sequence of consecutive integers.

  • No Negative Numbers or Zeroes: The problem specifies that the array contains only positive integers, excluding zero and negative numbers. Cyclic sort works efficiently with positive integers and relies on the absence of zero or negative values.

  • Linear Time Complexity Requirement: The problem constraints or requirements indicate the need for a solution with linear time complexity (O(N)), where N is the size of the array. Cyclic sort achieves linear time complexity as it involves iterating through the array once or a few times.

  • In-Place Sorting Requirement: The problem requires sorting the array in-place without using additional data structures or consuming extra space. Cyclic sort operates by rearranging the elements within the given array, fulfilling the in-place sorting requirement.

  • Adjust the range as required (0-n, 1-n), also adjust the index 

The Cyclic Sort Pattern typically involves a WHILE loop and the following components:

  1. Initialization: Start by initializing a pointer i to 0.

  2. Iterative Sorting: Repeat the following steps until i reaches the end of the array:

    • Calculate the correct index for the current number at index i. For example, if the array contains numbers from 1 to N, the correct index for the number x at index i would be x - 1.
    • Check if the number at index i is already in its correct position. If it is, increment i to move to the next element.
    • If the number at index i is not in its correct position, swap it with the number at its correct index.
    • Repeat these steps until all numbers are placed in their correct positions.

  3. Termination: Once i reaches the end of the array, the array is sorted.

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_index = nums[i] - 1  # Correct index for the current number
        if nums[i] != nums[correct_index]:  # If the number is not at its correct index
            nums[i], nums[correct_index] = nums[correct_index], nums[i]  # Swap the numbers
        else:
            i += 1  # Move to the next number if it's already at the correct index

# Example usage:
arr = [3, 1, 5, 4, 2]
cyclic_sort(arr)
print(arr)  # Output: [1, 2, 3, 4, 5]

Back to top