Back to DSA Course

DSA Course

Cyclic Sort

Cycle sort is a comparison sorting algorithm which forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array. It is theoretically optimal in the sense that it reduces the number of writes to the original array.

It is an in-place and unstable sorting algorithm.

It is optimal in terms of number of memory writes. It minimizes the number of memory writes to sort. Each value is either written zero times, if it's already in its correct position, or written one time to its correct position.

Consider an array of n distinct elements. An element a is given, index of a can be calculated by counting the number of elements that are smaller than a.

  • If the element is found to be at its correct position, simply leave it as it is.
  • Otherwise, find the correct position of a by counting the total number of elements that are less than a . where it must be present in the sorted array. The other element b which is replaced is to be moved to its correct position. This process continues until we got an element at the original position of a.

Let's start coding for cyclic sort

package com.praveen.sort;

import java.util.Arrays;

public class CyclicSort {

	public static void main(String[] args) {
		int[] arr = { 5, 4, 3, 2, 1};
		cyclic(arr);
		System.out.println(Arrays.toString(arr));

	}

	private static void cyclic(int[] arr) {
		int i = 0;
		while (i < arr.length) {
			int correct = arr[i] - 1;
			if (arr[i] != arr[correct]) {
				swap(arr, i, correct);
			} else {
				i++;
			}
		}
	}

	private static void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

}

Output

[1, 2, 3, 4, 5]

Let's see some programs

1.Missing Number

package com.praveen.sort.cyclic;

public class MissingNumber {

	public static void main(String[] args) {
		System.out.println(missingNumber(new int[] { 4, 0, 2, 1 }));
		System.out.println(missingNumber(new int[] { 9, 6, 4, 2, 3, 5, 7, 0, 1 }));

	}

	private static int missingNumber(int[] arr) {
		int i = 0;
		while (i < arr.length) {
			int correct = arr[i];
			if (arr[i] < arr.length && arr[i] != arr[correct]) {
				swap(arr, i, correct);
			} else {
				i++;
			}
		}

		// search for first missing number
		for (int index = 0; index < arr.length; index++) {
			if (arr[index] != index) {
				return index;
			}
		}

		// case 2
		return arr.length;
	}

	private static void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

}

Output

3
8

2.Find All Numbers Disappeared in an Array

package com.praveen.sort.cyclic;

import java.util.ArrayList;
import java.util.List;

public class FindAllMissing {

	public static void main(String[] args) {

		System.out.println(findDisappearedNumbers(new int[] { 4, 3, 2, 7, 8, 2, 3, 1 }));

	}

	private static List<Integer> findDisappearedNumbers(int[] nums) {
		int i = 0;
		while (i < nums.length) {
			int correct = nums[i] - 1;
			if (nums[i] != nums[correct]) {
				swap(nums, i, correct);
			} else {
				i++;
			}
		}

		// just find missing numbers
		List<Integer> ans = new ArrayList<>();
		for (int index = 0; index < nums.length; index++) {
			if (nums[index] != index + 1) {
				ans.add(index + 1);
			}
		}

		return ans;
	}

	private static void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

}

Output

[5, 6]

3.Find the Duplicate Number

package com.praveen.sort.cyclic;

public class FindDuplicate {

	public static void main(String[] args) {

		System.out.println(findDuplicate(new int[] { 1, 3, 4, 2, 2 }));
		System.out.println(findDuplicate(new int[] { 3, 1, 3, 4, 2 }));
	}

	private static int findDuplicate(int[] arr) {
		int i = 0;
		while (i < arr.length) {

			if (arr[i] != i + 1) {
				int correct = arr[i] - 1;
				if (arr[i] != arr[correct]) {
					swap(arr, i, correct);
				} else {
					return arr[i];
				}
			} else {
				i++;
			}
		}
		return -1;
	}

	private static void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

}

Output

2
3

4.Find All Duplicates in an Array

package com.praveen.sort.cyclic;

import java.util.ArrayList;
import java.util.List;

public class FindAllDuplicates {

	public static void main(String[] args) {
		System.out.println(findDuplicates(new int[] { 4, 3, 2, 7, 8, 2, 3, 1 }));
		System.out.println(findDuplicates(new int[] { 1, 1, 2 }));
		System.out.println(findDuplicates(new int[] { 1 }));
	}

	private static List<Integer> findDuplicates(int[] arr) {
		int i = 0;
		while (i < arr.length) {
			int correct = arr[i] - 1;
			if (arr[i] != arr[correct]) {
				swap(arr, i, correct);
			} else {
				i++;
			}
		}

		List<Integer> ans = new ArrayList<>();
		for (int index = 0; index < arr.length; index++) {
			if (arr[index] != index + 1) {
				ans.add(arr[index]);
			}
		}

		return ans;
	}

	private static void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

}

Output

[3, 2]
[1]
[]

5.Set Mismatch

package com.praveen.sort.cyclic;

import java.util.Arrays;

public class SetMismatch {

	public static void main(String[] args) {
		System.out.println(Arrays.toString(findErrorNums(new int[] { 1, 2, 2, 4 })));
		System.out.println(Arrays.toString(findErrorNums(new int[] { 1, 1 })));
		System.out.println(Arrays.toString(findErrorNums(new int[] { 1 })));
	}

	private static int[] findErrorNums(int[] arr) {
		int i = 0;
		while (i < arr.length) {
			int correct = arr[i] - 1;
			if (arr[i] != arr[correct]) {
				swap(arr, i, correct);
			} else {
				i++;
			}
		}

		// search for first missing number
		for (int index = 0; index < arr.length; index++) {
			if (arr[index] != index + 1) {
				return new int[] { arr[index], index + 1 };
			}
		}
		return new int[] { -1, -1 };
	}

	private static void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

}

Output

[2, 3]
[1, 2]
[-1, -1]

6.First Missing Positive

package com.praveen.sort.cyclic;

public class MissingPositive {

	public static void main(String[] args) {
		System.out.println(firstMissingPositive(new int[] { 1, 2, 0 }));
		System.out.println(firstMissingPositive(new int[] { 3, 4, -1, 1 }));
		System.out.println(firstMissingPositive(new int[] { 7, 8, 9, 11, 12 }));
	}

	private static int firstMissingPositive(int[] arr) {
		int i = 0;
		while (i < arr.length) {
			int correct = arr[i] - 1;
			if (arr[i] > 0 && arr[i] <= arr.length && arr[i] != arr[correct]) {
				swap(arr, i, correct);
			} else {
				i++;
			}
		}

		// search for first missing number
		for (int index = 0; index < arr.length; index++) {
			if (arr[index] != index + 1) {
				return index + 1;
			}
		}

		// case 2
		return arr.length + 1;
	}

	private static void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

}

Output

3
2
1