Sort Colors Algorithm

The Sort Colors Algorithm, also known as the Dutch National Flag Algorithm or the three-way partitioning algorithm, is an efficient in-place sorting algorithm designed to sort an array containing three distinct values or colors. It is named after the Dutch flag because the algorithm partitions the input array into three sections, just like the three-colored flag of the Netherlands. The algorithm is particularly useful in practical applications where the input data has a limited set of possible values, such as sorting colors or numbers in a specific range. The algorithm works by maintaining three pointers - low, mid, and high, which are initially set to the beginning, beginning, and end of the array, respectively. The mid pointer is used to iterate through the array, and depending on the value encountered, the algorithm either swaps it with the value at the low pointer, keeps it in place, or swaps it with the value at the high pointer. If the value is the smallest (i.e., the first color), the algorithm swaps it with the value at the low pointer and increments both the low and mid pointers. If the value is the largest (i.e., the third color), the algorithm swaps it with the value at the high pointer and decrements the high pointer. If the value is the middle value (i.e., the second color), the algorithm simply increments the mid pointer. This process continues until the mid pointer crosses the high pointer, at which point the array is sorted into three distinct sections corresponding to the three distinct values.
class Solution {
public:
    void sortColors(int A[], int n) {
        int p0 = -1;
        int p1 = 0;
        int p2 = n;
        while (p1 < p2) {
            if (A[p1] == 1) {
                p1++;
            } else if (A[p1] == 0) {
                swap(A[p0+1], A[p1]);
                p0++;
                p1++;
            } else {
                swap(A[p1], A[p2-1]);
                p2--;
            }
        }
    }
};

//
// Solution2 using the method like quicksort
//
class Solution2 {
public:
    void sortColors(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int p = split(A, 0, n - 1, 0);
        split(A, p + 1, n - 1, 1);
    }
    int split(int A[], int low, int high, int pivot) {
        int i = low - 1;
        for (int j = low; j <= high; j++) {
            if (A[j] <= pivot) {
                i += 1;
                if (i != j) swap(A[i], A[j]);
            }
        }
        return i;
    }
};

LANGUAGE:

DARK MODE: