# 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.

## Comments

## Post a Comment