Cyclic Sort

Cyclic sort is an in-place sorting algorithm optimized for arrays containing numbers in a cyclic or circular range. It exploits the cycle to avoid swapping elements unnecessarily.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void cyclicSort(int[] arr) {
  int i = 0;
  while (i < arr.length) {
    int j = arr[i] - 1;
    if (arr[i] != arr[j]) {
      swap(arr, i , j);
    } else {
      i++; 
    }
  }
}

void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void cyclicSort(vector<int>& arr) {
  int i = 0;
  while (i < arr.size()) {
    int j = arr[i] - 1;
    if (arr[i] != arr[j])
      swap(arr[i], arr[j]);
    else
      i++;
  }
}

void swap(int &a, int &b) {
  int temp = a;
  a = b;
  b = temp;
}

Python example:

1
2
3
4
5
6
7
8
def cyclic_sort(arr):
  i = 0
  while i < len(arr):
    j = arr[i] - 1
    if arr[i] != arr[j]:
      arr[i], arr[j] = arr[j], arr[i] 
    else:
      i += 1

Cyclic sort is very efficient for numbers in a contiguous cycle from 1 to n. Useful for array problems with a cyclic range.

Cyclic Sort is an efficient in-place sorting algorithm used to sort objects in linear time and constant space. This algorithm is particularly useful when dealing with a sequence of numbers containing n elements that are all in the range of 1 to n.

The basic idea of Cyclic Sort is to place each number in its correct position, i.e., placing the number i at the i-1-th position. The algorithm iterates through the array, and if the current number is not at the correct index, it swaps the number with the one at its target index.

Solution

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public void cyclicSort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        if (nums[i] != nums[nums[i] - 1])
            swap(nums, i, nums[i] - 1);
        else
            i++;
    }
}

public void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

C++

1
2
3
4
5
6
7
8
9
void cyclicSort(vector<int>& nums) {
    int i = 0;
    while (i < nums.size()) {
        if (nums[i] != nums[nums[i] - 1])
            swap(nums[i], nums[nums[i] - 1]);
        else
            i++;
    }
}

Python

1
2
3
4
5
6
7
def cyclicSort(nums):
    i = 0
    while i < len(nums):
        if nums[i] != nums[nums[i] - 1]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        else:
            i += 1

The given code snippets for Java, C++, and Python perform the Cyclic Sort operation on the given array or list. By iterating through the array and swapping elements, this algorithm ensures that every number is placed in its correct position, thereby sorting the entire sequence.