Det nederlandske flaggets problem

Det nederlandske flaggets problem er et programmeringsproblem innenfor informatikken som ble beskrevet av Edsger Dijkstra i 1976.Dijkstra, Edsger W. (1976): A Discipline of Programming, Prentice-Hall 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.

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

Kategori:Sorteringsalgoritmer