Dutch National Flag Problem in Java
Dutch National Flag (DNF) is a programming issue that Edsger Dijkstra put up. The white, red, and blue hues make up the Dutch flag. The goal is to haphazardly set white, red, and blue balls, so they are grouped according to color. We sort an array of 0, 1, and 2 values for the DNF (Dutch National Flag) in linear time without using any additional storage. Remember that this approach can only be used on an array with three distinct entries.
Algorithm
- Take three-pointers, specifically low, mid, and high.
- The beginning of the array is pointed to by the low and mid pointers, while the high pointer points to the end of the array.
- If array [mid] = 0, swap array [mid] for array [low], then increase both pointers by one.
- There is no need for swapping if array [mid] = 1. Mid pointer once increased.
- If array [mid] equals 2, then array [mid] and array [high] is switched, and the high pointer is decremented once.
Problem Statement
Given a 3-dimensional array A[] that only contains 0s, 1s, and 2s. You must create a method that sorts the supplied array. The functions should order all 0s first, followed by all 1s, and then all 2s.
Example 1
Input: {0, 1, 1,2, 0, 1, 2}
Output: {0, 0, 1, 1, 1,2,2}
Example 2
Input: {0, 1, 0, 1, 2, 1, 2, 0, 0, 1,2}
Output: {0, 0, 0, 0, 1, 1, 1, 1, 2, 2,2}
Using Pointers
Algorithm
- Three colors were used to present the issue in this case, "0," "1," and "2." Four components make up the array: arr[1] to arr[low - 1]
- arr[low ]to arr[low] to arr[mid – 1]
- arr[mid] to (high – 1),
- Swap the element to the low range if the ith element is 0.
- In a similar vein, if the element is 1, leave it alone.
- If the element is 2, replace it with a high-range element.
Explanation
- There are four ranges: 0 to low (the range of 0), 1 to low (the range of 1), 1 to mid (the range of 1), 0 to high (the range of unknown objects), and 0 to high (the range of N). Keep three indices, with low equaling 1 and high equaling 1. (the range containing 2s). From beginning to finish of the array, mid is less than high.
- When updating low = low + 1 and mid = mid + 1, swap the element with the element at index low if the element is 0.
- Update mid = mid + 1 when the element is 1.
File Name: DutchNationalFlag.java
import java.io.*;
class DutchNationalFlag
{
// Sorting the input array
static void sort(int a[], int size)
{
// integer variable to store low value
int lo = 0;
int hi = size - 1;
int mid = 0, temp = 0;
// iterate through the array
while (mid <= hi) {
switch (a[mid]) {
// If the array element is 0
case 0: {
temp = a[lo];
a[lo] = a[mid];
a[mid] = temp;
lo++;
mid++;
break;
}
// If the array element is 1
case 1:
mid++;
break;
// If the array element is 2
case 2: {
temp = a[mid];
a[mid] = a[hi];
a[hi] = temp;
hi--;
break;
}
}
}
for (int i = 0; i < size; i++)
System.out.print(a[i] + " ");
System.out.println("");
}
// Main section of the program where execution starts
public static void main(String [] s)
{
Scanner sc= new Scanner(System.in);
System.out.println("Enter size of the array");
int n=sc.nextInt();
int a[]=new int[n];
System.out.println("Enter array elements");
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
System.out.println("The original array is ");
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
// finding the length of the array
int size = a.length;
System.out.println();
System.out.println("The array after sorting is ");
// calling the sort function
sort(a,size);
}
}
Output
Enter size of the array
10
Enter array elements
0 1 0 2 1 2 0 1 0 2
The original array is
0 1 0 2 1 2 0 1 0 2
The array after sorting is
0 0 0 0 1 1 1 2 2 2
Complexity Analysis
Time Complexity: O(n), the array only needs to be traversed once.
Space Complexity: O(1) because no more space is needed.
Method 2
Algorithm
procedure three-way-partition(A : array of values, mid : value):
i ← 0
j ← 0
k ← size of A - 1
while j <= k:
if A[j] < mid:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
else if A[j] > mid:
swap A[j] and A[k]
k ← k - 1
else:
j ← j + 1
Explanation
Three variables—low, mid, and high are used in the program. The three situations are:
Swap array[mid] and array[low] and increase both pointers by one if array[mid]=0.
If array[mid]=1, no swapping is done, but the mid pointer is increased.
If array[mid]=2 then array[high] is swapped for array[mid], and the high pointer is decreased by one.
DutchNationalFlag2.java
import java.util.Arrays;
import java.util.*;
public class DutchNationalFlag2
{
// sort an array containing 0, 1, and 2.
public static void Partition(int[] Arr)
{
// s indicates the first index
// mid is the mid value of first and last index
int s = 0, mid = 0;
int pivot = 1;
// finding last index value
int end = Arr.length - 1;
// we traverse the loop until the mid value is less than or equal to last value
while (mid <= end)
{
// if current array element is 0
if (Arr[mid] < pivot)
{
swap(Arr, s, mid);
++s;
++mid;
}
// if current array element is 2
else if (Arr[mid] > pivot)
{
swap(Arr, mid, end);
--end;
}
// if current array element is 1
else {
++mid;
}
}
}
// function swap to swap the elements at index i and j
private static void swap(int[] A, int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// Main section of the program from where execution begins
public static void main (String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array ");
// storing the size of the array into variable n
int n=sc.nextInt();
// array declaration
int a[]=new int [n];
System.out.println("Enter array elements");
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
// calling the function Partition by passing array as parameter
Partition(a);
//prints sorted array
System.out.println(Arrays.toString(a));
}
}
Output
enter the size of the array
7
Enter array elements
1 2 0 1 2 1 0
[0, 0, 1, 1, 1, 2, 2]
By using quicksort
DutchNationalFlag3.java
import java.util.*;
class DutchNationalFlag3
{
static int i, j;
static void partition(int a[], int l, int r)
{
i = l - 1; j = r;
int p = l - 1, q = r;
int v = a[r];
while (true)
{
while (a[++i] < v)
;
while (v < a[--j])
if (j == l)
break;
if (i >= j)
break;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
if (a[i] == v) {
p++;
temp = a[i];
a[i] = a[p];
a[p] = temp;
}
if (a[j] == v) {
q--;
temp = a[q];
a[q] = a[j];
a[j] = temp;
}
}
int temp = a[i];
a[i] = a[r];
a[r] = temp;
j = i - 1;
for (int k = l; k < p; k++, j--)
{
temp = a[k];
a[k] = a[j];
a[j] = temp;
}
i = i + 1;
for (int k = r - 1; k > q; k--, i++)
{
temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
static void quicksort(int arr[], int l, int r)
{
if (r <= l)
return;
i = 0; j = 0;
partition(arr, l, r);
quicksort(arr, l, j);
quicksort(arr, i, r);
}
static void printarr(int a[], int n)
{
for (int j = 0; j < n; ++j)
System.out.printf("%d ", a[j]);
System.out.printf("\n");
}
public static void main(String[] s)
{
int arr[] = { 0,1,2,1,2,0,1,2,0,1};
int length = arr.length;
System.out.println("The original array is ");
printarr(arr, length);
quicksort(arr, 0, length - 1);
System.out.println("After sorting the array is ");
printarr(arr, length);
}
}
Output
The original array is
0 1 2 1 2 0 1 2 0 1
After sorting the array is
0 0 0 1 1 1 1 2 2 2
Complexity Analysis
Time Complexity
O(N * log(N)) is the time complexity.
Space Complexity
The complexity of Space: O (log N)
where "N" is the array or list's element count.