Sort Colors - Java Solution

1. Introduction

This post discusses a solution to the "Sort Colors" problem, a classic challenge in sorting algorithms and partitioning. It involves sorting an array containing objects of three different colors, represented by 0, 1, and 2, without using a library's sort function. The goal is to sort the objects so that the same colors are adjacent and in the order of red (0), white (1), and blue (2).

Problem

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent in the order red, white, and blue (corresponding to 0, 1, and 2, respectively).

Examples:

- Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

- Input: nums = [2,0,1]

Output: [0,1,2]

2. Solution Steps

1. Use three pointers approach: start for 0s, end for 2s, and index for the current element.

2. Iterate through the array:

- If the current element is 0, swap it with the element at start and move both start and index forward.

- If the current element is 2, swap it with the element at end and move end backward.

- If the current element is 1, just move index forward.

3. Continue this process until index crosses end.

3. Code Program

public class SortColors {
    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0};
        sortColors(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    // Function to sort colors represented by 0, 1, and 2
    public static void sortColors(int[] nums) {
        int start = 0, end = nums.length - 1, index = 0;

        while (index <= end) {
            if (nums[index] == 0) {
                swap(nums, index++, start++);
            } else if (nums[index] == 2) {
                swap(nums, index, end--);
            } else {
                index++;
            }
        }
    }

    // Helper method to swap elements in the array
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Output:

0 0 1 1 2 2

Explanation:

1. sortColors: This function sorts the array nums containing 0s, 1s, and 2s.

2. A three-pointer approach is used: start, end, and index to manage the positions where 0s and 2s should be placed.

3. The function iterates through the array, swapping 0s to the beginning and 2s to the end, while 1s automatically get arranged in the middle.

4. The swapping is done in-place, and the iteration continues until index surpasses end.

5. This approach ensures that the sorting is completed in a single pass through the array, resulting in an efficient O(n) time complexity.

6. No additional space is used apart from the variable swaps, adhering to the O(1) space complexity requirement.