This is the Java Program to Solve the Dutch National Flag Problem.
Given an array of 0’s, 1’s and 2’s, all the elements in the random order, sort the array in linear time, without using extra space. This is known as the Dutch National Flag problem.
Example:
Array = [1 0 2 2 0 1]
Output
Array = [0 0 1 1 2 2]
The idea here is to divide the array into three regions such that the starting region contains all the zeroes, the next season contains all the ones and the final region contains all the zeroes. Start from the beginning of the array and check if the element is zero or two, if it is then interchange it with the first one, if it is a one continue iterating.
Here is the source code of the Java Program to Solve the Dutch National Flag Problem. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.
//Java Program to Solve the Dutch National Flag Problem
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class DutchNationalFlag {
// Function to solve the Dutch National Flag problem
static void dutchNationalFlag(int[] array){
int low,high,middle,temp;
low = middle = 0;
high = array.length-1;
while(middle<=high){
if(array[middle] == 0)
{
temp = array[low];
array[low] = array[middle];
array[mid] = temp;
low = low + 1;
middle = middle + 1;
}
else if(array[middle] == 1)
middle++;
else
{
temp = array[high];
array[high] = array[middle];
array[middle] = temp;
high = high - 1;
}
}
}
// Function to read input and display the output
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the size of the array");
try {
size = Integer.parseInt(br.readLine());
} catch (Exception e) {
System.out.println("Invalid Input");
return;
}
int[] array = new int[size];
System.out.println("Enter array elements");
int i;
for (i = 0; i < array.length; i++) {
try {
array[i] = Integer.parseInt(br.readLine());
} catch (Exception e) {
System.out.println("An error occurred");
return;
}
}
System.out.println("The initial array is");
for(i = 0;i < array.length; i++){
System.out.print(array[i] + " ");
}
dutchNationalFlag(array);
System.out.println("\nThe final array is");
for(i = 0;i < array.length; i++){
System.out.print(array[i] + " ");
}
}
}
1. In the function dutchNationalFlag(), we take three variables low, mid and high.
2. low and mid are initialized to zero, whereas high is initialized to array.length – 1.
3. Now using the loop while (mid <= high), we check the array elements at index mid, using a switch statement.
4. If the element is zero according to case 0, then we interchange the elements at index low and mid, and increment both low and mid.
5. If the element is one according to case 1, we increment mid.
6. Finally, if the element is two according to case 2, we swap the element at mid and high, along with decrementing high.
Time Complexity: O(n) where n is the number of elements in the array.
Case 1 (Simple test Case): Enter the size of the array 6 Enter array elements 1 0 2 2 0 1 The initial array is 1 0 2 2 0 1 The final array is 0 0 1 1 2 2 Case 2 (Simple test Case - another example): Enter the size of the array 8 Enter array elements 2 2 0 0 0 1 1 1 The initial array is 2 2 0 0 0 1 1 1 The final array is 0 0 0 1 1 1 2 2
Sanfoundry Global Education & Learning Series – Java Programs.
- Check Java Books
- Practice Programming MCQs
- Apply for Computer Science Internship
- Practice BCA MCQs
- Check Programming Books