Home/Questions/Q 803893
Next
In Process

Quearn Latest Questions

codemania
  • 0
codemania
Asked: May 27, 20232023-05-27T09:39:32+00:00 2023-05-27T09:39:32+00:00In:

Dutch National Flag Problem in Java

  • 0
Dutch National Flag Problem in Java
codejava
Share

    1 Answer

    1. codemania
      codemania
      2023-05-27T09:40:05+00:00Added an answer on May 27, 2023 at 9:40 am

      This is the Java Program to Solve the Dutch National Flag Problem.

      Problem Description

      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]

      Problem Solution

      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.

      Program/Source Code

      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.

      2. //Java Program to Solve the Dutch National Flag Problem
      4. import java.io.BufferedReader;
      5. import java.io.InputStreamReader;
      7. public class DutchNationalFlag {
      8.     // Function to solve the Dutch National Flag problem
      9.     static void dutchNationalFlag(int[] array){
      10.         int low,high,middle,temp;
      11.         low = middle = 0;
      12.         high = array.length-1;
      13.         while(middle<=high){
      14.                 if(array[middle] == 0)
      15.                 {
      16.                     temp = array[low];
      17.                     array[low] = array[middle];
      18.                     array[mid] = temp;
      19.                     low = low + 1;
      20.                     middle  = middle + 1;
      21.                 }
      22.                 else if(array[middle] == 1)
      23.                     middle++;
      24.                 else
      25.                 {
      26.                     temp = array[high];
      27.                     array[high] = array[middle];
      28.                     array[middle] = temp;
      29.                     high = high - 1;
      30.                 }
      31.         }
      32.     }
      34.     // Function to read input and display the output
      35.     public static void main(String[] args) {
      36.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      37.         int size;
      38.         System.out.println("Enter the size of the array");
      39.         try {
      40.             size = Integer.parseInt(br.readLine());
      41.         } catch (Exception e) {
      42.             System.out.println("Invalid Input");
      43.             return;
      44.         }
      45.         int[] array = new int[size];
      46.         System.out.println("Enter array elements");
      47.         int i;
      48.         for (i = 0; i < array.length; i++) {
      49.             try {
      50.                 array[i] = Integer.parseInt(br.readLine());
      51.             } catch (Exception e) {
      52.                 System.out.println("An error occurred");
      53.                 return;
      54.             }
      55.         }
      56.         System.out.println("The initial array is");
      57.         for(i = 0;i < array.length; i++){
      58.             System.out.print(array[i] + " ");
      59.         }
      60.         dutchNationalFlag(array);
      61.         System.out.println("\nThe final array is");
      62.         for(i = 0;i < array.length; i++){
      63.             System.out.print(array[i] + " ");
      64.         }
      65.     }
      66. }
      Program Explanation
      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.
      Runtime Test Cases
       
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
      • 0
    You must login to add an answer.
    Need An Account, 
    Related Questions