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

flagi

Dalej znowu szukamy z lewej strony pierwszej 1, a z prawej pierwszego 0:

1

2

3

4

5

6

7

8

9

0

0

1

0

1

1

0

1

1

i=3 j=7 j=8

ponieważ i<j, więc:

zamieniamy element z pozycji i=3 z elementem z pozycji j=7
zwiększamy indeks i, zmniejszamy indeks j:

Po zamianie mamy:

1

2

3

4

5

6

7

8

9

0

0

0

0

1

1

1

1

1

i=4 j=6

Dalej znowu szukamy z lewej strony pierwszej 1, a z prawej pierwszego 0:

1

2

3

4

5

6

7

8

9

0

0

0

0

1

1

1

1

1

i=4 i=5

j=5 j=6

Algorytm zakończy działanie, gdyż i>=j. Tablica jest już posortowana.

FLAGA FRANCUSKA ( sortowanie „0-1-2”)

Sortowanie „0-1-2” polega na podzieleniu tablicy na trzy 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, 1 i 2, po posortowaniu flagą francuską na

początku mają stać zera, następnie jedynki, a na końcu dwójki.

Ma ono złożoność liniową, dlatego nie opłaca się stosować do takiego typu zadań

klasycznych algorytmów sortujących (np. insertsort, quicksort).