Strona główna » Algorytmy » Artykuły » Problem Flagi Holenderskiej
 

Problem Flagi Holenderskiej

Cel

Holenderska flaga składa się z koloru czerwonego, białego i niebieskiego. E. Dijkstra przedstawił problem informatyczny w myśl którego uznajmy, że flaga składa się z kolorowych kulek, ale zostały one wymieszane. Zadanie polega na tym, aby umieścić ten sam kolor koło siebie i w odpowiedniej kolejności. Algorytm rozwiązujący to zadanie działa ze złożonością liniową, ale istnieje wiele różnych algorytmów to realizujące. Nie wszystkie mają identyczną efektywność.

Algorytm

Na wejściu program otrzymuje listę kolorów kulek, które zostały pomieszane. Oznaczmy sobie każdą kulkę poprzez literkę koloru na jaki jest pomalowana. Przyjmijmy, że kulki mogą być: R - czerwone, W - białe oraz B - niebieskie. Algorytm polega na tym, aby przeglądać elementy od lewej do prawej. W każdym kroku podejmujemy decyzję z którym elementem zamienić aktualnie przeglądany element. Jeśli jest to kulka R to przeniesiemy ją na początek, a jeśli B to na koniec. Po każdym takim odłożeniu zmieniamy zakres indeksów jeszcze nie posortowanej tablicy. W przypadku natrafienia na wartość, która powinna znaleźć się pośrodku to nie wykonujemy żadnej zamiany. Kolejne elementy porównujemy dopóki nie wyjdziemy poza zakres nieposortowanej tablicy.

Przykład

Weźmy przykładowo tablicę kolorów {R, B, W, R, R, B, W, B, B}. Sortujemy elementy tak, aby na początku była grupa R potem W, a na koniec B. Początkowo zakres sięga od pierwszego elementu o indeksie 0 do ostatniego o indeksie równym długości tablicy pomniejszonym o jeden. Środkowy element to na początku pierwszy od lewej. Kolejno wykonujemy:

ListaLewyPrawyŚrodekKomentarz
RBWRRBWBB080zamiana 0 z 0
RBWRRBWBB181zamiana 1 z 8
RBWRRBWBB171zamiana 1 z 7
RBWRRBWBB161zamiana 1 z 6
RWWRRBBBB151zwiększamy środek
RWWRRBBBB152zwiększamy środek
RWWRRBBBB153zamiana 1 z 3
RRWWRBBBB254zamiana 2 z 4
RRRWWBBBB355zamiana 5 z 5
RRRWWBBBB354-

Na koniec otrzymujemy posortowane elementy jako ciąg znaków "RRRWWBBBB". Takie same elementy są koło siebie i wszystkie grupy występują w kolejności ustalonej na początku przykładu.

Implementacja

Funkcja sortująca sortujRWB() będzie przyjmować jedynie ciąg znaków, która ma zostać posortowany. Zakłada się, że wprowadzone dane są poprawne.

C++
C#
  1. void sortujRWB(char* tab) {
  2.   int lewy = 0;
  3.   int prawy = strlen(tab) - 1;
  4.   int srodek = 0;
  5.   while (srodek <= prawy) {
  6.     if (tab[srodek] == 'R') {
  7.       swap(tab[lewy++], tab[srodek++]);
  8.     } else if (tab[srodek] == 'B') {
  9.       swap(tab[srodek], tab[prawy--]);
  10.     } else {
  11.       srodek++;
  12.     }
  13.   }
  14. }

Algorytm początkowo ustala zakres (2.) "od" indeksu 0 (3.) "do" do indeksu ostatniego elementu w tablicy, a następnie (4.) środek zapisu. Mogą istnieć elementy do zamiany jeśli (5.) środek zapisu jest mniejszy, równy zakresowi "do". W każdym powtórzeniu (6.) jeśli element należy do grupy R to (7.) zamieniamy aktualny element z elementem w zakresie "od". Jeśli jednak należy do (8.) ostatniej grupy to zamieniamy z zakresem "do". Jeśli jednak jest to grupa środkowa to (10.) należy zwiększyć pozycję aktualnie rozpatrywanego elementu.

Testowanie funkcji

Przedstawiony poniżej kod wczyta od użytkownika ciąg znaków złożony z znaków R, W oraz B, a następnie wypisze na ekran posortowane dane tak, aby kolejno występowały znaki R potem W, a potem B.

C++
C#
  1. int main() {
  2.   char* tab = new char[512];
  3.   cout << "Podaj kolejne kolory kulek (maks. 511)" << endl;
  4.   cout << "R - czerwona, W - biala, B - niebieska" << endl;
  5.   cin.getline(tab, 512);
  6.   sortujRWB(tab);
  7.   cout << "\nPo posortowaniu otrzymamy:\n" << tab << endl;
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz program, który pozwoli na grupowanie liczb. Program wczyta od użytkownika n całkowitych oraz wartowników w1 oraz w2. W pierwszej części listy mają znaleźć się wartości x < w1, w drugiej w1 ≤ x < w2, a w trzeciej w2 ≤ x.

Przykładowo jeśli zostanie wprowadzona tablica liczb całkowitych L := {9, 5, 1, 2, 8, 6, 3, 4, 7} oraz strażników w1 = 4 oraz w2 = 7 to program powinien wypisać "1, 2, 3, 5, 4, 6, 8, 7, 9". Pierwsza grupa to liczby mniejsze od 4, więc jest to podlista {1, 2, 3}. Potem druga zawiera się od 4 do 6 czyli {5, 4, 6}, a ostatnia to {8, 7, 9} czyli liczby większe od w2 = 7.