Lecture 46 :- Sort Colors

Sorting Colors, also known as the Dutch National Flag problem, is a popular array sorting problem. The goal is to sort an array containing only 0s, 1s, and 2s in ascending order without using any sorting algorithms like QuickSort or MergeSort.

Here's the problem statement:

Given an array nums containing only 0s, 1s, and 2s, sort the array in-place such that all 0s come before 1s, and all 1s come before 2s.

Example:

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

To solve this problem, we can use a two-pointer approach, often called the Dutch National Flag algorithm. The two pointers low and high will be used to keep track of the position of 0s and 2s, respectively.

Algorithm:

1. Initialize three pointers: low, mid, and high.
2. low points to the start of the array, mid points to the start, and high points to the end of the array.
3. Traverse the array using the mid pointer.
4. If the element at mid is 0, swap it with the element at low, and increment both low and mid.
5. If the element at mid is 1, leave it in its place and just increment mid.
6. If the element at mid is 2, swap it with the element at high, and decrement high.
7. Repeat steps 3-6 until mid becomes greater than high.

Here's the C++ code to sort the colors (0s, 1s, and 2s) in ascending order:

cppCopy code

#include <iostream> #include <vector> void sortColors(std::vector<int>& nums) {    int low = 0;    int mid = 0;    int high = nums.size() - 1;    while (mid <= high) {        if (nums[mid] == 0) {            std::swap(nums[low], nums[mid]);            low++;            mid++;        } else if (nums[mid] == 1) {            mid++;        } else {            std::swap(nums[mid], nums[high]);            high--;        }    } } int main() {    std::vector<int> nums = {2, 0, 2, 1, 1, 0};    std::cout << "Before Sorting: ";    for (int num : nums) {        std::cout << num << " ";    }    std::cout << std::endl;    sortColors(nums);    std::cout << "After Sorting: ";    for (int num : nums) {        std::cout << num << " ";    }    std::cout << std::endl;    return 0; }

Example Output:

mathematicaCopy code

Before Sorting: 2 0 2 1 1 0 After Sorting: 0 0 1 1 2 2

In this solution, the sortColors function performs the sorting in-place using the two-pointer approach. The time complexity of this algorithm is O(n), where n is the number of elements in the array.