forked from IamBisrutPyne/Java-Programs
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDutchNationalFlag.java
More file actions
62 lines (54 loc) · 1.78 KB
/
DutchNationalFlag.java
File metadata and controls
62 lines (54 loc) · 1.78 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
* Program Title: Dutch National Flag Sort
* Author: bmv126
* Date: 2025-10-13
*
* Description: Sorts an array containing only three distinct elements (0s, 1s, and 2s) in a single pass
* using the Dutch National Flag algorithm.
*
* Language: Java
*
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
import java.util.Arrays;
public class DutchNationalFlag {
/**
* Sorts an array of 0s, 1s, and 2s in a single pass using the DNF algorithm.
*/
public static void sort(int[] arr) {
int low = 0; // Pointer for the start of the 0s section
int mid = 0; // Pointer for the current element being processed
int high = arr.length - 1; // Pointer for the end of the 2s section
while (mid <= high) {
switch (arr[mid]) {
case 0:
// If the element is 0, swap it with 'low' pointer
swap(arr, low, mid);
low++;
mid++;
break;
case 1:
// If the element is 1, it's already in the middle position,
mid++;
break;
case 2:
// If the element is 2, swap it with 'high' pointer
swap(arr, mid, high);
high--;
break;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] array = {2, 0, 1, 2, 0, 1, 0, 2};
System.out.println("Original array: " + Arrays.toString(array));
sort(array);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}