...

/

Solution: Dutch National Flag Problem

Solution: Dutch National Flag Problem

In this review lesson, we give a detailed analysis of the solutions for the Dutch national flag problem.

Solution #1: Brute force

Press + to interact
class DutchFlag {
//sorting in ascending order using selection sort
public static int[] selectionSort(int[] lst) {
int size = lst.length;
int index = 0;
for (int i = 0; i < size; i++) {
//finding the minimum value's index
index = find_min(lst, i, size);
//swapping it with current value
int temp = lst[i];
lst[i] = lst[index];
lst[index] = temp;
}
return lst;
}
//function to find the index of the minimum value
public 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 function
public 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.