An analysis of algorithms for the Dutch National Flag Problem
- 1 October 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 21 (10) , 842-846
- https://doi.org/10.1145/359619.359629
Abstract
Solutions to the Dutch National Flag Problem have been given by Dijkstra [1] and Meyer [3]. Dijkstra starts with a simple program and arrives at an improved program by refinement. Both of the algorithms given by Dijkstra are shown to have an expected number of swaps which is 2/3 N + θ(1) and that these values differ at most by 1/3 of a swap and asymptotically by 1/4 of a swap. The algorithm of Meyer is shown to have expected swap complexity 5/9 N .Keywords
This publication has 0 references indexed in Scilit: