Proste i zaawansowane algorytmy
sortowania
Bartłomiej Tomżyński
http://illusion3d.wordpress.com Wydanie 1
2 Przedmowa
Spis treści
Przedmowa .............................................................................................................................................. 3
Wstęp....................................................................................................................................................... 4
Sortowanie przez wybór (selection sort) ................................................................................................. 5
Sortowanie przez wstawianie (insertion sort).......................................................................................... 7
Sortowanie Shella .................................................................................................................................... 9
Sortowanie bÄ…belkowe (bubble sort) ..................................................................................................... 12
Sortowanie szybkie (quicksort) ............................................................................................................. 14
Sortowanie kopcowe (heap sort) ........................................................................................................... 16
Sortowanie przez scalanie (merge sort)................................................................................................. 19
Sortowanie przez zliczanie (counting sort) ........................................................................................... 21
Sortowanie pozycyjne (radix sort)......................................................................................................... 23
Sortowanie kubełkowe (bucket sort) ..................................................................................................... 24
Wnioski ................................................................................................................................................. 25
Bibliografia............................................................................................................................................ 27
3 Przedmowa
Przedmowa
Niniejsze opracowanie powstało na potrzeby zaliczenia przedmiotu Algorytmy i Struktury Danych,
które prowadził prof. dr hab. inż. Zbigniew Czech na III i IV semestrze studiów informatycznych na
Wydziale Automatyki, Elektroniki i Informatyki Politechniki ÅšlÄ…skiej w Gliwicach.
Te opracowanie to tylko zarys algorytmów sortujących. Ma za zadanie wytłumaczyć w jak najbardziej
przystępny sposób zagadnienia związane z sortowaniem. Nie będę się czuć gorszy, jeżeli czegoś za-
pomnę lub pominę, ponieważ nikomu nie uda się napisać książki zawierającej opis wszystkich algo-
rytmów ze wszystkich dziedzin (wystarczy wspomnieć, że "biblia algorytmiki ma 1200 stron, a na-
zwali to Wprowadzenie do algorytmów, więc to o czymś świadczy).
Życzę miłej lektury.
Bartłomiej Tomżyński
Tarnowskie Góry, maj 2009 r.
4 Wstęp
Wstęp
Sortowanie jest jednym z najważniejszych problemów w algorytmice, które doczekało się wielu efek-
tywnych rozwiązań. W wielu algorytmach sortowanie stanowi jeden z ich etapów i bywa tak, że ja-
kość zastosowanego algorytmu sortowania decyduje o szybkości całego programu lub systemu.
W tym wypracowaniu postaram się omówić kilka najważniejszych algorytmów sortowania.
Sortowanie to ułożenie (permutacja) elementów danego ciągu wejściowego w pewnej określonej rela-
cji.
Algorytmika wyróżnia dwie klasy algorytmów sortowania  sortowanie tablic (wewnętrzne) oraz sor-
towanie plików (sekwencyjne, zewnętrzne). W tym opracowaniu skupię się głównie na pierwszej kla-
sie algorytmów.
Algorytmy sortowania będziemy klasyfikować według ich złożoności obliczeniowej, stabilności
i sposobu działania.
Złożoność obliczeniowa danego algorytmu mówi, jak szybko dany zbiór zostanie posortowany. Dla
algorytmów sortujÄ…cych za pomocÄ… porównywaÅ„ dolne ograniczenie zÅ‚ożonoÅ›ci wynosi 5ØBÜ(5Ø[Ü log 5Ø[Ü),
gdzie 5Ø[Ü to ilość danych do posortowania. Możliwe jest zejÅ›cie poniżej tej granicy i uzyskać nawet
liniowÄ… zÅ‚ożoność 5ØBÜ(5Ø[Ü), ale wtedy sortowanie odbywa siÄ™ w inny sposób niż przez porównanie dwóch
elementów.
Kolejną cechą algorytmów sortowania jest ich stabilność. Algorytm sortowania jest stabilny, gdy za-
chowuje początkową względną relację pomiędzy elementami reprezentowanymi przez klucze. Klu-
czem nazywamy pole w rekordzie, względem którego są ustawiane elementy danego zbioru. Algoryt-
my będą przedstawiane na tablicach zwykłych liczb całkowitych, ale w praktyce sortuje się jakąś ko-
lekcję obiektów. Obiekt zawiera klucz jak i też inne pola, które z punktu widzenia sortowania są nie-
istotne, ale mogą być potem istotne.
Jeżeli element A znajdował się przed sortowaniem po elemencie B, czyli matematycznie
jÄ…c 5Ø4Ü {" 5Ø5Ü (zakÅ‚adamy, że elementy A i B posiadajÄ… też inne pola, wzglÄ™dem których nie sortujemy), a
po posortowaniu element A dalej jest przed B (mogą się pojawić inne elementy pomiędzy nimi, ale
względne ułożenie tych dwóch elementów jest niezmienne), to wtedy takie sortowanie nazywamy
stabilnym. W przeciwnym wypadku jest to sortowanie niestabilne.
Inną cechą algorytmów jest zachowanie naturalne. O algorytmie mówimy, że wykazuje zachowanie
naturalnie, gdy jest najszybszy dla danych już posortowanych, a najwolniejszy dla danych ułożonych
w odwrotnej kolejności niż dane posortowane.
We wnioskach znajduje się podsumowanie i zestawienie wszystkich zaprezentowanych algorytmów.
5 Sortowanie przez wybór (selection sort)
Sortowanie przez wybór (selection sort)
Idea tego algorytmu jest następująca: z ciągu nieposortowanego wybieramy najmniejszy element
i zamieniamy go z pierwszym elementem ciÄ…gu nieposortowanego, zmniejszamy ciÄ…g nieposortowany
o jeden element, po czym wybieramy najmniejszy element z nowopowstałego ciągu nieposortowanego
itd. aż do końca tablicy.
Jest to dosyć intuicyjny algorytm, każdy bez problemu może go sobie wyobrazić. Pewnie wielu z Was
bezwiednie korzystało z niego w życiu codziennym.
Zilustrujmy działanie powyższego zapisu na jakieś przykładowej tablicy. Ciemnoszarym kolorem
oznaczono obszar już posortowany.
Tablica przed sortowaniem ciąg nieposortowany to po prostu cała tablica.
5 2 4 1 3
Na początku z całej tablicy wybieramy najmniejszy element  jest nią liczba 1 i zamieniamy miejsca-
mi liczby 1 i 5 (bo 5 jest pierwszym elementem ciÄ…gu nieposortowanego).
1 2 4 5 3
Teraz w niezacieniowanym ciągu szukamy elementu najmniejszego  jest nim liczba 2, która okazała
się być na swoim miejscu.
1 2 4 5 3
Kolejne kroki są już oczywiste.
1 2 3 5 4
1 2 3 4 5
I w ten sposób otrzymaliśmy posortowaną tablicę.
Ten opis możemy zapisać w pseudokodzie:
SORTOWANIE-PRZEZ-WYBÓR(A)
1. for i := 1 to n - 1
2. do x := A[i]
3. for j := i + 1 to n do
4. if A[j] < x then
5. k := j
6. x := A[j]
7. A[k] := A[i]
8. A[i] := x
ZÅ‚ożoność tego algorytmu jest rzÄ™du 5ØBÜ(5Ø[Ü2).
Można zauważyć, że po zamianie ciąg posortowany (szary obszar) nie jest dalej modyfikowany, tzn.
nie modyfikujemy kolejności elementów w tym ciągu, tylko dopisujemy na koniec nowy najmniejszy
element. Można także zauważyć, że ten algorytm wykonuje ciągle tą samą operację na zmniejszają-
cym się zakresie danych. Z tych dwóch spostrzeżeń można wyciągnąć wniosek, że jest możliwa reali-
zacja tego algorytmu jako algorytmu rekurencyjnego:
6 Sortowanie przez wybór (selection sort)
SORTOWANIE-PRZEZ-WYBÓR-REKURENCYJNIE(A)
1. if i < j then
2. A[i] Ô! A[k]
3. SORTOWANIE-PRZEZ-WYBÓR-REKURENCYJNIE(A[i + 1..j])
W rozdziale poświęconym algorytmowi sortowania przez wstawianie porównamo algorytm sortowa-
nia przez wstawianie z sortowaniem przez wybór.
Zaprezentowany algorytm sortowania przez wybór nie gwarantuje stabilności sortowania, jednak za-
mieniając znak ostrej nierówności przy szukaniu minimalnego/maksymalnego elementu w danym
zbiorze na nieostrą można uzyskać stabilny algorytm sortowania przez wybór. Można to udowodnić.
Załóżmy, że mamy dwa obiekty A i B o takich samych kluczach, względem których sortujemy. Ele-
ment A jest przed B (A {" B) i chcemy, żeby tak też było po posortowaniu. Jeżeli w wyniku zamiany
miejscami z aktualnie najmniejszym elementem w ciÄ…gu nieposortowanym obiekt A wyleci za obiekt
B (czyli B {" A), to w wyniku sortowania ze znakiem ostrej nierówności najpierw zostanie wstawiony
element B, natomiast jedną iterację dalej, gdy szukamy elementu większego/mniejszego niż B trafimy
na obiekt A, to zostanie on zignorowany (wyrażenia 5ØNÜ < 5ØNÜ i 5ØNÜ > 5ØNÜ sÄ… nieprawdziwe; 5ØNÜ nie jest mniej-
sze od 5ØNÜ, jest równe 5ØNÜ, czyli zdanie jest nieprawdziwe) i zostanie wstawiony potem, za element B.
Tego nie chcieliśmy. Zmieniając znak nierówności na nieostrą obiekt A nie zostanie zignorowany
i zostanie zamieniony z elementem B. Względne ułożenie tych elementów pozostanie wtedy takie
same jak przed sortowaniem.
Algorytm sortowania przez wybór nie wykazuje zachowania naturalnego.
7 Sortowanie przez wstawianie (insertion sort)
Sortowanie przez wstawianie (insertion sort)
Jest to jeden z najprostszych i jeden z najbardziej intuicyjnych algorytmów sortowania. W wielu pu-
blikacjach porównuje się go do sortowania kart: bierzemy pierwszą kartę z nieposortowanego stosu
kart i znajdujemy dla niej odpowiednie miejsce w ciągu posortowanych kart, przesuwając karty więk-
sze od tej trzymanej w dłoni w prawo. Gdy znajdziemy kartę mniejszą bądz
równą wyciągniętej to
kończymy poszukiwanie i wstawiamy tą kartę do ciągu wyjściowego.
Powyższy zapis w pseudokodzie będzie wyglądał tak:
SORTOWANIE-PRZEZ-WSTAWIANIE(A)
1. for j := 2 to length[A] do
2. key := A[j]
3. i := j  1
4. while i > 0 i A[i] > key
5. do A[i + 1] := A[i]
6. i--
7. A[i + 1] := key
Na początku ciąg posortowany składa się tylko z pierwszego elementu.
Linie 4-6 realizują przesuwanie wszystkich elementów w prawo w celu znalezienia odpowiedniego
miejsca dla aktualnie rozpatrywanego elementu, który jest zapamiętany w zmiennej key. Po znalezie-
niu elementu większego od key pętla while zostaje przerwana i element key jest zapisywany w tak
powstałej luce.
Zilustrujmy działanie tego algorytmu na naszej przykładowej tablicy.
Przed sortowaniem.
Zakładamy, że pierwszy element jest już na swoim miejscu. Robi to warunek inicjacji zewnętrznej
pÄ™tli for (5ØWÜ 6"= 2). Na szaro zaznaczono na który element pokazuje zmienna 5ØWÜ:
5 2 4 1 3
Bierzemy teraz pierwszy element z ciÄ…gu nieposortowanego. Jest nim liczba 2, zapisujemy jÄ… sobie
gdzieś na boku (linia 2), i przesuwamy elementy większe od tego elementu w prawo (linie 4-6).
2
5 4 1 3
Jak znajdziemy miejsce dla tej liczby to jÄ… wstawiamy w tÄ… lukÄ™ (linia 7).
2 5 4 1 3
Teraz bierzemy liczbę 4, zapisujemy ją na boku i przesuwamy, aż znajdziemy dla niej miejsce.
4
2 5 1 3
2 4 5 1 3
8 Sortowanie przez wstawianie (insertion sort)
1
2 4 5 3
1 2 4 5 3
1 2 4 5 3
W efekcie czego dostajemy ciÄ…g posortowany.
W najlepszym przypadku, tzn. gdy dane są już posortowane, algorytm sortowania przez wstawianie
wykonuje siÄ™ w czasie 5ØBÜ(5Ø[Ü). Natomiast jego zÅ‚ożoność Å›rednia i pesymistyczna wynosi 5ØBÜ(5Ø[Ü2). Z tego
powodu ten algorytm jest niepraktyczny do sortowania dużych tablic. Natomiast dobrze sprawdza się
w sortowaniu małych tablic lub tablic częściowo posortowanych. Dla danych częściowo posortowa-
nych algorytm ten ma zÅ‚ożoność 5ØBÜ(5ØXÜ " 5Ø[Ü), gdzie 5ØXÜ, (5ØXÜ e" 1) to ilość elementów, które trzeba przenieść,
aby ciÄ…g byÅ‚ posortowany. Gdy 5ØXÜ = 5Ø[Ü, czyli gdy mamy do czynienia z najgorszym przypadkiem, kie-
dy to dane sÄ… w odwrotnej kolejnoÅ›ci do tej, której oczekujemy, to mamy 5ØBÜ 5Ø[Ü " 5Ø[Ü = 5ØBÜ 5Ø[Ü2 .
Z tego powodu algorytm ten wykazuje zachowanie naturalne.
Algorytm sortowania przez wstawianie jest bardzo podobny do algorytmu sortowania przez wybór,
które było przedstawione wyżej, ale w praktyce jest odrobinę szybszy. Ta różnica spowodowana jest
tym, że wewnętrzna pętla sortowania przez wstawianie wykonuje się tak długo, aż nie znajdzie miej-
sca dla aktualnie rozpatrywanego elementu, podczas gdy algorytm sortowania przez wybór musi
przejść przez całą tablicę w wewnętrznej pętli, aby mieć pewność, że odnalazł najmniejszy element
w danym podciągu. W ten sposób zyskujemy kilka iteracji wewnętrznej pętli mniej, co już ma wpływ
na szybkość działania.
Algorytm ten nie wymaga dodatkowej pamięci. Jest także stabilnym algorytmem sortowania. Wynika
to z tego, że zewnętrzna pętla for przechodzi przez elementy od lewej do prawej, więc jeżeli element
A znajduje się przed elementem B (A i B mają takie same pole, względem którego są sortowane), to
pierwszy na swoje miejsce zostanie wstawiony element A, a tuż za nim zostanie wstawiony element
B. Względne ułożenie tych elementów pozostanie więc takie same.
9 Sortowanie Shella
Sortowanie Shella
Sortowanie Shella jest uogólnieniem sortowania przez wstawianie. Nazywane jest także sortowaniem
przez wstawianie z malejącymi odstępami. Zaraz wyjaśnię, o co chodzi z tymi odstępami.
Idea algorytmu polega na porównywaniu elementów odległych od siebie o odległość !, która ciągle
maleje, aż osiągnie wartość 1. Shell zauważył, że algorytm sortowania przez wstawianie działa szyb-
ciej, gdy dane są już w dużym stopniu uporządkowane. Sortując dane odległe od siebie o odległość
większą niż 1 można szybciej osiągnąć stan uporządkowany, dla którego algorytm sortowania przez
wstawianie działa szybciej.
SHELL-SORT(A)
1. h := length[A] / 2
2. while h > 0 do
3. for i := h to length[A] do
4. j := i
5. temp := A[i]
6. while j >= h i A[j-h] > temp do
7. A[j] := A[j - h]
8. j := j - h
9. A[j] := temp
10. if h = 2 then
11. h := 1
12. else
13. h := h / 2
Prześledz
my kod algorytmu. Polega on na podziale ciągu wejściowego na kilka podciągów składają-
cych się z elementów odległych od siebie o !, a następnie posortowaniu tego ciągu jakimkolwiek in-
nym algorytmem. Nie warto tworzyć osobnych podtablic na podciągi, bo to zwiększałoby złożoność
pamięciową algorytmu i nie wyglądałoby to zbyt elegancko. Dużo lepszym rozwiązaniem jest taka
modyfikacja algorytmu sortowania przez wstawianie, żeby porównywał ze sobą elementy odległe o !
pozycji. Porównaj linie 6-8 z liniami 4-6 algorytmu przez wstawianie. Są prawie takie same, tylko
odstęp pomiędzy elementami wynosi !, a nie 1.
Zaprezentowany algorytm opiera się na oryginalnej koncepcji Shella, według której początkowa war-
tość ! jest równa połowie długość ciągu do posortowania, a w każdym następnym kroku ! jest zmniej-
szane dwukrotnie (dzielenie całkowitoliczbowe), aż osiągnie wartość 1. W ten sposób można uzyskać
zÅ‚ożoność rzÄ™du 5ØBÜ(5Ø[Ü2).
Przedstawmy ten algorytm na przykładowej tablicy.
2 4 1 8 3 10 7 9 6 5
Tablica ma rozmiar 10, więc pierwsza wartość ! będzie wynosić 5.
2 4 1 8 3 10 7 9 6 5 Przed sortowaniem
2 4 1 6 3 10 7 9 8 5 Po sortowaniu
10 Sortowanie Shella
Z kolejnym krokiem ! zmniejsza się dwukrotnie (przypominam, dzielenie całkowitoliczbowe),
li ! = 2:
2 4 1 6 3 10 7 9 8 5 Przed sortowaniem
1 4 2 5 3 6 7 9 8 10 Po sortowaniu
Kolejną wartością ! będzie 1, a więc mamy do czynienia ze zwykłym sortowaniem przez wstawianie,
w efekcie czego dostaniemy posortowanÄ… tablicÄ™.
Istnieją inne metody określania kolejnych wartości !. Bardzo dobre wyniki dają wartości ! uzyskane
ze wzoru:
·ð ! 1 = 1
·ð ! 5ØVÜ+1 = 3 " !5ØVÜ + 1
W takim przypadku można uzyskać nawet zÅ‚ożoność 5ØBÜ(5Ø[Ü1,15). Należy unikać odlegÅ‚oÅ›ci bÄ™dÄ…cymi
wielokrotnościami jakiś liczb, aby w skład podciągów wchodziły elementy z jak największej liczby
podciągów z kroków wcześniejszych. Ważne jest, aby ostatnią wartością ! było 1  wtedy mamy
w najgorszym przypadku do czynienia ze zwykłym sortowaniem przez wstawianie, co gwarantuje
posortowanie tablicy.
Algorytm Shella nie jest stabilny, choć opiera na sortowaniu przez wstawianie, które jest stabilne.
Dlaczego tak jest? Winne temu jest główne założenie algorytmu Shella  sortujemy elementy odległe
od siebie o pewną odległość !. Znów wez
my nasze elementy A i B tradycyjnie o takich samych klu-
czach, A{"B. W wyniku jakiegoś z kroków algorytmu może się zdarzyć, że element A zostanie wyrzu-
cony za B. Zróbmy tablicę, na której można to pokazać. Elementy 51 i 52 to są innymi słowy elementy
A i B:
! = 4
2 51 10 52 4 1 0 7 8 Przed sortowaniem
2 1 0 52 4 51 10 9 8 Po sortowaniu
! = 2
2 1 0 52 4 51 10 9 8 Przed sortowaniem
0 1 2 52 4 51 8 9 10 Po sortowaniu
Teraz widać, dlaczego sortowanie Shella jest niestabilne. Winna temu jest ostra nierówność w 6. linii.
W tym momencie pętla while zostaje przerwana (warunek staje się fałszywy) i nie następuje zamiana
elementów. Zamiana na nieostrą nierówność niewiele by dała, bo np. w naszym przypadku w drugim
11 Sortowanie Shella
kroku elementy zostałyby wstawione w odpowiedniej kolejności, ale już w następnym, gdy ! = 1 to
zostałyby znów ze sobą zamienione i wtedy 51 znalazłby się za 52, a tego nie chcieliśmy.
Sortowanie Shella wykazuje zachowanie naturalne. Kolejne kroki sÄ… sortowane za pomocÄ… sortowania
przez wstawianie, które wykazuje zachowanie naturalne.
12 Sortowanie bÄ…belkowe (bubble sort)
Sortowanie bÄ…belkowe (bubble sort)
W tym algorytmie przechodzimy po całej tablicy zamieniając parami sąsiednie elementy, jeżeli nie są
one w odpowiedniej relacji. Nazwa wzięła się stąd, że jak postawimy sortowaną tablicę pionowo to
efekt będzie podobny do bąbelków unoszących się w jakimś płynie. Najszybciej do góry będą się uno-
sić małe bąbelki, a te większe najwolniej.
W pseudokodzie ten algorytm wygląda następującą:
SORTOWANIE-B
BELKOWE(A)
1. for i := 2 to n do
2. for j := n downto i do
3. if A[j] < A[j - 1] then
4. A[j] "! A[j  1]
Prześledz
my wykonanie tego algorytmu na naszej przykładowej tablicy:
5 2 4 1 3
Każda linia w przykładzie pokazującym działanie algorytmu to pojedyncza iteracja tej pętli. Na szaro
zaznaczono obszar już posortowany.
WiÄ™c zaczynamy od 5Ø[Ü 6"= 2 i przechodzimy do wewnÄ™trznej pÄ™tli for, która idzie od koÅ„ca tablicy
do 5Ø[Ü. PominÄ…Å‚em pierwszÄ… iteracjÄ™ tej pÄ™tli, bo liczby 1 i 3 sÄ… na tym etapie na swoim miejscu:
5 2 4 1 3 5 2 1 4 3 5 1 2 4 3 1 5 2 4 3
Skończyła się pierwsza iteracja zewnętrznej pętli, wykonujemy drugą:
1 5 2 4 3 1 5 2 3 4 1 5 2 3 4 1 2 5 3 4
Kolejna iteracja:
1 2 5 3 4 1 2 5 3 4 1 2 3 5 4
I kolejna:
1 2 3 5 4 1 2 3 4 5
I otrzymaliśmy ciąg posortowany.
Można zauważyć, że w tym algorytmie mogą zdarzyć się puste przebiegi. Można tego uniknąć i spró-
bować poprawić czas działania algorytmu przełączając kierunki sortowania i zapamiętując pozycję
ostatniej zamiany. W ten sposób powstał algorytm shaker sort.
Oto jego zapis w pseudokodzie:
13 Sortowanie bÄ…belkowe (bubble sort)
SHAKERSORT(A)
1. do
2. swapped := false
3. for i := 0 to length[A] - 2 do
4. if A[i] > A[i + 1] then
5. A[i] "! A[i + 1]
6. swapped := true
7. if swapped = false then
8. break
9. swapped := false
10. for i := length[A] - 2 to 0 do
11. if A[i] > A[i + 1] then
12. A[i] "! A[i + 1]
13. swapped := true
14. while swapped
ZÅ‚ożoność sortowania bÄ…belkowego jest zarówno w najgorszym jak i Å›rednim przypadku rzÄ™du 5ØBÜ(5Ø[Ü2),
co w praktyce wyklucza go z sortowania dużych tablic. Również sortowanie shaker sort ma taką samą
złożoność średnią i pesymistyczną. Jednak oba algorytmy mają dobre czasy sortowań dla danych bę-
dÄ…cych już częściowo posortowanych. W takim przypadku, gdy element jest 5ØXÜ elementów od swojej
docelowej pozycji (5ØXÜ e" 1), to ich zÅ‚ożoność wynosi 5ØBÜ(5ØXÜ " 5Ø[Ü).
Jest to przykład algorytmu sortującego stabilnego. Tą stabilność załatwia nam warunek instrukcji if,
który sprawdza, czy możemy zamienić miejscami sąsiednie elementy. Znów wez
my dwa elementy A
i B (A{"B). W tym przypadku pierwszy zostanie wstawiony element A. W którejś z kolei iteracji bę-
dziemy szukać miejsca dla elementu B. W warunku instrukcji if jest ostra nierówność, co oznacza, że
jak dojdziemy do elementu A warunek jest faÅ‚szywy (przypominam, że 5ØNÜ < 5ØNÜ i 5ØNÜ > 5ØNÜ sÄ… zdaniami
fałszywymi) i element B nie będzie już przesuwany w górę. W ten sposób element B będzie tuż za
elementem A, czego bardzo chcieliśmy.
Algorytm ten nie znalazł większego zastosowania w praktyce. Nawet sam Donald Knuth w swojej
książce The Art of Computer Programming napisał: "the bubble sort seems to have nothing to recom-
mend it, except a catchy name and the fact that it leads to some interesting theoretical problems". Jest
to najprostszy w zapisie algorytm (więc osoby wkuwające algorytmy na pamięć będą uszczęśliwione),
co jest chyba jego jedynÄ… zaletÄ….
W porównaniu do poprzednich algorytmów w sortowaniu bąbelkowym zamiana sąsiednich elementów
wystÄ™puje w najgorszym wypadku 5Ø[Ü2, podczas gdy w poprzednich prezentowanych algorytmach za-
miana elementów wystÄ™puje 5Ø[Ü razy. Operacja zamiany jest kosztowna, wiÄ™c stÄ…d ta różnica wyników.
Zastosowanie algorytmu shaker sort nieznacznie poprawia czas działania algorytmu, jednak dalej ten
ulepszony algorytm jest jednym z najwolniejszych.
14 Sortowanie szybkie (quicksort)
Sortowanie szybkie (quicksort)
Algorytm quicksort jest przykładem algorytmu opartego na technice dziel i zwyciężaj. Jego pesymi-
styczny czas dziaÅ‚ania wynosi 5ØéÞ(5Ø[Ü2), jednak jego Å›redni czas jest rzÄ™du 5ØéÞ(5Ø[Ü log 5Ø[Ü), a staÅ‚e ukryte
w 5ØéÞ sÄ… bardzo maÅ‚e. Z tego powodu jest to najlepszy algorytm do praktycznych zastosowaÅ„.
Działanie algorytmu quicksort opiera się na trzech krokach:
1. Podziale tablicy wejÅ›ciowej5Ø4Ü[5Ø]Ü. . 5Ø_Ü] na dwie niepuste podtablice 5Ø4Ü1[5Ø]Ü. . 5Ø^Ü - 1]
i 5Ø4Ü2[5Ø^Ü + 1. . 5Ø_Ü] takie, że każdy element tablicy A1 jest mniejszy bÄ…dz
równy pewnemu
elementowi A[q] (zwanym elementem osiowym, ang. pivot), który sam jest nie więk-
szy niż każdy element z tablicy A2
2. Podtablice A1 i A2 sÄ… sortowane rekurencyjnie za pomocÄ… algorytmu quicksort
3. Nie jest wymagane scalanie elementów, ponieważ sortowanie odbywa się w miejscu;
wynikiem jest tablica 5Ø4Ü[5Ø]Ü. . 5Ø_Ü]
Zapis algorytmu pseudokodzie:
QUICKSORT(A, p, r)
1. if p < r then
2. q := PARTITION(A, p, r)
3. QUICKSORT(A, p, q - 1)
4. QUICKSORT(A, q + 1, r)
Najważniejszym elementem tego algorytmu jest odpowiednia implementacja metody PARTITION.
Od niego zależy szybkość samego algorytmu. Oto przykładowa implementacja tej procedury. Jako
element osiowy jest wybierany skrajny prawy element ciągu wejściowego:
PARTITION(A, p, r)
1. x := A[r]
2. i := p -1
3. for j := p to r  1 do
4. if A[j] d" x then
5. i++
6. A[i] "! A[j]
7. A[i + 1] "! A[r]
8. return i + 1
Czas dziaÅ‚ania algorytmu podziaÅ‚u wynosi 5ØéÞ(5Ø[Ü). W wyniku dziaÅ‚ania tej procedury wejÅ›ciowy ciÄ…g A
zostaÅ‚ podzielony na trzy zbiory  na elementy mniejsze niż 5ØeÜ, na elementy wiÄ™ksze niż 5ØeÜ i na jedno-
elementowy zbiór 5ØeÜ, bÄ™dÄ…cy elementem osiowym danego podziaÅ‚u.
Szybkość działania algorytmu quicksort zależy od zrównoważenia podziału, wykonanego w metodzie
PARTITION. W zaprezentowanym przykładzie jako element osiowy wybierany jest zawsze skrajny
prawy element zbioru wejściowego, jednak takie rozwiązanie może dać dla danych już posortowanych
zÅ‚ożoność najgorszÄ… z możliwych dla quicksort, czyli 5ØéÞ(5Ø[Ü2). W takim przypadku mamy też do czy-
nienia z liniową złożonością pamięciową, co już na miejscu zabija algorytm.
Z najgorszym przypadkiem podziału mamy do czynienia wtedy, gdy procedura dzieląca podzieli dane
wejÅ›ciowe o rozmiarze 5Ø[Ü na dwa obszary, jeden zawierajÄ…cy tylko jeden element, i drugi
cy 5Ø[Ü - 1 elementów. Gdyby taki podziaÅ‚ miaÅ‚ miejsce, to czas dziaÅ‚ania algorytmu quicksort bÄ™dzie
wynosiÅ‚ 5ØéÞ(5Ø[Ü2). Taki przypadek zachodzi m.in. dla danych posortowanych.
15 Sortowanie szybkie (quicksort)
Z najlepszym podziałem mamy do czynienia, gdy nastąpił równoważny podział. Wtedy czas działania
algorytmu quicksort wynosi 5ØéÞ(5Ø[Ü log 5Ø[Ü).
Są różne metody uzyskania podziału zrównoważonego. Można próbować wyznaczyć przybliżoną
medianę, losować element osiowy, albo stosować metodę  środkowy z trzech .
Metoda poszukiwania przybliżonej mediany daje podział najbardziej zbliżony do zrównoważonego.
Jednak wadą tego rozwiązania jest to, że algorytmy wyznaczające medianę są bardzo kosztowne, co
może negatywnie odbić się na całkowitym czasie sortowania.
Ostatnia metoda polega na wyborze trzech elementów z danego zbioru, a następnie wybraniu jako
element osiowy element leżący pomiędzy dwoma pozostałymi.
Pomimo tej pułapki w postaci funkcji podziału jest to obecnie najszybszy algorytm sortujący.
Nie jest to stabilny algorytm sortowania.
16 Sortowanie kopcowe (heap sort)
Sortowanie kopcowe (heap sort)
Ten algorytm różni się od poprzednich. Algorytm ten sortując tworzy strukturę zwaną kopcem. Ko-
piec jest strukturą danych, którą można rozpatrywać jako niepełne drzewo binarne. Kształtem przy-
pomina ściętą od dołu z prawej piramidę. Jego cechą charakterystyczną jest uporządkowanie. Przykła-
dowa tablica 5Ø4Ü = {5,2,1,3,4} może być reprezentowana jako drzewo, co pokazuje rysunek poniżej:
Załóżmy, że w pewnym węz
le znajduje siÄ™ wartość 5ØeÜ. W każdym wÄ™z
le poniżej danego węzła ich
wartość jest mniejsza lub równa 5ØeÜ. W notacji tablicowej można to zapisać jako 5ØGÜ[5Ø\Ü5ØWÜ5ØPÜ5ØVÜ5ØRÜ5ØPÜ(5ØVÜ)] e" 5ØGÜ[5ØVÜ].
Kopiec można reprezentować w tablicy T (założyłem, że jest indeksowana od 0), która spełnia nastę-
pujÄ…ce dwa warunki:
·ð w komórce 5ØGÜ 0 znajduje siÄ™ wierzchoÅ‚ek kopca (korzeÅ„ drzewa)
·ð dla dowolnego istniejÄ…cego wÄ™zÅ‚a 5ØGÜ 5ØVÜ jego lewy syn jest w 5ØGÜ[25ØVÜ + 1], a prawy
w 5ØGÜ[25ØVÜ + 2]
Są dwa typy kopców: typu max i typu min.
W kopcach typu max speÅ‚niona jest wÅ‚asność kopców typu max: 5ØGÜ[5Ø\Ü5ØWÜ5ØPÜ5ØVÜ5ØRÜ5ØPÜ 5ØVÜ ] e" 5ØGÜ[5ØVÜ], natomiast
w kopcach typu min speÅ‚niona jest wÅ‚asność kopców typu min: 5ØGÜ[5Ø\Ü5ØWÜ5ØPÜ5ØVÜ5ØRÜ5ØPÜ(5ØVÜ)] d" 5ØGÜ[5ØVÜ]. W zależnoÅ›ci od
typu kopca najmniejszy lub największy element znajduje się w korzeniu drzewa.
Aby móc wykorzystać algorytm sortowania przez kopcowanie należy zdefiniować procedury pozwala-
jÄ…ce na utworzenie kopca jak i na zarzÄ…dzanie nim. Te procedury to:
·ð MAX-HEAPIFY  dziaÅ‚ajÄ…ca w czasie 5ØBÜ(log 5Ø[Ü), sÅ‚użąca do przywracania wÅ‚asnoÅ›ci
kopca typu max
·ð BUILD-MAX-HEAP  dziaÅ‚ajÄ…ca w czasie 5ØBÜ(5Ø[Ü), tworzy kopiec max z nieposortowa-
nego ciągu wejściowego
·ð HEAPSORT  dziaÅ‚ajÄ…ca w czasie 5ØBÜ(5Ø[Ü log 5Ø[Ü), sortuje tablicÄ™
Procedura MAX-HEAPIFY sÅ‚uży do przywracania wÅ‚asnoÅ›ci kopca typu max. Jeżeli element 5ØGÜ 5ØVÜ jest
mniejszy niż jego synowie, przy założeniu, że synowie są poprawnymi kopcami typu max, to wtedy
element 5ØGÜ[5ØVÜ] narusza strukturÄ™ drzewa i należy przenieść go w dół drzewa, aby odzyskaÅ‚o wÅ‚asność
kopca typu max.
Poniżej znajduje się opis procedury MAX-HEAPIFY w pseudokodzie:
17 Sortowanie kopcowe (heap sort)
MAX-HEAPIFY(A, i)
1. l := LEFT(i)
2. r := RIGHT(i)
3. if l d" heap-size[A] i A[l] > A[i] then
4. largest := l
5. else
6. largest := i
7. if r d" heap-size[A] i A[r] > A[largest] then
8. largest := r
9. if largest `" i then
10. A[i] "! A[largest]
11. MAX-HEAPIFY(A, largest)
Procedura BUILD-MAX-HEAP służy do budowania kopca typu max. Wykorzystuje procedurę MAX-
HEAPIFY do przeksztaÅ‚cenia tablicy T o dÅ‚ugoÅ›ci 5Ø[Ü w kopiec typu max. Oto jej zapis w pseudokod-
zie:
BUILD-MAX-HEAP(A)
1. heap-size[A] := length[A]
2. for i := floor(length[A] / 2) downto 1 do
3. MAX-HEAPIFY(A, i)
Mając już dane te dwie procedury można przystąpić do napisania procedury sortującej przez kopco-
wanie. Jej zapis w pseudokodzie:
HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i := length[A] downto 2 do
3. A[1] "! A[i]
4. heap-size[A]--
5. MAX-HEAPIFY(A,1)
Na poniższym rysunku są przedstawione kolejne etapy sortowania przez kopcowanie na przykładowej
tablicy 5Ø4Ü = {5,2,1,3,4}.
Przed sortowaniem:
Pierwszym krokiem jest zbudowanie kopca typu max. Lewa gałąz
tego drzewa narusza zasady kopca,
a konkretnie potomkowie węzła 2. Naprawiamy więc kopiec i otrzymujemy:
18 Sortowanie kopcowe (heap sort)
Teraz sczytujemy wartości. Zaczynamy od wierzchołka, zapisujemy go gdzieś na boku, usuwamy go,
przywracamy własność kopca typu max/min i znowu usuwamy wierzchołek, itd. aż kopiec nie będzie
pusty. Następnie zapisujemy wartości od końca i mamy posortowany ciąg wejściowy.
Takie rozwiązanie podaje [1], ale moim zdaniem lepszym pomysłem byłoby zbudowanie kopca typu
max, jeżeli sortujemy dane nierosnąco, a min gdy sortujemy niemalejąco. Dzięki temu mamy element
najmniejszy (dla sortowania nierosnącego) lub największy (dla niemalejącego) w wierzchołku drzewa
i nie jest wtedy wymagane odwrócenie tablicy z wynikami.
Sortowanie przez kopcowanie jest szybkim algorytmem. Jego złożoność pesymistyczna jak i średnia
wynosi 5ØBÜ(5Ø[Ü log 5Ø[Ü). Jest minimalnie wolniejszy niż quicksort, ale za to jest bardziej odporny na atak
za pomocą odpowiednio spreparowanych danych wejściowych (są to dane już posortowane). W takim
przypadku quicksort dziaÅ‚aÅ‚by w czasie 5ØBÜ(5Ø[Ü2), podczas gdy sortowanie przez kopcowanie
w czasie 5ØBÜ(5Ø[Ü log 5Ø[Ü).
Algorytm sortowania przez kopcowanie nie wymaga dodatkowej pamięci.
Jest to algorytm niestabilny.
19 Sortowanie przez scalanie (merge sort)
Sortowanie przez scalanie (merge sort)
Algorytm sortowania przez scalanie wykorzystuje technikę dziel i zwyciężaj. Przez odpowiedni po-
dział problemu uzyskano znaczny wzrost szybkości działania.
W tym rozwiązaniu można wyróżnić dwa etapy:
·ð dziel  dzielenie tablicy na podtablice
·ð zwyciężaj  sortowanie otrzymanych podciÄ…gów poprzez rekurencyjne wywoÅ‚ywania
sortowania przez scalanie
·ð poÅ‚Ä…cz  Å‚Ä…czenie posortowanych podciÄ…gów w jeden posortowany ciÄ…g
Mechanizm rekurencji działa tak długo, aż wejściowy ciąg jest większy niż 1, ponieważ ciąg o długo-
ści 1 jest już posortowany.
Za punkt ostatni, czyli połącz, odpowiada procedura MERGE. Jako argument przyjmuje dwa posor-
towane podciągi (stosy) i scala je w jeden ciąg. Robi to w następujący sposób: porównuje dwa ele-
menty będące szczytami tych dwóch stosów i zapisuje do ciągu wyjściowego większy/mniejszy ele-
ment, zależnie od pożądanej relacji porządku. Oto jej zapis w pseudokodzie:
MERGE(A, p, q, r)
1. n1 := q  p + 1
2. n2 := r  q
3. Utwórz tablice L[1..n1 + 1] i R[1..n2]
4. for i := 1 to n1 do
5. L[i] := A[p + i  1]
6. for j := 1 to n2 do
7. R[i] := A[q + j]
8. L[n1 + 1] := "
9. R[n2 + 1] := "
10. i := 1
11. j := 1
12. for k := p to r do
13. if L[i] d" R[j] then
14. A[k] := L[i]
15. i++
16. else
17. A[k] := R[j]
18. j++
W powyższym rozwiązaniu na dno każdego ze stosów umieszcza się wartowników, każdy mający
bardzo dużą lub specyficzną wartość, która na pewno nie pojawi się w ciągu wejściowym. Dzięki te-
mu można pominąć instrukcje sprawdzające, czy opróżniono już któryś ze stosów i kod staje się czy-
telniejszy i bardziej elegancki.
Algorytm sortowania przez scalanie opiera się na ciągłym wywoływaniu samego siebie i dzieleniu
ciągu wejściowego na dwa podciągi, aż ciąg wejściowy będzie równy 1. Wtedy zaczyna scalać otrzy-
mane podciÄ…gi procedurÄ… MERGE.
20 Sortowanie przez scalanie (merge sort)
MERGE-SORT(A, p, r)
1. if p < r then
2. q := floor((p + r) / 2)
3. MERGE-SORT(A, p, q)
4. MERGE-SORT(A, q + 1, r)
5. MERGE(A, p, q, r)
Zobaczmy, jak algorytm sortowania przez scalanie posortuje na przykład taką tablicę:
4 7 1 9 2 0 8 3 5 6
Jest to tablica 10-elementowa. Na początku wywołujemy rekurencyjnie procedury MERGE-SORT,
która dzieli tą tablicę na pojedyncze elementy, które potem procedura MERGE łączy w całość.
4 7 1 9 2 0 8 3 5 6
4 7 1 9 0 2 3 8 5 6
1 4 7 9 0 2 3 8 5 6
0 1 2 3 4 7 8 9 5 6
0 1 2 3 4 5 6 7 8 9
Algorytm sortowania przez scalanie należy do klasy 5ØéÞ(5Ø[Ü log 5Ø[Ü).
Wymaga dodatkowej 5ØBÜ 5Ø[Ü pamiÄ™ci na przechowywanie wyników czÄ…stkowych.
Jest algorytmem stabilnym dzięki linii 13 procedury MERGE. Jeżeli A znajdowało się przed sortowa-
niem przed B, to oznacza, że element A będzie po podzieleniu tablicy wejściowej albo w lewej tablicy
pomocniczej, albo w tej samej, ale przed elementem B. Drugi przypadek jest oczywisty, wtedy jest
spełniony warunek stabilności. W pierwszym przypadku oba elementy w tym samym czasie wskoczą
na początek tych tablic i wtedy wspomniana linia 13 najpierw pobierze element z lewej tablicy dzięki
nieostrej nierówności, a potem wstawi element z prawej tablicy. Nie ma więc możliwości, żeby B
wskoczyło przed A.
21 Sortowanie przez zliczanie (counting sort)
Sortowanie przez zliczanie (counting sort)
W porównaniu do poprzednich algorytmów sortowanie przez zliczanie nie sortuje za pomocą porów-
nań. Jak się póz
niej okaże, sortuje on dane w czasie 5ØBÜ(5Ø[Ü). Metoda ta wymaga jednak speÅ‚nienia pew-
nych założeń wobec danych wejściowych. Algorytm bowiem zakłada, że dane są z góry określonego
skończonego zbioru małych liczb całkowitych. Przy omawianiu tego algorytmu zakładam, że dane
wejÅ›ciowe sÄ… z liczbami caÅ‚kowitymi z przedziaÅ‚u 1. . 5ØXÜ dla pewnego ustalonego 5ØXÜ.
Algorytm ten działa na innej zasadzie niż algorytmy porównujące poszczególne elementy. Algorytm
zlicza, ile elementów jest mniejszych niż dany element. Jeżeli np. 5 elementów jest mniejszych niż 5ØeÜ,
to 5ØeÜ powinien znalez
ć się na 6. pozycji.
Zapis algorytmu przez zliczanie w pseudokodzie:
COUNTING-SORT(A, B, k)
1. for i := 0 to k do
2. C[i] := 0
3. for j := 1 to length[A] do
4. C[A[j]]++
5. for i := 1 to k do
6. C[i] := C[i] + C[i  1]
7. for j := length[A] downto 1 do
8. B[C[A[j]]] := A[j]
9. C[A[j]]--
W linijkach 1 i 2 nastÄ™puje inicjacja tablicy pomocniczej C o dÅ‚ugoÅ›ci 5ØXÜ. NastÄ™pnie w linijkach 3 i 4
nastÄ™puje zliczanie, ile dany element wystÄ…piÅ‚. Jeżeli element o wartoÅ›ci 5ØeÜ wystÄ…piÅ‚ 5ØYÜ razy, to ten wy-
nik jest zapisywany do tablicy C do komórki o numerze 5ØeÜ.
W liniach 5 i 6 następuje zsumowanie, ile elementów jest przed danym elementem.
Linie 7-9 ustawiają przy pomocy tablicy C dane wejściowe w odpowiednie miejsce w tablicy wyj-
ściowej B. Linia 9 pozwala uniknąć sytuacji, gdy dwa takie same elementy chcą zająć to samo miej-
sce.
Zawsze przykład jest warty tysiąca słów, więc zobaczmy sortowanie przez zliczanie w akcji. Danymi
do posortowania są następujące liczby całkowite z przedziału 1,6
1 2 2 1 5 6 2 3 4 1
Tworzymy pomocniczÄ… tablicÄ™ C o rozmiarze 5ØXÜ = 6 i w i-tej komórce (5ØVÜ = 1 & 5ØXÜ) zapisujemy, ile razy
i-ta liczba wystąpiła (linie 3 i 4).
1 2 3 4 5 6
Liczba wystąpień 3 3 1 1 1 1
Teraz wyznaczamy liczbę elementów mniejszych od i-tej komórki poprzez zsumowanie liczby wystą-
pień liczb mniejszych bądz
równych od tej w i-tej komórce (linie 5 i 6):
1 2 3 4 5 6
Liczba wystąpień 3 6 7 8 9 10
22 Sortowanie przez zliczanie (counting sort)
I teraz przystępujemy do przepisywania liczb do tablicy wynikowej na podstawie powyższej tablicy
(linie 7-9, na szaro zaznaczam elementy już wstawione):
5ØWÜ = 10
1
1 2 3 4 5 6
2 6 7 8 9 10
5ØWÜ = 9
1 4
1 2 3 4 5 6
2 6 7 7 9 10
5ØWÜ = 8
1 3 4
1 2 3 4 5 6
2 6 6 7 9 10
5ØWÜ = 7
1 2 3 4
1 2 3 4 5 6
2 6 6 7 9 10
I tak dalej& aż uzyskamy szybciej niż by to się wydawało posortowaną tablicę.
Przeglądając kod algorytmu widać, dlaczego danymi wejściowymi mogą być tylko liczby całkowite,
i to z góry określonego i małego zbioru. W czasie wykonywania algorytmu tworzona jest tablica C,
w której w komórkach o odpowiednich indeksach przechowuję się informację o liczbie wystąpień
danej wartości. Tablica ta nie może mieć niecałkowitych indeksów i nie może zajmować nieskończo-
nej ilości pamięci, bo jest fizycznie niemożliwe (ogólnie nieskończoność w jakiejkolwiek postaci jest
fizycznie niemożliwa), stąd te ograniczenie co do danych wejściowych.
ZÅ‚ożoność obliczeniowa tego algorytmu to 5ØBÜ(5Ø[Ü + 5ØXÜ). Wynika to stÄ…d, że w tym algorytmie wystÄ™pujÄ…
pojedyncze (niezagnieżdżone) pÄ™tle for, które siÄ™ wykonujÄ… 5Ø[Ü lub 5ØXÜ cykli. W praktyce wykorzystuje
siÄ™ 5ØXÜ = 5ØBÜ(5Ø[Ü), wtedy czas sortowania wynosi 5ØéÞ(5Ø[Ü). Wymaga za to dodatkowej pamiÄ™ci 
5ØBÜ 5ØXÜ lub 5ØBÜ(5Ø[Ü + 5ØXÜ).
W pierwszym zdaniu padło przy opisie tego algorytmu padło stwierdzenie, że w sortowaniu przez
zliczanie nie porównujemy elementów. Obejrzyj kod, widać gdzieś tam porównania? Nie ma ich tam.
Elementy są ustawiane w odpowiednim porządku przy pomocy ich indeksów. Ta zmiana sposobu
sortowania pozwoliÅ‚a pokonać barierÄ™ &! 5Ø[Ü log 5Ø[Ü i zejść do zależnoÅ›ci liniowej 5ØBÜ(5Ø[Ü).
Jest to algorytm stabilny.
23 Sortowanie pozycyjne (radix sort)
Sortowanie pozycyjne (radix sort)
Znów poczyńmy pewne założenie co do danych wejściowych. Dotychczas kluczem był pojedynczy
rekord w obiekcie. A co, jeżeli chcemy sortować według więcej niż jednym kluczu na raz?
Wez
my takie oto dane wejściowe:
2 5 9
6 0 6
1 3 8
3 5 1
6 7 8
3 3 1
Każdy obiekt jest w osobnym wierszu, a sortujemy według kolumn, czyli mamy 5 obiektów, każdy
z trzema rekordami.
Można rozwiązać ten problem w następujący sposób  sortować dowolnym algorytmem sortującym
według kolejnych kolumn, zaczynając od najmniej znaczącej. Trzeba jednak pamiętać, aby względne
ułożenie posortowanych obiektów w kolumnach było takie same, czyli algorytm sortujący daną ko-
lumnę musi być stabilny.
Sam algorytm jest bardzo prosty w zapisie. Przyjmujemy, że sortujemy dane A o dÅ‚ugoÅ›ci 5Ø[Ü, a każdy
z obiektów posiada 5ØQÜ pól, wzglÄ™dem których sortujemy, przy czym pole pierwsze jest najmniej zna-
czÄ…ce.
RADIX-SORT(A, d)
1. for i := 1 to d do
2. posortuj stabilnie dane A względem kolumny i
Prześledz
my, jak ten algorytm posortuje naszą przykładową tablicę. Na szaro zaznaczono kolumnę,
względem której sortujemy.
2 5 9 3 5 1 6 0 6 1 3 8
6 0 6 3 3 1 3 3 1 2 5 9
1 3 8 6 0 6 1 3 8 3 3 1
3 5 1 1 3 8 3 5 1 3 5 1
6 7 8 6 7 8 2 5 9 6 0 6
3 3 1 2 5 9 6 7 8 6 7 8
I otrzymaliśmy posortowane dane wejściowe.
Ten algorytm świetnie się sprawdza, jeżeli mamy do posortowania bardzo dużo długich liczb lub in-
nych ciągów, przy czym ich najbardziej znaczące pozycje są bardzo podobne, tzn. prawdopodobień-
stwo, że pierwsze cyfry lub znaki będą takie same jest duże. Inne algorytmy musiały by zaczynać od
znaków wiodących i schodzić coraz głębiej w dany rekord. W przypadku sortowania pozycyjnego
idziemy od tyłu, czyli od znaków najmniej znaczących i możemy szybciej osiągnąć stan uporządko-
wany.
ZÅ‚ożoność tego algorytmu wynosi 5ØBÜ 5Ø[Ü i jest to algorytm stabilny.
24 Sortowanie kubełkowe (bucket sort)
Sortowanie kubełkowe (bucket sort)
Kolejny z algorytmów sortujących nie korzystający z porównań. Jak się okaże, algorytm ten sortuje
w czasie liniowym.
CaÅ‚y myk w tym algorytmie polega na powrzucaniu danych wejÅ›ciowych do 5ØZÜ kubeÅ‚ków. KubeÅ‚ki sÄ…
pewnymi przedziałami. Na początku przepisujemy liczby z tablicy sortowanej do odpowiednich ku-
bełków (przedziałów), następnie je sortujemy i na końcu łączymy kubełki, aby uzyskać ciąg już posor-
towany.
A gdzie są tutaj założenia co do danych wejściowych? Mianowicie, musimy wiedzieć, ile ma być ku-
bełków. Żeby to wiedzieć, musimy znać ilość elementów i wartość największego elementu w ciągu.
To drugie może być wąskim gardłem całego procesu, bo algorytmy znajdujące element maksymalny
dziaÅ‚ajÄ… w czasie 5ØBÜ(5Ø[Ü). Dlatego warto zaÅ‚ożyć, że dane wejÅ›ciowe sÄ… z pewnego zakresu, który zna-
my.
Zapis algorytmu w pseudokodzie. Tablica A to ciąg do posortowania, a B to lista kubełków:
1. n := length[A]
2. utwórz n pustych kubełków
3. for i := 1 to n do
4. wstaw A[i] na właściwą listę B[j]
5. for i := 0 to n-1 do
6. posortuj listÄ™ B[i] przez wstawianie
7. połącz listy B[0]& B[n-1] z zachowaniem kolejności
ZÅ‚ożoność obliczeniowa tego algorytmu wynosi 5ØBÜ(5Ø[Ü).
25 Wnioski
Wnioski
W poniższej tabeli zebrałem wnioski z moich rozważań nad poszczególnymi algorytmami.
Złożoność obliczeniowa
Złożoność
Nazwa algorytmu Stabilny
pamięciowa
Åšrednia Pesymistyczna
Przez wstawianie 5ØBÜ(1) Tak
5ØBÜ(5Ø[Ü2) 5ØBÜ(5Ø[Ü2)
Shella - 5ØBÜ(5Ø[Ü log25Ø[Ü) 5ØBÜ(1) Nie
Przez wybór 5ØBÜ(1) Nie
5ØBÜ(5Ø[Ü2) 5ØBÜ(5Ø[Ü2)
BÄ…belkowe 5ØBÜ(1) Tak
5ØBÜ(5Ø[Ü2) 5ØBÜ(5Ø[Ü2)
Szybkie 5ØBÜ(5Ø[Ü log 5Ø[Ü) 5ØBÜ(5Ø[Ü2) 5ØBÜ(5Ø[Ü log 5Ø[Ü) Nie
Przez kopcowanie 5ØBÜ(5Ø[Ü log 5Ø[Ü) 5ØBÜ(5Ø[Ü log 5Ø[Ü) 5ØBÜ(5Ø[Ü) Tak
Przez scalanie 5ØBÜ(5Ø[Ü log 5Ø[Ü) 5ØBÜ(5Ø[Ü log 5Ø[Ü) 5ØBÜ(5Ø[Ü) Tak
Przez zliczanie 5ØBÜ(5Ø[Ü) 5ØBÜ(5Ø[Ü) 5ØBÜ(5Ø[Ü) Tak
Pozycyjne 5ØBÜ(5Ø[Ü) 5ØBÜ(5Ø[Ü) 5ØBÜ(5Ø[Ü) Tak
KubeÅ‚kowe 5ØBÜ(5Ø[Ü " 5ØXÜ) 5ØBÜ(5Ø[Ü2 " 5ØXÜ) 5ØBÜ(5Ø[Ü " 5ØXÜ) Tak
Przyglądając się tej tabeli można zauważyć jedną ze starych prawd informatyki: im szybszy algorytm,
tym więcej wymaga zasobów, i na odwrót.
Przy wyborze algorytmu sortowania należy wziąć pod uwagę charakterystykę zbiorów, na których
będzie działać.
Dla dużych zbiorów czas działania algorytmów sortowania przez wstawianie, Shella, przez wybór,
bąbelkowego i shakersort są nie do przyjęcia. Dla takich zbiorów dużo lepszym rozwiązaniem są algo-
rytmy o zÅ‚ożonoÅ›ci 5ØBÜ(5Ø[Ü log 5Ø[Ü), które to wykonajÄ… to zadanie znacznie szybciej. W takim wypadku
algorytmy quicksort, mergesort i heapsort są bezkonkurencyjne. Używając algorytmu quicksort należy
uważać, aby dane wejściowe nie były w dużym stopniu uporządkowane, bo wtedy jego złożoność
obliczeniowa wynosi 5ØBÜ(5Ø[Ü2). Dużo bezpieczniejszy jest algorytm heapsort, który jest na takie puÅ‚apki
odporny, a jest minimalnie wolniejszy.
Jeżeli zbiór wejściowy jest już częściowo posortowany to można zastosować algorytmy sortowań
przez wstawianie czy przez wybór. Jeżeli jest 5ØXÜ elementów, które nie sÄ… na swoich pozycjach, to zÅ‚o-
żoność tych algorytmów jest klasy 5ØBÜ(5Ø[Ü " 5ØXÜ). Gdy 5ØXÜ jest bliskie 1 to wtedy sortowanie odbywa siÄ™ nie-
malże w czasie liniowym. W takim przypadku lepiej jest użyć sortowania przez wstawianie z racji
tego, że nie musi on skanować całego zbioru w celu znalezienia najmniejszego elementu, tylko koń-
26 Wnioski
czy, gdy znajdzie element większy/mniejszy niż aktualnie rozpatrywany. Jego dodatkową zaletą jest
to, że jest stabilny.
Mając jakąś wiedzę na temat danych, które będziemy sortować, można użyć sortowań nie opierają-
cych swoje działanie na porównaniach i posortować ciąg w czasie liniowym.
To nie są wszystkie stworzone algorytmy sortowań. To są jedynie te najczęściej spotykane. Cały czas
sÄ… tworzone nowe algorytmy sortowania, mniej lub bardziej udane.
27 Bibliografia
Bibliografia
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein. Wprowadzenie do
algorytmów. Wydawnictwa Naukowo-Techniczne, Warszawa 2005. ISBN 83-204-3149-2
[2] Niklaus Wirth. Algorytmy + struktury danych = programy. Wydawnictwa Naukowo-
Techniczne, Warszawa 2004. ISBN 83-204-3057-7
[3] Zbigniew J. Czech, Sebastian Deorowicz, Piotr Fabian. Algorytmy i struktury danych. Wybra-
ne zagadnienia. Wydawnictwo Politechniki ÅšlÄ…skiej, Gliwice 2007. ISBN 978-83-7335-366-4
[4] Piotr Wróblewski. Algorytmy, struktury danych i techniki programowania. Helion, Gliwice
2003. ISBN 83-7361-101-0
[5] Wikipedia, http://en.wikipedia.org/wiki/Sorting_algorithm
[6] Wikipedia, http://pl.wikipedia.org/wiki/Sortowanie