Dutch National Flag Problem.
Given an array containing elements that can take one of three distinct values (e.g., red, white, and blue), the task is to sort the array in place such that elements of the same value are grouped together and the array is partitioned into three sections:
- All elements less than a certain value (e.g., red).
- All elements equal to that value.
- All elements greater than a certain value (e.g., blue).
Example:
Suppose the array represents colors: [1, 0, 2, 1, 0, 2] (0 for red, 1 for white, 2 for blue).
Initial Array: [1, 0, 2, 1, 0, 2] Sorted Array: [0, 0, 1, 1, 2, 2]
Dutch National Flag Algorithm Explain.
This algorithm is used for partitioning elements within an array containing multiple distinct values, grouping similar elements together efficiently in a single pass through the array.
Step 1: Initialize three-pointers low, mid, and high where low and mid-pointers point to the start of the array and high pointer points to the end of the array.
Step 2: Start iterating through the array while mid is less than or equal to high:
- If the element at mid is the lower value (0) then swap the element at low with the element at mid and increment both low and mid.
- If the element at mid is the middle value (1) then increment mid by 1.
- If the element at mid is the higher value (2) then swap the element at mid with the element at high and decrement high.
Step 3: Keep repeating step 2 until mid crosses high, ensuring all elements are appropriately sorted.
Working Example of Dutch National Flag Algorithm.
This algorithm basically sorts an array containing only three different types of values. Below we are showing the operation it performs in each iteration.
| Iteration | Array | Operation/Description |
|---|---|---|
| 1. | [1, 0, 2, 1, 0, 2] | Initial array |
| 2. | [0, 0, 2, 1, 1, 2] | Swap 1 at index 0 with 0 at index 1 |
| 3. | [0, 0, 2, 1, 1, 2] | Increment 'mid' |
| 4. | [0, 0, 2, 1, 1, 2] | Increment 'mid' |
| 5. | [0, 0, 2, 1, 1, 2] | Swap 2 at index 2 with 2 at index 5 |
| 6. | [0, 0, 1, 1, 2, 2] | Decrement 'high' and Increment 'mid' |
I hope that now you have understood the workings of the Dutch National Flag Algorithm and we are going to implement this algorithm using different programming languages such as C, C++, Python, and Java.
C Code Implementation:
// C Code Implementation of Dutch National Flag Algorithm #include <stdio.h> // Function to swap two values void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // function definition void sortColors(int* nums, int numsSize) { int low = 0, mid = 0, high = numsSize - 1; while (mid <= high) { switch(nums[mid]) { case 0: swap(&nums[low++], &nums[mid++]); break; case 1: mid++; break; case 2: swap(&nums[mid], &nums[high--]); break; } } } int main() { int nums[] = {1, 0, 2, 1, 0, 2}; int numsSize = sizeof(nums) / sizeof(nums[0]); sortColors(nums, numsSize); printf("Sorted Array: "); for (int i = 0; i < numsSize; ++i) { printf("%d ", nums[i]); } printf("\n"); return 0; }
Sorted Array: 0 0 1 1 2 2
C++ Code Implementation:
// C++ code implementation of Dutch National Flag Algorithm #include <iostream> #include <vector> using namespace std; void sortColors(vector<int>& nums) { int low = 0, mid = 0, high = nums.size() - 1; while (mid <= high) { switch(nums[mid]) { case 0: swap(nums[low++], nums[mid++]); break; case 1: mid++; break; case 2: swap(nums[mid], nums[high--]); break; } } } int main() { vector<int> nums = {1, 0, 2, 1, 0, 2}; sortColors(nums); cout << "Sorted Array: "; for (int i = 0; i < nums.size(); ++i) { cout << nums[i] << " "; } cout << endl; return 0; }
Output:
Sorted Array: 0 0 1 1 2 2
Java Code Implementation:
// Java Code Implementation for Dutch National Flag Algorithm public class DutchNationalFlag { // Function public static void sortColors(int[] nums) { int low = 0, mid = 0, high = nums.length - 1; while (mid <= high) { switch(nums[mid]) { case 0: int tempLow = nums[low]; nums[low++] = nums[mid]; nums[mid++] = tempLow; break; case 1: mid++; break; case 2: int tempHigh = nums[high]; nums[high--] = nums[mid]; nums[mid] = tempHigh; break; } } } public static void main(String[] args) { int[] nums = {1, 0, 2, 1, 0, 2}; sortColors(nums); System.out.print("Sorted Array: "); for (int num : nums) { System.out.print(num + " "); } System.out.println(); } }
Output:
Sorted Array: 0 0 1 1 2 2
Python Code Implementation:
# Python Code Implementation of Dutch National Flag Algorithm 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 nums = [1, 0, 2, 1, 0, 2] sortColors(nums) print("Sorted Array:", nums)
Output:
Sorted Array: 0 0 1 1 2 2
Time and Space Complexity.
Time Complexity: The Dutch National Flag Algorithm processes each element in the array exactly once so the time complexity is O(n) where n is the number of elements in the array.
Space Complexity: The algorithm performs sorting in the same array without using additional data structures. It uses only a few variables (pointers) to manipulate the array elements, resulting in contact space usage O(1).
No comments:
Post a Comment