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