Sort Colors - Python Solution

1. Introduction

"Sort Colors" is an intriguing problem that deals with sorting an array of elements representing different colors. The challenge lies in sorting these elements in-place based on their assigned numerical values, representing specific colors, without using a library sort function. This problem is a practical example of applying partitioning algorithms like the Dutch National Flag algorithm.

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. The colors are represented by integers 0 (red), 1 (white), and 2 (blue), respectively. The goal is to sort the array with these constraints without using a library's sort function.

2. Solution Steps

1. Initialize three pointers: low for the start, mid for the current element, and high for the end of the array.

2. Iterate through the array using the mid pointer.

3. If the element at mid is 0, swap it with the element at low, increment low and mid.

4. If the element at mid is 1, simply increment mid.

5. If the element at mid is 2, swap it with the element at high and decrement high.

6. Continue this process until mid exceeds high.

7. The array will be sorted with reds at the beginning, followed by whites, and blues at the end.

3. Code Program

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

# Example Usage
nums = [2,0,2,1,1,0]
sortColors(nums)
print(nums)  # Output: [0,0,1,1,2,2]

nums = [2,0,1]
sortColors(nums)
print(nums)  # Output: [0,1,2]

Output:

[0,0,1,1,2,2]
[0,1,2]

Explanation:

1. Dutch National Flag Algorithm: Uses a three-way partitioning approach to sort the colors.

2. Pointer Management: The low, mid, and high pointers are used to segregate the colors.

3. In-place Sorting: The array is sorted in-place, ensuring O(1) space complexity.

4. Efficient Solution: The solution runs in O(n) time complexity, where n is the number of elements in the array.

5. Practical Use Case: Demonstrates an efficient way to sort elements when there are a small number of distinct values.