...

/

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 Problem.

Solution #1: Brute force

Press + to interact
main.cpp
AuxiliaryFunctions.h
AuxiliaryFunctions.cpp
#include "AuxiliaryFunctions.h"
void selectionSort(int arr[], int size) {
int maxInd;
for (int i = 0; i < size; i++) {
maxInd = findMin(arr, i, size - 1); // findMin expects a start and end index so arrSize won't work
swap(arr[i], arr[maxInd]);
}
}
int main() {
int size = 6;
int arr[size] = {2, 0, 0, 1, 2, 1};
selectionSort(arr, size);
printArray(arr, size);
}

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 ...

Access this course and 1400+ top-rated courses and projects.