Java Program to Sort an Array of 0's, 1's, and 2’s | Dutch National Flag Problem in Java

The famed Dutch computer programmer Edsger Dijkstra's Dutch Nation Flag (DNF) challenge ranks among the most well-known programming challenges. The Dutch tricolor flag, comprising red, white, and blue, is the inspiration for this flag, as its name suggests. To ensure that objects with the same color are grouped collectively, must distribute the red, white, and blue balls uniformly.

willThe will resolve mentioned issue through the use of an array. We shall arrange the arrays to match the hue of both the bolls. Rather than colors, we will utilize the numbers 0, 1, and 2, which stand in for the red, white, and blue hues.

Navie Methodology

Counting and sorting the arrays is a simple alternative. To sort these elements (0, 1, and 2), we tally how often they occur before placing them in the appropriate order. The method's drawback is that it scans the array twice: once to sort its components and again to arrange them properly.

To address the weakness above, we rearranged the arrangement to resolve the issue in a single traverse. The values are split into the three subgroups using an alternate linear-time division technique (also known as a 3-way division).

• Values (in red) below the pivot point.
• The center is equivalent to the numbers (white), and.
• The (blue) results exceed the midpoint.

Algorithm

three-way-partitioning technique(Arr : array of values, mid : value):  
   l ← 0 
   m← 0  
   n ← size of Arr - 1  
   while m<= n:  
       if A[m] < mid:  
           swap Arr[l] and Arr[m]  
           l ← l + 1  
           m ← m+ 1  
       else if Arr[m] > mid:  
           swap Arr[m] and A[n]  
           n ← n- 1  
       else:  
           m ← m+ 1

Java Program for dutch national flag problem

Example: NationalFlagOfDutch

// this program is for the dutch national flag challenge
//importing the packages
import java.util.Arrays;  
public class NationalFlagOfDutch  
{  
    // A linear time partitioning procedure is used to sort an array with 
    //the values 0, 1, and 2. It is comparable to the 3-way dividing solution for the Dutch national flag issue.  
    public static void threeWayPartitions(int[] Arr)  
    {  
        int starts = 0, mids= 0;  
        int pivots = 1;  
        int ends = Arr.length - 1;  
        while (mids <= ends)  
        {  
            if (Arr[mids] < pivots)         // checks for the current position element  
            {  
                swaps(Arr, starts, mids);  
                ++starts;  
                ++mids;  
            }  
            else if (Arr[mids] > pivots)    //  check the current element is 2 or not  
            {  
                swaps(Arr, mids, ends);  
                --ends;  
            }  
            else {                      //  check the current element is 1
                ++mids;  
            }  
        }  
    }   
    //Convenience method to switch the arra's parts Arr[i] and Arr[j]  
    private static void swaps(int[] Arr, int i, int j)  
    {  
        int temps = Arr[i];  
        Arr[i] = Arr[j];  
        Arr[j] = temps;  
    }  
// the main section of the program
    public static void main (String args[])  
    {  
    // the array for sorting the elements 
        int[] Arr = { 0,2,0,2,0,0,1,1};  
   
        threeWayPartitions(Arr);  
    // displaying the sorted array
        System.out.println(Arrays.toString(Arr));  
    }  
}  

Output

[0, 0, 0, 0, 0, 1, 1, 2, 2]

Example2: DutchNationalFlagProblem.java

// this program is for the dutch national flag challenge
//importing the packages
import java.io.*;   
public class DutchNationalFlagProblem   
{   
    static void DNF(int array[], int arr_sizes)   
    {   
        int lows = 0;   
        int hig = arr_sizes - 1;   
        int mids = 0, temps=0; // For switching, temp variables are utilised.
        while (mids <= hig)   
        {   
            switch (array[mids])   
            {   
        case 0: // if indeed the midpointer is at 0,
        {   
        // logic for the swapping      
          temps = array[lows];   
          array[lows] = array[mids];   
          array[mids] = temps;   
          lows++;   
          mids++;   
          break;   
        }   
        case 1: 
            //If the midpoint is at 1, nothing switching is needed; increase your midpointer.
          mids++;   
          break;   
        case 2: // condition for mid pointer
        {   
        //logic for swapping   
          temps = array[mids];   
          array[mids] = array[hig];   
          array[hig] = temps;   
          hig--;   
          break;   
        }   
            }   
        }   
    }   
    // the method for displaying the sorted and unsorted array  
    static void printArray(int array[], int arr_sizes)   
    {   
        int i;   
        // loop for iterating the array  
        for (i = 0; i < arr_sizes; i++)   
        // displaying the elements
            System.out.print(array[i]+" ");   
            // the space is printed  
        System.out.println("");   
    }   
     // the main section of the program  
    public static void main (String args[])   
    {   
        int array[] = {0, 2, 1, 1, 0, 1, 2};   
        //identifies the element's length  
        int arr_sizes = array.length;   
    System.out.println(" The array before the sorting method: ");   
        printArray(array, arr_sizes);   
        // the method for calling before sorting
    DNF(array, arr_sizes);   
    // displaying the sorted array
    System.out.println(" The array after the sorting method: ");   
    // the function can be called after the sorting
        printArray(array, arr_sizes);   
    }   
}  

Output

 The array before the sorting  method: 
0 2 1 1 0 1 2 
 The array after the sorting method: 
0 0 1 1 1 2 2