Algorytmy sortowania

autor - Ewa Dadacz

1. Sortowanie bąbelkowe - bubble sort

1. Opis działania algorytmu

Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

2. Sposoby zapisu algorytmu

Lista kroków

dane wejściowe

n	- liczba elementów w sortowanym zbiorze, n N,
d[]	- zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

dane wyjściowe

d[]	- posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

zmienne pomocnicze

i, j	- zmienne sterujące pętli; i, j N.

lista kroków

K01:	dla j = 1,2,...,n-1: wykonuj K02
K02:	dla i = 1,2,...,n-1: jeśli d[i]>d[i+1], to d[i]↔d[i+1]
K03:	Zakończ

Schemat blokowy

Rys. 2.1. Schemat blokowy algorytmu sortowania bąbelkowego

 

Kod źródłowy algorytmu

Algorytm sortowania bąbelkowego napisany w języku Pascal:

for j := 1 to n - 1 do

for i := 1 to n - 1 do

if d[i] > d[i+1] then // porządek rosnący

begin

x := d[i]; d[i] := d[i+1]; d[i+1] := x;

end;

2. Sortowanie przez wybór - selection sort

1. Opis działania algorytmu

Idea algorytmu sortowania przez wybór jest prosta. Chcąc posortować n - elementowy zbiór liczbowy rosnąco, element najmniejszy powinien znaleźć się na pierwszej pozycji. W zbiorze wyszukiwany jest element najmniejszy i zamieniany z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji. Ponownie, ale już spośród n-1 elementów wyszukiwany jest element najmniejszy i zamieniany z elementem na drugiej pozycji. W wyniku tej operacji dwa pierwsze elementy będą posortowane. Aby posortować resztę elementów, należy kontynuować procedurę dotąd, aż wszystkie będą w odpowiednim porządku.

2. Sposoby zapisu algorytmu

Lista kroków

dane wejściowe

n	- liczba elementów w sortowanym zbiorze, n N,
d[]	- zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

dane wyjściowe

d[]	- posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

zmienne pomocnicze

i, j	- zmienne sterujące pętli; i, j N.
pmin	- pozycja elementu minimalnego w zbiorze d[ ], pmin N.

lista kroków

K01:	dla j = 1,2,...,n-1 wykonuj K02...K04
K02:	pmin ← j
K03:	dla i = j+1, j+2,..., n jeśli d[i]<d[pmin], to pmin ← i
K04:	d[j] ↔ d[pmin]
K05:	Zakończ

Schemat blokowy

Rys. 3.1. Schemat blokowy algorytmu sortowania przez wybór

  

Pętla zewnętrzna sterowana zmienną j wyznacza kolejne elementy zbioru o indeksach od 1 do n-1, w których zostaną umieszczone elementy minimalne. Na początku tej pętli należy założyć, iż elementem minimalnym jest element d[j] i zapamiętać jego indeks w zmiennej p_min.

W pętli numer 2 sterowanej zmienną i porównywane są pozostałe elementy zbioru z elementem d[p_min]. Jeśli element zbioru d[i] jest mniejszy od elementu d[p_min], to należy zapamiętać jego pozycję w p_min i kontynuować pętlę wewnętrzną.

Po zakończeniu pętli wewnętrznej p_min zawiera indeks elementu minimalnego. Element d[j] zamieniany jest miejscami z elementem d[p_min]. Dzięki tej operacji element minimalny znajduje się na swojej docelowej pozycji. Przechodząc do kolejnego elementu zbioru wartość zmiennej j zwiększa się i kontynuowana jest pętla zewnętrzna.

Kod źródłowy algorytmu

for j := 1 to n - 1 do

begin

p_min := j;

for i := j + 1 to n do

if d[i] < d[p_min] then p_min := i;

x := d[p_min]; d[p_min] := d[j]; d[j] := x;

end;

3. Sortowanie przez wstawianie - insertion sort

1. Opis działania algorytmu

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw pobierana jest pierwsza karta. Następnie pobiera się kolejne, aż do wyczerpania talii. Każda pobrana karta porównywana jest z kartami, które już pobrano i wyszukiwane jest dla niej miejsce przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy takie miejsce istnieje, karty są rozsuwane i nową karta wstawiana jest na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. Insertion Sort). Jeśli karta jest najstarsza (najmłodsza), to umieszczana jest na samym końcu. Tak porządkowane są karty.

Algorytm sortowania przez wstawianie będzie składał się z dwóch pętli. Pętla główna (zewnętrzna) symuluje pobieranie kart, czyli w tym wypadku elementów zbioru. Odpowiednikiem kart na ręce jest tzw. lista uporządkowana (ang. sorted list), która sukcesywnie będzie tworzona na końcu zbioru (istnieje też odmiana algorytmu umieszczająca listę uporządkowaną na początku zbioru). Pętla sortująca (wewnętrzna) służy do wyszukiwania dla pobranego elementu miejsca na liście uporządkowanej. Jeśli takie miejsce zostanie znalezione, to elementy listy są odpowiednio rozsuwane, aby tworzyć miejsce na nowy element i element wybrany przez pętlę główną trafia tam. W ten sposób lista uporządkowana rozrasta się. Jeśli na liście uporządkowanej nie ma elementu większego od wybranego, to element ten trafia na koniec listy. Sortowanie zakończy się, gdy pętla główna wybierze wszystkie elementy zbioru.

Najważniejszą operacją w opisywanym algorytmie sortowania jest wstawianie wybranego elementu na listę uporządkowaną. Zasady są następujące:

1. Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni element zbioru. Jednoelementowa lista jest zawsze uporządkowana.

2. Ze zbioru zawsze wybierany jest element leżący tuż przed listą uporządkowaną. Element ten zapamiętywany jest w zewnętrznej zmiennej. Miejsce, które zajmował, można potraktować jak puste.

3. Wybrany element porównywany jest z kolejnymi elementami listy uporządkowanej.

4. Jeśli osiągnięty jest koniec listy, element wybrany wstawiany jest na puste miejsce - lista rozrasta się o nowy element.

5. Jeśli element listy jest większy od wybranego, to element wybrany wstawiany jest na puste miejsce - lista rozrasta się o nowy element.

6. Jeśli element listy nie jest większy od wybranego, to element listy przesuwa się na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Porównywanie jest kontynuowane, aż wystąpi sytuacja z punktu 4 lub 5.

1. Sposoby zapisu algorytmu

Lista kroków

dane wejściowe

n	- liczba elementów w sortowanym zbiorze, n N,
d[]	- zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

dane wyjściowe

d[]	- posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

zmienne pomocnicze

i, j	- zmienne sterujące pętli; i, j N.
x	- zawiera wybrany ze zbioru element.

lista kroków

K01:	dla j = n-1, n-2,..., 1: wykonuj K02...K04
K02:	x←d[j]; i←j+1
K03:	dopóki (i≤n) and (x>d[i]): wykonuj d[i-1]←d[i]; i←i+1
K04:	d[i-1]←x
K05:	Zakończ

Schemat blokowy

Rys. 4.1. Schemat blokowy algorytmu sortowania przez wstawianie

Pętla główna rozpoczyna się od przedostatniej pozycji w zbiorze. Element na ostatniej pozycji jest zalążkiem listy uporządkowanej. Dlatego licznik pętli nr 1 przyjmuje wartość początkową j = n-1.

Ze zbioru wybierany jest element d[j] i umieszczony w zmiennej pomocniczej x. Miejsce zajmowane przez ten element staje się puste. W rzeczywistości na pozycji j pozostaje dalej ten sam element. Jednakże jego wartość jest zapamiętana, zatem pozycja ta może być zapisana inną informacją - element nie zostanie utracony, ponieważ przechowuje go zmienna x. Dlatego pozycję tę można potraktować jako pustą, tzn. z nieistotną zawartością.

Pętla wewnętrzna rozpoczyna się od pozycji następnej w stosunku do j. Pozycja ta zawiera pierwszy element listy uporządkowanej, która tworzona jest na końcu sortowanego zbioru. Pętla wewnętrzna przerywana jest w dwóch przypadkach - gdy licznik pętli wyjdzie poza indeks ostatniego elementu w zbiorze lub gdy element wybrany, przechowywany w zmiennej pomocniczej x, jest mniejszy lub równy bieżąco testowanemu elementowi listy uporządkowanej (dla sortowania malejącego należy zastosować w tym miejscu relację większy lub równy). W obu przypadkach na puste miejsce ma trafić zawartość zmiennej x i pętla zewnętrzna jest kontynuowana. Pozycja tego miejsca w zbiorze jest równa i-1.

Jeśli żaden z warunków przerwania pętli wewnętrznej nr 2 nie wystąpi, to bieżący element listy przesuwany jest na puste miejsce i pętla wewnętrzna jest kontynuowana.

Podsumowując: pętla zewnętrzna wybiera ze zbioru kolejne elementy o indeksach od n-1 do 1, pętla wewnętrzna szuka dla wybranych elementów miejsca wstawienia na liście uporządkowanej, po znalezieniu którego pętla zewnętrzna wstawia wybrany element na listę. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od n-1 do 1, zbiór będzie posortowany.

Kod źródłowy algorytmu

Algorytm sortowania przez wstawianie napisany w języku Pascal:

for j := n - 1 downto 1 do

begin

x := d[j];

i := j + 1;

while (i <= n) and (x > d[i]) do

begin

d[i - 1] := d[i];

inc(i);

end;

d[i - 1] := x;

end;

4. Sortowanie szybkie - quick sort

1. Opis działania algorytmu

Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:

• DZIEL - problem główny zostaje podzielony na podproblemy,

• ZWYCIĘŻAJ - znajdowane jest rozwiązanie podproblemów,

• POŁĄCZ - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego.

Opis poszczególnych etapów algorytmu quicksort przedstawiono w tabeli:

DZIEL	Najpierw sortowany zbiór dzielony jest na dwie części w taki sposób, aby wszystkie elementy leżące w pierwszej części (zwanej lewą partycją) były mniejsze lub równe od wszystkich elementów drugiej części zbioru (zwanej prawą partycją).
ZWYCIĘŻAJ	Każda z partycji sortowana jest rekurencyjnie tym samym algorytmem.
POŁĄCZ	Połączenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany.

Sortowanie szybkie zostało wynalezione przez angielskiego informatyka, profesora Toniego Hoare'a w latach 60-tych ubiegłego wieku. W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(nlog(n)) - stąd pochodzi jego popularność w zastosowaniach. Należy jednak pamiętać, iż w pewnych sytuacjach (np. niekorzystnego ułożenia danych wejściowych) klasa złożoności obliczeniowej tego algorytmu może się degradować do O(n²). Co więcej, poziom wywołań rekurencyjnych może spowodować przepełnienie stosu i zablokowanie komputera. Z tych powodów algorytmu sortowania szybkiego nie można stosować bezmyślnie w każdej sytuacji tylko dlatego, iż jest uważany za jeden z najszybszych algorytmów sortujących - zawsze należy przeprowadzić analizę możliwych danych wejściowych pod kątem przypadku niekorzystnego.

Tworzenie partycji

Do utworzenia partycji należy ze zbioru wybrać jeden z elementów, który przykładowo otrzyma nazwę piwot. W lewej partycji znajdą się wszystkie elementy niewiększe, a w prawej partycji - wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem mogą one występować w obu partycjach. Również porządek elementów w każdej z partycji nie jest ustalony.

Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Przykładowo, wybierany jest element środkowy:

piwot ← d[(lewy+prawy)div2]

gdzie:

piwot	- element podziałowy
d[]	- dzielony zbiór
lewy	- indeks pierwszego elementu
prawy	- indeks ostatniego elementu

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku zbioru - i oraz j. Wskaźnik i przebiega przez zbiór poszukując wartości mniejszych od piwotu. Po znalezieniu takiej wartości jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaźnik j jest przesuwany na następną pozycję. Wskaźnik j zapamiętuje pozycję, na którą trafi następny element oraz na końcu wskazuje miejsce, gdzie znajdzie się piwot. W trakcie podziału piwot jest przechowywany na ostatniej pozycji w zbiorze.

1. Sposoby zapisu algorytmu

Lista kroków

Sortuj_szybko(lewy, prawy)

dane wejściowe

d[]	- zbiór zawierający elementy do posortowania; zakres indeksów elementów jest dowolny
lewy	- indeks pierwszego elementu w zbiorze, lewy C
prawy	- indeks ostatniego elementu w zbiorze, prawy C

dane wyjściowe

d[]	- posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

zmienne pomocnicze

i, j	- zmienne sterujące pętli; i, j N.
piwot	- element podziałowy.

lista kroków

i ← [

lewy+prawy

]

2

K01:
K02:	piwot ← d[i]; d[i] ← d[prawy]; j ← lewy
K03:	Dla i = lewy, lewy +1, ..., prawy-1: wykonuj K04...K05
K04:	Jeśli d[i]≥piwot, to wykonaj kolejny obieg pętli K03
K05:	d[i] ↔ d[j];  j ← j+1
K06:	d[prawy] ← d[j]; d[j] ← piwot
K07:	Jeśli lewy<j-1, to Sortuj_szybko(lewy, j-1)
K08:	Jeśli j+1<prawy, to Sortuj_szybko(j+1, prawy)
K09:	Zakończ

 

Algorytm sortowania szybkiego wywołuje się podając za lewy indeks pierwszego elementu zbioru, a za prawy indeks elementu ostatniego (czyli Sortuj_szybko(1,n)). Zakres indeksów jest dowolny - dzięki temu ten sam algorytm może również sortować fragment zbioru, co wykorzystujemy przy sortowaniu wyliczonych partycji.

Schemat blokowy

Rys. 5.1. Schemat blokowy algorytmu sortowania szybkiego

Na element podziałowy wybiera się element leżący w środku dzielonej partycji. Wyliczana jest jego pozycja i zapamiętana tymczasowo w zmiennej i. Element d[i] zapamiętany jest w zmiennej piwot, a do d[i] zapisywany jest ostatni element partycji. Dzięki tej operacji piwot jest usuwany ze zbioru. Zmienną j ustawiana jest na początek partycji. Zapamiętuje ona pozycję podziału partycji.

W pętli sterowanej zmienną i przeglądane są kolejne elementy od pierwszego do przedostatniego (ostatni jest umieszczony na pozycji piwotu, a piwot zapamiętany). Jeśli i-ty element jest mniejszy od piwotu, to trafia on na początek partycji - elementy wymieniane są ze sobą na pozycjach i-tej i j-tej. Po tej operacji przesuwany jest punkt podziałowy partycji j.

Po zakończeniu pętli element z pozycji j-tej przenoszony jest na koniec partycji, aby zwolnić miejsce dla piwotu, po czym wstawiany jest tam piwot. Zmienna j wskazuje zatem wynikową pozycję piwotu. Pierwotna partycja została podzielona na dwie partycje:

• partycja lewa od pozycji lewy do j-1 zawiera elementy mniejsze od piwotu;

• partycja prawa od pozycji j+1 do pozycji prawy zawiera elementy większe lub równe piwotowi.

Należy następnie sprawdzić, czy partycje te obejmują więcej niż jeden element. Jeśli tak, to algorytm sortowania szybkiego wywoływany jest rekurencyjnie z odpowiednimi wyznaczonymi granicami partycji. Po powrocie z wywołań rekurencyjnych partycja wyjściowa jest posortowana rosnąco. Algorytm jest zakończony.

Kod źródłowy algorytmu

Procedura sortowania szybkiego napisany w języku Pascal:

procedure Sortuj_szybko(lewy, prawy : integer);

var

i,j,piwot,x : integer;

begin

i := (lewy + prawy) div 2;

piwot := d[i]; d[i] := d[prawy];

j := lewy;

for i := lewy to prawy - 1 do

if d[i] < piwot then

begin

x := d[i]; d[i] := d[j]; d[j] := x;

inc(j);

end;

d[prawy] := d[j]; d[j] := piwot;

if lewy < j - 1 then Sortuj_szybko(lewy, j - 1);

if j + 1 < prawy then Sortuj_szybko(j + 1, prawy);

end;

10

---