Repository: TheAlgorithms/Java
Pull request #3025 (2022-04-20 16:59:25)

Dutch national flag sort
### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

merges #3024
improves upon src/main/java/com/thealgorithms/sorts/DNFSort.java (might possibly replace it)

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.


BranAndSceolan: Thank you for reviewing. I have made the changes you requested.

Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/DutchNationalFlagSort.java b/src/main/java/com/thealgorithms/sorts/DutchNationalFlagSort.java
new file mode 100644
index 00000000..a2e32c2f
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/DutchNationalFlagSort.java
@@ -0,0 +1,44 @@
+package com.thealgorithms.sorts;
+
+/**
+ * The Dutch National Flag Sort sorts a sequence of values into three permutations which are defined by a value given
+ * as the indented middle.
+ * First permutation: values less than middle.
+ * Second permutation: values equal middle.
+ * Third permutation: values greater than middle.
+ * If no indented middle is given, this implementation will use a value from the given Array.
+ * This value is the one positioned in the arrays' middle if the arrays' length is odd.
+ * If the arrays' length is even, the value left to the middle will be used.
+ * More information and Pseudocode: https://en.wikipedia.org/wiki/Dutch_national_flag_problem
+ */
+public class DutchNationalFlagSort implements SortAlgorithm {
+
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
+        return dutch_national_flag_sort(unsorted, unsorted[(int) Math.ceil((unsorted.length)/2.0) -1]);
+    }
+
+    public <T extends Comparable<T>> T[] sort(T[] unsorted, T intendedMiddle) {
+        return dutch_national_flag_sort(unsorted, intendedMiddle);
+    }
+
+    private <T extends Comparable<T>> T[] dutch_national_flag_sort(T[] arr, T intendedMiddle){
+        int i = 0;
+        int j = 0;
+        int k = arr.length - 1;
+
+        while( j <= k){
+            if ( 0 > arr[j].compareTo(intendedMiddle)){
+                SortUtils.swap(arr, i, j);
+                j++;
+                i++;
+            } else if (0 < arr[j].compareTo(intendedMiddle)){
+                SortUtils.swap(arr, j, k);
+                k--;
+            } else {
+                j++;
+            }
+        }
+       return arr;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java b/src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java
new file mode 100644
index 00000000..56df1b35
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java
@@ -0,0 +1,112 @@
+package com.thealgorithms.sorts;
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+public class DutchNationalFlagSortTest {
+    @Test
+    /*
+      1 will be used as intended middle.
+      Partitions on the result array: [ smaller than 1 , equal 1, greater than 1]
+     */
+    void DNFSTestOdd() {
+        Integer[] integers = {1, 3, 1, 4, 0};
+        Integer[] integersResult = {0, 1, 1, 4, 3};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(integers);
+        assertArrayEquals(integers, integersResult);
+    }
+
+    @Test
+    /*
+      3 will be used as intended middle.
+      Partitions on the result array: [ smaller than 3 , equal 3, greater than 3]
+     */
+    void DNFSTestEven() {
+        Integer[] integers = {8, 1, 3, 1, 4, 0};
+        Integer[] integersResult = {0, 1, 1, 3, 4, 8};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(integers);
+        assertArrayEquals(integers, integersResult);
+    }
+
+    @Test
+    /*
+      "b" will be used as intended middle.
+      Partitions on the result array: [ smaller than b , equal b, greater than b]
+     */
+    void DNFSTestEvenStrings() {
+        String[] strings = {"a", "d", "b", "s", "e", "e"};
+        String[] stringsResult = {"a", "b", "s", "e", "e", "d"};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(strings);
+        assertArrayEquals(strings, stringsResult);
+    }
+
+    @Test
+    /*
+      "b" will be used as intended middle.
+      Partitions on the result array: [ smaller than b , equal b, greater than b]
+     */
+    void DNFSTestOddStrings() {
+        String[] strings = {"a", "d", "b", "s", "e"};
+        String[] stringsResult = {"a", "b", "s", "e", "d"};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(strings);
+        assertArrayEquals(strings, stringsResult);
+    }
+
+    @Test
+    /*
+      0 will be used as intended middle.
+      Partitions on the result array: [ smaller than 0 , equal 0, greater than 0]
+     */
+    void DNFSTestOddMidGiven() {
+        Integer[] integers = {1, 3, 1, 4, 0};
+        Integer[] integersResult = {0, 1, 4, 3, 1};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(integers, 0);
+        assertArrayEquals(integers, integersResult);
+    }
+
+    @Test
+    /*
+      4 will be used as intended middle.
+      Partitions on the result array: [ smaller than 4 , equal 4, greater than 4]
+     */
+    void DNFSTestEvenMidGiven() {
+        Integer[] integers = {8, 1, 3, 1, 4, 0};
+        Integer[] integersResult = {0, 1, 3, 1, 4, 8};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(integers, 4);
+        assertArrayEquals(integers, integersResult);
+    }
+
+    @Test
+    /*
+      "s" will be used as intended middle.
+      Partitions on the result array: [ smaller than s , equal s, greater than s]
+     */
+    void DNFSTestEvenStringsMidGiven() {
+        String[] strings = {"a", "d", "b", "s", "e", "e"};
+        String[] stringsResult = {"a", "d", "b", "e", "e", "s"};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(strings, "s");
+        assertArrayEquals(strings, stringsResult);
+    }
+
+    @Test
+    /*
+      "e" will be used as intended middle.
+      Partitions on the result array: [ smaller than e , equal e, greater than e]
+     */
+    void DNFSTestOddStringsMidGiven() {
+        String[] strings = {"a", "d", "b", "s", "e"};
+        String[] stringsResult = {"a", "d", "b", "e", "s"};
+        DutchNationalFlagSort dutchNationalFlagSort = new DutchNationalFlagSort();
+        dutchNationalFlagSort.sort(strings, "e");
+        assertArrayEquals(strings, stringsResult);
+    }
+}