Skip to main content

Cyclic Sort

  • Understanding cyclic sort
  • Solved problems are presented in alphabetical order
Missing Number

️↗ See LeetCode Problem #268​

public class Solution {    //  Solved using the binary approach    //  Cyclic sorting can/will be added at a later time    static int missingNumber(int[] nums) {        //  nums.length will always be in the given array        //      but it won't appear as an index in the for loop        int missing = nums.length;        for (int i = 0; i < nums.length; i++) {            missing ^= nums[i] ^ i;        }        return missing;    }    public static void main(String[] args) {        // Example 1:        int[] nums1 = {3, 0, 1};        //  O/P: 2        // Example 2:        int[] nums2 = {0, 1};        //  O/P: 2        // Example 3:        int[] nums3 = {9, 6, 4, 2, 3, 5, 7, 0, 1};        //  O/P: 8        // Example 4:        int[] nums4 = {2, 0, 3};        //  O/P: 2        // 3^2^0^0^1^3^2        System.out.println("Example 1: " + missingNumber(nums1));        System.out.println("Example 2: " + missingNumber(nums2));        System.out.println("Example 3: " + missingNumber(nums3));        System.out.println("Example 4: " + missingNumber(nums4));    } }
Separate 1s and 0s

Problem Statement in the Code Block​

import java.util.Arrays;public class Solution {    /*  Problem Statement:    *   Given an array of 0s and 1s in random order. Separate 0s on the    *   left side and 1s on right side of the array.     */    public static int[] separate1sAndOs (int[] nums) {        int zeroIndex = 0;        int oneIndex = nums.length - 1;        while (zeroIndex < oneIndex) {            if (nums[zeroIndex] == 1) {                if (nums[oneIndex] != 1) {                    swapElements(nums, zeroIndex, oneIndex);                }                oneIndex--;            } else {                zeroIndex++;            }        }        return nums;    }    private static void swapElements (int[] nums, int index, int newIndex) {        int tempElement = nums[index];        nums[index] = nums[newIndex];        nums[newIndex] = tempElement;    }    public static void main(String[] args) {        int[] array1 = { 0, 1, 0, 1, 1, 1 };        int[] array2 = { 0, 1, 0, 1, 1, 1, 0, 0};        int[] array3 = {0};        int[] array4 = {1};        int[] array5 = {};        System.out.println(Arrays.toString(separate1sAndOs(array1)));        System.out.println(Arrays.toString(separate1sAndOs(array2)));        System.out.println(Arrays.toString(separate1sAndOs(array3)));        System.out.println(Arrays.toString(separate1sAndOs(array4)));        System.out.println(Arrays.toString(separate1sAndOs(array5)));    }}