Skip to content

Commit dfdce96

Browse files
BranAndSceolanAntonia Stracksiriak
authored
Add Dutch National Flag Sort (TheAlgorithms#3025)
Co-authored-by: Antonia Strack <antonia.strack@thm.mni.de> Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent 99ff516 commit dfdce96

File tree

2 files changed

+156
-0
lines changed

2 files changed

+156
-0
lines changed

‎src/main/java/com/thealgorithms/sorts/DutchNationalFlagSort.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.thealgorithms.sorts;
2+
3+
/**
4+
* The Dutch National Flag Sort sorts a sequence of values into three permutations which are defined by a value given
5+
* as the indented middle.
6+
* First permutation: values less than middle.
7+
* Second permutation: values equal middle.
8+
* Third permutation: values greater than middle.
9+
* If no indented middle is given, this implementation will use a value from the given Array.
10+
* This value is the one positioned in the arrays' middle if the arrays' length is odd.
11+
* If the arrays' length is even, the value left to the middle will be used.
12+
* More information and Pseudocode: https://en.wikipedia.org/wiki/Dutch_national_flag_problem
13+
*/
14+
public class DutchNationalFlagSort implements SortAlgorithm {
15+
16+
@Override
17+
public <T extends Comparable<T>> T[] sort(T[] unsorted) {
18+
return dutch_national_flag_sort(unsorted, unsorted[(int) Math.ceil((unsorted.length)/2.0) -1]);
19+
}
20+
21+
public <T extends Comparable<T>> T[] sort(T[] unsorted, T intendedMiddle) {
22+
return dutch_national_flag_sort(unsorted, intendedMiddle);
23+
}
24+
25+
private <T extends Comparable<T>> T[] dutch_national_flag_sort(T[] arr, T intendedMiddle){
26+
int i = 0;
27+
int j = 0;
28+
int k = arr.length - 1;
29+
30+
while( j <= k){
31+
if ( 0 > arr[j].compareTo(intendedMiddle)){
32+
SortUtils.swap(arr, i, j);
33+
j++;
34+
i++;
35+
} else if (0 < arr[j].compareTo(intendedMiddle)){
36+
SortUtils.swap(arr, j, k);
37+
k--;
38+
} else {
39+
j++;
40+
}
41+
}
42+
return arr;
43+
}
44+
}

‎src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
package com.thealgorithms.sorts;
2+
import org.junit.jupiter.api.Test;
3+
4+
import java.util.Arrays;
5+
6+
import static org.junit.jupiter.api.Assertions.*;
7+
8+
public class DutchNationalFlagSortTest {
9+
@Test
10+
/*
11+
1 will be used as intended middle.
12+
Partitions on the result array: [ smaller than 1 , equal 1, greater than 1]
13+
*/
14+
void DNFSTestOdd() {
15+
Integer[] integers = {1, 3, 1, 4, 0};
16+
Integer[] integersResult = {0, 1, 1, 4, 3};
17+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
18+
dutchNationalFlagSort.sort(integers);
19+
assertArrayEquals(integers, integersResult);
20+
}
21+
22+
@Test
23+
/*
24+
3 will be used as intended middle.
25+
Partitions on the result array: [ smaller than 3 , equal 3, greater than 3]
26+
*/
27+
void DNFSTestEven() {
28+
Integer[] integers = {8, 1, 3, 1, 4, 0};
29+
Integer[] integersResult = {0, 1, 1, 3, 4, 8};
30+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
31+
dutchNationalFlagSort.sort(integers);
32+
assertArrayEquals(integers, integersResult);
33+
}
34+
35+
@Test
36+
/*
37+
"b" will be used as intended middle.
38+
Partitions on the result array: [ smaller than b , equal b, greater than b]
39+
*/
40+
void DNFSTestEvenStrings() {
41+
String[] strings = {"a", "d", "b", "s", "e", "e"};
42+
String[] stringsResult = {"a", "b", "s", "e", "e", "d"};
43+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
44+
dutchNationalFlagSort.sort(strings);
45+
assertArrayEquals(strings, stringsResult);
46+
}
47+
48+
@Test
49+
/*
50+
"b" will be used as intended middle.
51+
Partitions on the result array: [ smaller than b , equal b, greater than b]
52+
*/
53+
void DNFSTestOddStrings() {
54+
String[] strings = {"a", "d", "b", "s", "e"};
55+
String[] stringsResult = {"a", "b", "s", "e", "d"};
56+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
57+
dutchNationalFlagSort.sort(strings);
58+
assertArrayEquals(strings, stringsResult);
59+
}
60+
61+
@Test
62+
/*
63+
0 will be used as intended middle.
64+
Partitions on the result array: [ smaller than 0 , equal 0, greater than 0]
65+
*/
66+
void DNFSTestOddMidGiven() {
67+
Integer[] integers = {1, 3, 1, 4, 0};
68+
Integer[] integersResult = {0, 1, 4, 3, 1};
69+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
70+
dutchNationalFlagSort.sort(integers, 0);
71+
assertArrayEquals(integers, integersResult);
72+
}
73+
74+
@Test
75+
/*
76+
4 will be used as intended middle.
77+
Partitions on the result array: [ smaller than 4 , equal 4, greater than 4]
78+
*/
79+
void DNFSTestEvenMidGiven() {
80+
Integer[] integers = {8, 1, 3, 1, 4, 0};
81+
Integer[] integersResult = {0, 1, 3, 1, 4, 8};
82+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
83+
dutchNationalFlagSort.sort(integers, 4);
84+
assertArrayEquals(integers, integersResult);
85+
}
86+
87+
@Test
88+
/*
89+
"s" will be used as intended middle.
90+
Partitions on the result array: [ smaller than s , equal s, greater than s]
91+
*/
92+
void DNFSTestEvenStringsMidGiven() {
93+
String[] strings = {"a", "d", "b", "s", "e", "e"};
94+
String[] stringsResult = {"a", "d", "b", "e", "e", "s"};
95+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
96+
dutchNationalFlagSort.sort(strings, "s");
97+
assertArrayEquals(strings, stringsResult);
98+
}
99+
100+
@Test
101+
/*
102+
"e" will be used as intended middle.
103+
Partitions on the result array: [ smaller than e , equal e, greater than e]
104+
*/
105+
void DNFSTestOddStringsMidGiven() {
106+
String[] strings = {"a", "d", "b", "s", "e"};
107+
String[] stringsResult = {"a", "d", "b", "e", "s"};
108+
DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
109+
dutchNationalFlagSort.sort(strings, "e");
110+
assertArrayEquals(strings, stringsResult);
111+
}
112+
}

0 commit comments

Comments
 (0)