Solution: Dutch National Flag Problem
In this review lesson, we give a detailed analysis of the solutions for the Dutch national flag problem.
We'll cover the following...
Solution #1: Brute force
Press + to interact
class DutchFlag {//sorting in ascending order using selection sortpublic static int[] selectionSort(int[] lst) {int size = lst.length;int index = 0;for (int i = 0; i < size; i++) {//finding the minimum value's indexindex = find_min(lst, i, size);//swapping it with current valueint temp = lst[i];lst[i] = lst[index];lst[index] = temp;}return lst;}//function to find the index of the minimum valuepublic static int find_min(int[] lst, int start, int end) {int min = lst[start];int index = start;for (int i = start; i < end; i++) {if (lst[i] < min) {min = lst[i];index = i;}}return index;}//driver functionpublic static void main(String args[]) {int[] arr = {2,0,0,1,2,1};System.out.println(Arrays.toString(selectionSort(arr)));}}
We have used simple selection sort to rearrange the array in ascending order. This method is naive and does not cater to the fact that we have just three different digits for this problem.
Time complexity
The time complexity is also too high, i.e. ...
Access this course and 1400+ top-rated courses and projects.