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ść.
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.
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:
| Lista | Lewy | Prawy | Środek | Komentarz |
|---|---|---|---|---|
| RBWRRBWBB | 0 | 8 | 0 | zamiana 0 z 0 |
| RBWRRBWBB | 1 | 8 | 1 | zamiana 1 z 8 |
| RBWRRBWBB | 1 | 7 | 1 | zamiana 1 z 7 |
| RBWRRBWBB | 1 | 6 | 1 | zamiana 1 z 6 |
| RWWRRBBBB | 1 | 5 | 1 | zwiększamy środek |
| RWWRRBBBB | 1 | 5 | 2 | zwiększamy środek |
| RWWRRBBBB | 1 | 5 | 3 | zamiana 1 z 3 |
| RRWWRBBBB | 2 | 5 | 4 | zamiana 2 z 4 |
| RRRWWBBBB | 3 | 5 | 5 | zamiana 5 z 5 |
| RRRWWBBBB | 3 | 5 | 4 | - |
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.
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.
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.
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.
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.