9. a. The Dutch national flag problem is to rearrange an array of characters R,

Question

9. a. The Dutch national flag problem is to rearrange an array of characters R, W, and B (red, white, and blue are the colors of the Dutch national flag) so that all the R?s come first, the W?s come next, and the B?s come last. [Dij76J Design a linear in-place algorithm for this problem. b. Explain how a solution to the Dutch national flag problem can be used in quicksort.

Explanation / Answer

#include Dutch_Flag(50) Func Dutch_Flag($arrayitems) Local $avArray[$arrayitems] For $i = 0 To UBound($avArray) - 1 $avArray[$i] = Random(1, 3, 1) Next Local $low = 2, $high = 3, $i = 0 Local $arraypos = -1 Local $p = UBound($avArray) - 1 While $i < $p if $avArray[$i] < $low Then $arraypos += 1 _ArraySwap($avArray[$i], $avArray[$arraypos]) $i += 1 ElseIf $avArray[$i] >= $high Then _ArraySwap($avArray[$i], $avArray[$p]) $p -= 1 Else $i += 1 EndIf WEnd _ArrayDisplay($avArray) EndFunc ;==>Dutch_Flag

Related Questions

Navigate

• Browse (All)
• Browse 9
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.