Sort Colors - C Solution

1. Introduction

In this blog post, we will tackle a fundamental problem in array manipulation using C programming: sorting an array of colors represented by integers. This problem is known as the Dutch National Flag problem and is commonly used to understand partitioning in sorting algorithms.

Problem

Given an array 'nums' with 'n' objects colored red, white, or blue, represented by the integers 0, 1, and 2, respectively, the task is to sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. The solution must be achieved without using the library's sort function.

2. Solution Steps

1. Use three pointer approach: 'low', 'mid', and 'high'.

2. Initialize 'low' and 'mid' to the beginning of the array and 'high' to the end.

3. Traverse the array using 'mid' and swap elements to rearrange the colors:

- If 'nums[mid]' is 0, swap it with 'nums[low]' and increment both 'low' and 'mid'.

- If 'nums[mid]' is 1, increment 'mid'.

- If 'nums[mid]' is 2, swap it with 'nums[high]' and decrement 'high'.

4. Continue this process until 'mid' exceeds 'high'.

3. Code Program

#include <stdio.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to sort colors
void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(&nums[low++], &nums[mid++]);
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(&nums[mid], &nums[high--]);
        }
    }
}

// Main function to demonstrate sortColors function
int main() {
    int nums[] = {2, 0, 2, 1, 1, 0}; // Example input
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    sortColors(nums, numsSize); // Call the function

    // Print the sorted array
    printf("Output: ");
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

Output:

0 0 1 1 2 2

Explanation:

The program sorts an array of colors using the three-pointer approach. This approach partitions the array into three sections: red (0), white (1), and blue (2). The 'low' pointer is used to place all the reds at the beginning, the 'mid' pointer traverses the array, and the 'high' pointer places all the blues at the end. 

In the example, the array [2, 0, 2, 1, 1, 0] is sorted to [0, 0, 1, 1, 2, 2], arranging the colors in the order red, white, and blue. 

This approach efficiently sorts the array in a single pass with O(1) extra space.