Det nederlandske flaggets problem

Det nederlandske flaggets problem[1] er et programmeringsproblem innenfor informatikken som ble beskrevet av Edsger Dijkstra i 1976.[2] Nederlands flagg består av tre farger: rød, hvit og blå. Baller med disse tre fargene er ordnet tilfeldig på en linje (antall baller spiller ingen rolle), og oppgaven er å ordne disse ballene slik at baller med samme farge er sortert sammen slik at deres kollektive fargegruppe er i korrekt rekkefølge.

Det nederlandske flagget

Løsningen på problemet har interesse for konstruksjon av sorteringsalgoritmer. Varianter av quicksort som må være istand til å håndtere repeterende elementer, trenger en treveis partisjoneringsfunksjon som grupperer elementene i verdier mindre enn en gitt nøkkel (rød), verdier identisk med nøkkelen (hvit) og verdier større enn nøkkelen (blå), Flere løsninger eksisterer som har varierende ytelse, knyttet til om de sorterte tabellene har et mindre eller større antall av repeterende elementer.

Referanser rediger

  1. ^ «Dutch National Flag problem and algorithm». Faculty of Information Technology (Clayton), Monash University, Australia. 1998. 
  2. ^ Dijkstra, Edsger W. (1976): A Discipline of Programming, Prentice-Hall