Question

Edsger Dijkstra studied the following problem which he called the Problem of the Dutch National Flag. We are given an array of pebbles, some blue, some red, some white. We want to rearrange them in the order of the Dutch flag, that is, first come the red, then the white, and finally the blue pebbles. Which sorting method is best suited for this task, that is, most efficient?

Group of answer choices

Heapsort

Insertion sort

Mergesort

Quicksort

Selection sort

Shellsort

Sorting by counting

Answer 1

For this problem Dutch National Flag the best sorting algorithm is :

Quicksort

Reason:

Sort an Array of Three Color Balls.We have N balls of three unique sorts: red(r), blue(b), and white(w). I have to sort them so red balls seem firsts, at that point every white ball lastly all blue balls.

In basic QuickSort calculation, we select an element as pivot, segment the cluster around turn Given an exhibit and a range [lowVal, highVal], segment the exhibit around the range with the end goal that cluster is isolated in three sections.
1) All elements littler than lowVal start things out.
2) All elements in extend lowVal to highVal come straightaway.
3) All elements more prominent than highVal show up at long last.
The individual elements of three sets can show up in any.

The complexity for solving this problem is :

• Time complexity = O(n)
• Space complexity = O(1)

Thank you...........