flagi
FLAGA POLSKA ( sortowanie „0-1”)
Sortowanie „0-1” polega na podzieleniu tablicy na dwa rozłączne podzbiory wypełniające
cała przestrzeń danych. Podział ten odbywa się przy jednokrotnym przejrzeniu całej tablicy.
O każdym elemencie tablicy wiemy jednoznacznie, do którego zbioru należy.
Przy założeniu, że w tablicy występują tylko 0 i 1, po posortowaniu flagą polską na
początku mają stać zera, a na końcu jedynki. Równie dobrze może to być podział zbioru na kobiety
i mężczyzn, liczby parzyste i nieparzyste, itp.
Ma ono złożoność liniową, dlatego nie opłaca się stosować do takiego typu zadań
klasycznych algorytmów sortujących (np. insertsort, quicksort).
Idea algorytmu:
Zmienna lewy_koniec pokazuje na pierwszy element w tablicy;
Zmienna prawy_koniec pokazuje na ostatni element w tablicy;
Dopóki zmienna lewy_koniec jest mniejsza od zmiennej prawy_koniec wykonujemy
następujące działania:
szukamy pierwszej jedynki z lewej strony (stojącej nie na swoim miejscu) – wskazuje na
nią zmienna lewy_koniec;
szukamy pierwszego zera z prawej strony (stojącego nie na swoim miejscu) – wskazuje
na nią zmienna prawy_koniec;
jeżeli zmienna lewy_koniec jest mniejsza od prawy_koniec, to dokonujemy zamiany
elementów stojących na pozycjach, na które wskazują te zmienne;
Przykład 1
Dana jest tablica A. Posortować ją flagą polską tak, aby na początku stały zera, a na końcu jedynki.
Szukamy z lewej strony pierwszej 1, a z prawej pierwszego 0:
1
2
3
4
5
6
7
8
9
0
1
1
0
1
1
0
1
0
i=1 i=2 j=9
ponieważ i<j, więc:
zamieniamy element z pozycji i=2 z elementem z pozycji j=9
zwiększamy indeks i, zmniejszamy indeks j.
Po zamianie mamy:
1
2
3
4
5
6
7
8
9
0
0
1
0
1
1
0
1
1
i=3 j=8
