Klasa II sortowanie

Sortowanie danych jest jednym z podstawowych problemów programowania komputerów, z którym prędzej czy później spotka się każdy programista. Poniżej przedstawiamy tylko nieliczne dziedziny, w których występuje potrzeba sortowania danych:

sport - wyniki uzyskane przez poszczególnych zawodników należy ułożyć w określonej kolejności, aby wyłonić zwycięzcę oraz podać lokatę każdego zawodnika.
bank - spłaty kredytów należy ułożyć w odpowiedniej kolejności, aby wiadomo było kto i kiedy ma płacić odsetki do banku.
grafika - wiele algorytmów graficznych wymaga porządkowania elementów, np. ścian obiektów ze względu na odległość od obserwatora. Uporządkowanie takie pozwala później określić, które ze ścian są zakrywane przez inne ściany dając w efekcie obraz trójwymiarowy.
bazy danych - informacja przechowywana w bazie danych może wymagać różnego rodzaju uporządkowania, np. lista książek może być alfabetycznie porządkowana wg autorów lub tytułów, co znacznie ułatwia znalezienie określonej pozycji.

Wbrew obiegowym opiniom nie ma "idealnego" i "uniwersalnego" algorytmu sortującego - jeden algorytm jest lepszy w jednej sytuacji, drugi w innej. Dlatego dokładna znajomość własności algorytmów sortujących pozwala na tworzenie naprawdę efektywnych aplikacji.

Porządek w zbiorze

Zbiór posortowany to taki zbiór, w którym kolejne elementy są poukładane w pewnym porządku (kolejności). Porządek ten możemy określić za pomocą relacji ≥ lub ≤ (albo dowolnej innej relacji porządkowej, która jednoznacznie wyznacza kolejność elementów w zbiorze). Równość jest konieczna w przypadku, gdy elementy zbioru mogą przyjmować takie same wartości. Na przykład zbiór liczb:

D = { 1, 3, 3, 5, 7, 7, 8, 9 }

jest posortowany rosnąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja:

element poprzedni jest mniejszy lub równy od elementu następnego

Odwrotnie, zbiór:

D = { 9, 8, 6, 6, 4, 2, 1, 1, 0 }

jest posortowany malejąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja:

element poprzedni jest większy lub równy od elementu następnego.

Oczywiście zbiór wcale nie musi składać się z liczb (chociaż tak naprawdę każdy rodzaj danych komputerowych w końcu sprowadza się do liczb, gdyż wewnętrznie jest reprezentowany przez kody binarne). W takim przypadku należy określić dla każdego elementu tzw. klucz (ang. key), wg którego dokonywane jest sortowanie. Ponieważ klucz jest liczbą, zatem obowiązują dla niego podane wyżej zasady kolejności elementów. Na przykład dla tekstów kluczem mogą być kody poszczególnych znaków. Większość języków programowania posiada operatory porównywania ciągu znaków (problemem może być sortowanie wg zasad języka polskiego - nie wystarczy wtedy porównywać kodów znakowych, ponieważ kody polskich literek ą, ć, Ć itd. są zwykle większe od kodów liter alfabetu łacińskiego, ale i ten problem daje się z powodzeniem rozwiązać przez odpowiedni dobór kluczy).

Przez sortowanie będziemy rozumieć taką zmianę kolejności elementów zbioru nieuporządkowanego (permutację), aby w wyniku spełniały one założony porządek.

Czasowa złożoność obliczeniowa

Kolejnym zagadnieniem, które powinniśmy omówić we wstępie, jest tzw. czasowa złożoność obliczeniowa (ang. computational complexity) algorytmu sortującego (istnieje również złożoność pamięciowa). Określa ona statystycznie czas wykonywania algorytmu w zależności od liczby danych wejściowych. Czasowa złożoność obliczeniowa wyrażana jest liczbą tzw. operacji dominujących, czyli takich, które mają bezpośredni wpływ na czas wykonywania algorytmu. Dzięki takiemu podejściu uniezależniamy czasową złożoność obliczeniową od szybkości komputera, na którym dany algorytm jest realizowany. Złożoność obliczeniową charakteryzujemy przy pomocy tzw. notacji O (omikron). Oto odpowiednie przykłady:

O(n)	-	Algorytm o liniowej zależności czasu wykonania od ilości danych. Dwukrotny wzrost liczby przetwarzanych danych powoduje dwukrotny wzrost czasu wykonania. Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać stałą liczbę operacji.
O(n²)	-	Algorytm, w którym czas wykonania rośnie z kwadratem liczby przetwarzanych elementów. Dwukrotny wzrost liczby danych powoduje czterokrotny wzrost czasu wykonania. Tego typu złożoność powstaje, gdy dla każdego elementu należy wykonać ilość operacji proporcjonalną do liczby wszystkich elementów.
O(n logn)	-	Dobre algorytmy sortujące mają taką właśnie złożoność obliczeniową. Czas wykonania przyrasta dużo wolniej od wzrostu kwadratowego. Tego typu złożoność powstaje, gdy zadanie dla n elementów można rozłożyć na dwa zadania zawierające po połowie elementów.
O(n!) O(aⁿ)	-	Bardzo pesymistyczne algorytmy, czas wykonania rośnie szybko ze wzrostem liczby elementów wejściowych, czyli znalezienie rozwiązania może zająć najszybszym komputerom całe wieki lub tysiąclecia. Takich algorytmów należy unikać jak ognia !

Zapis O( ) określamy mianem klasy złożoności obliczeniowej algorytmu. Klasa czasowej złożoności obliczeniowej umożliwia porównywanie wydajności różnych algorytmów sortujących. Z reguły proste algorytmy posiadają wysoką złożoność obliczeniową - długo dochodzą do wyniku końcowego. Algorytmy bardziej skomplikowane posiadają mniejszą złożoność obliczeniową - szybko dochodzą do rozwiązania. Złożoność obliczeniowa wszystkich algorytmów sortujących została dokładnie oszacowana - my również dokonujemy tego w niniejszym opracowaniu.

Przykład:

Załóżmy, iż mamy program sortujący dane zbudowany na bazie algorytmu sortującego o klasie złożoności obliczeniowej O(n²). Sto elementów jest sortowane w czasie 1 sekundy. Ile czasu zajmie posortowanie za pomocą tego programu zbioru o tysiącu elementach? Odpowiedź brzmi - 100 sekund. Ponieważ ilość danych wzrosła 10 razy, to czas obliczeń wzrósł 10², czyli 100 razy. Poniżej przedstawiamy odpowiednią tabelkę.

Lp.

n

Czas obliczeń

1.

100

= 1 sekunda

2.

1.000

= 100 sekund = 1 minuta 40 sekund

3.

10.000

= 10.000 sekund = 2 godziny 46 minut 40 sekund

4.

100.000

= 1.000.000 sekund = 11 dni 13 godzin 46 minut 40 sekund

5.

1.000.000

= 100.000.000 sekund = 3 lata 2 miesiące 9 godzin 46 minut 40 sekund

6.

10.000.000

= 1 x 10¹⁰ sekund = 317 lat 1 miesiąc 4 dni 17 godzin 46 minut 40 sekund

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.

Algorytm sortowania bąbelkowego przy porządkowaniu zbioru nieposortowanego ma klasę czasowej złożoności obliczeniowej równą O(n²). Sortowanie odbywa się w miejscu.

Przykład:

Jako przykład działania algorytmu sortowania bąbelkowego posortujemy przy jego pomocy 5-cio elementowy zbiór liczb {5 4 3 2 1}, który wstępnie jest posortowany w kierunku odwrotnym, co możemy uznać za przypadek najbardziej niekorzystny, ponieważ wymaga przestawienia wszystkich elementów.

Obieg	Zbiór	Opis operacji
1	5 4 3 2 1	Rozpoczynamy od pierwszej pary, która wymaga wymiany elementów
	4 5 3 2 1	Druga para też wymaga zamiany elementów
	4 3 5 2 1	Wymagana wymiana elementów
	4 3 2 5 1	Ostatnia para również wymaga wymiany elementów
	4 3 2 1 5	Stan po pierwszym obiegu. Zwróć uwagę, iż najstarszy element (5) znalazł się na końcu zbioru, a najmłodszy (1) przesunął się o jedną pozycję w lewo.
2	4 3 2 1 5	Para wymaga wymiany
	3 4 2 1 5	Para wymaga wymiany
	3 2 4 1 5	Para wymaga wymiany
	3 2 1 4 5	Elementy są w dobrej kolejności, zamiana nie jest konieczna.
	3 2 1 4 5	Stan po drugim obiegu. Zwróć uwagę, iż najmniejszy element (1) znów przesunął się o jedną pozycję w lewo. Z obserwacji tych można wywnioskować, iż po każdym obiegu najmniejszy element wędruje o jedną pozycję ku początkowi zbioru. Najstarszy element zajmuje natomiast swe miejsce końcowe.
3	3 2 1 4 5	Para wymaga wymiany
	2 3 1 4 5	Para wymaga wymiany
	2 1 3 4 5	Dobra kolejność
	2 1 3 4 5	Dobra kolejność
	2 1 3 4 5	Stan po trzecim obiegu. Wnioski te same.
4	2 1 3 4 5	Para wymaga wymiany
	1 2 3 4 5	Dobra kolejność
	1 2 3 4 5	Dobra kolejność
	1 2 3 4 5	Dobra kolejność
	1 2 3 4 5	Zbiór jest posortowany. Koniec

Posortowanie naszego zbioru wymaga 4 obiegów. Jest to oczywiste: w przypadku najbardziej niekorzystnym najmniejszy element znajduje się na samym końcu zbioru wejściowego. Każdy obieg przesuwa go o jedną pozycję w kierunku początku zbioru. Takich przesunięć należy wykonać n - 1 (n - ilość elementów w zbiorze).

Uwaga:

Algorytm sortowania bąbelkowego jest uważany za bardzo zły algorytm sortujący. Można go stosować tylko dla niewielkiej liczby elementów w sortowanym zbiorze (do około 5000). Przy większych zbiorach czas sortowania może być zbyt długi.

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 0 do n - 1.

Dane wyjściowe

d[ ]	- posortowany zbiór n-elementowy.

Zmienne pomocnicze

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

Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji.

W identyczny sposób postępujemy z resztą elementów należących do zbioru. Znów wyszukujemy element najmniejszy i zamieniamy go z elementem na drugiej pozycji. Otrzymamy dwa posortowane elementy. Procedurę kontynuujemy dla pozostałych elementów dotąd, aż wszystkie będą posortowane.

Algorytm sortowania przez wybór posiada klasę czasowej złożoności obliczeniowej równą O(n²). Sortowanie odbywa się w miejscu.

Przykład:

Dla przykładu posortujmy tą metodą zbiór {4 7 2 9 3}. Kolorem zielonym oznaczyliśmy elementy zbioru, które są już posortowane.

Zbiór Opis operacji

 4 7 2 9 3

Wyszukujemy najmniejszy element w zbiorze. Jest nim liczba 2.

 2 7 4 9 3

Znaleziony element minimalny wymieniamy z pierwszym elementem zbioru - liczbą 4

 2 7 4 9 3

Wśród pozostałych elementów wyszukujemy element najmniejszy. Jest nim liczba 3.

 2 3 4 9 7

Znaleziony element minimalny wymieniamy z drugim elementem zbioru - liczbą 7.

 2 3 4 9 7

Znajdujemy kolejny element minimalny - liczbę 4.

 2 3 4 9 7

Wymieniamy go z samym sobą - element ten nie zmienia zatem swojej pozycji w zbiorze.

 2 3 4 9 7

Znajdujemy kolejny element minimalny

 2 3 4 7 9

Wymieniamy go z liczbą 9

 2 3 4 7 9

Ostatni element jest zawsze na właściwej pozycji. Sortowanie zakończone

Podana metoda sortuje zbiór rosnąco. Jeśli chcemy posortować zbiór malejąco, to zamiast elementu minimalnego poszukujemy elementu maksymalnego. Pozostała część procedury sortującej nie ulega zmianie.

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 0 do n - 1.

Dane wyjściowe

d[ ]	- posortowany zbiór n-elementowy.

Zmienne pomocnicze

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

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. Insertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty. A jak przenieść tę ideę do świata komputerów i zbiorów liczbowych?

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órą sukcesywnie będziemy tworzyli na końcu zbioru (istnieje też odmiana algorytmu umieszczająca listę uporządkowaną na początku zbioru). Pętla sortująca (wewnętrzna) szuka 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ńczymy, gdy pętla główna wybierze wszystkie elementy zbioru.

Algorytm sortowania przez wstawianie posiada klasę czasowej złożoności obliczeniowej równą O(n²). Sortowanie odbywa się w miejscu.

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

Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni element zbioru. Jednoelementowa lista jest zawsze uporządkowana.
Ze zbioru zawsze wybieramy element leżący tuż przed listą uporządkowaną. Element ten zapamiętujemy w zewnętrznej zmiennej. Miejsce, które zajmował, możemy potraktować jak puste.
Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej.
Jeśli natrafimy na koniec listy, element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy jest większy od wybranego, to element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy nie jest większy od wybranego, to element listy przesuwamy na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Kontynuujemy porównywanie, aż wystąpi sytuacja z punktu 4 lub 5.

Przykład:

Dla przykładu wstawmy wg opisanej metody pierwszy element zbioru listę uporządkowaną utworzoną z pozostałych elementów {8 4 5 6 9}. Elementy listy uporządkowanej zaznaczyliśmy kolorem zielonym. Puste miejsce zaznaczyliśmy kolorem białym:

Zbiór Opis operacji

 8  4  5  6  9

Element 8 znajduje się tuż przed listą uporządkowaną.

 8 
    4  5  6  9

Wybieramy ze zbioru element 8. Zajmowane przez niego miejsce staje się puste.

    8 
    4  5  6  9

Porównujemy 8 z pierwszym elementem listy uporządkowanej, z liczbą 4.

    8 
 4 <<< 5  6  9

Ponieważ element 4 jest mniejszy od elementu wybranego 8, przesuwamy go na puste miejsce. Zwróć uwagę, iż puste miejsce wędruje w kierunku końca listy uporządkowanej.

       8 
 4     5  6  9

Porównujemy 8 z kolejnym elementem listy uporządkowanej, z liczbą 5.

       8 
 4  5 <<< 6  9

5 jest5 mniejsze od 8, zatem wędruje na puste miejsce, które przesuwa się przed kolejny element listy uporządkowanej, liczbę 6.

          8 
 4  5     6  9

Porównujemy 8 z 6.

          8 
 4  5  6 <<< 9

6 jest mniejsze od 8, wędruje na puste miejsce.

             8 
 4  5  6     9

Porównujemy 8 z 9.

 4  5  6  8  9

Tym razem element wybrany wędruje na puste miejsce, ponieważ jest mniejszy od elementu 9 listy uporządkowanej. Operacja wstawiania jest zakończona. Lista rozrasta się o jeden element.

Przykład:

Wykorzystajmy podane informacje do posortowania opisywaną metodą zbioru { 7 3 8 5 2 }.

Zbiór Opis operacji

 7  3  8  5  2

Ostatni element jest zalążkiem listy uporządkowanej.

          5 
 7  3  8     2

Ze zbioru wybieramy element leżący tuż przed listą uporządkowaną.

             5 
 7  3  8     2

Wybrany element porównujemy z elementem listy.

             5 
 7  3  8  2 <<<

Ponieważ element listy jest mniejszy od elementu wybranego, to przesuwamy go na puste miejsce.

 7  3  8  2  5

Na liście nie ma już więcej elementów do porównania, więc element wybrany wstawiamy na puste miejsce. Lista uporządkowana zawiera już dwa elementy.

       8 
 7  3     2  5

Ze zbioru wybieramy 8

          8 
 7  3     2  5

8 porównujemy z 2

          8 
 7  3  2 <<< 5

2 jest mniejsze, zatem przesuwamy je na puste miejsce.

             8 
 7  3  2     5

8 porównujemy z 5

             8 
 7  3  2  5 <<<

5 jest mniejsze, przesuwamy je na puste miejsce

 7  3  2  5  8

Lista nie zawiera więcej elementów, zatem 8 wstawiamy na puste miejsce. Na liście uporządkowanej mamy już trzy elementy.

    3 
 7     2  5  8

Ze zbioru wybieramy 3

       3 
 7     2  5  8

3 porównujemy z 2

       3 
 7  2 <<< 5  8

2 jest mniejsze, wędruje zatem na puste miejsce

          3 
 7  2     5  8

3 porównujemy z 5.

 7  2  3  5  8

Tym razem mniejszy jest element wybrany. Znaleźliśmy jego miejsce na liście, więc wstawiamy go na puste miejsce. Lista zawiera już 4 elementy.

 7 
    2  3  5  8

Ze zbioru wybieramy ostatni element - liczbę 7.

    7 
    2  3  5  8

7 porównujemy z 2

    7 
 2 <<< 3  5  8

2 jest mniejsze, przesuwamy je na puste miejsce

       7 
 2     3  5  8

7 porównujemy z 3

       7 
 2  3 <<< 5  8

3 jest mniejsze, przesuwamy je na puste miejsce

          7 
 2  3     5  8

7 porównujemy z 5

          7 
 2  3  5 <<< 8

5 jest mniejsze, przesuwamy je na puste miejsce

             7 
 2  3  5     8

7 porównujemy z 8

 2  3  5  7  8

Element wybrany jest mniejszy, wstawiamy go na puste miejsce. Lista uporządkowana objęła już cały zbiór. Sortowanie jest zakończone.

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 0 do n - 1.

Dane wyjściowe

d[ ]	- posortowany zbiór n-elementowy.

Zmienne pomocnicze

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

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe

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

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

K01:	Dla j = n - 2, n - 3, ...,0: wykonuj K02...K04
K02:	x ← d[j]; i ← j + 1
K03:	Dopóki ( i < n ) ∧ ( x > d[i] ): wykonuj d[i - 1] ← d[i]; i ← i + 1
K04:	d[i - 1] ← x
K05:	Zakończ

Informatyka dla klas II

Sortowanie danych

Porządek w zbiorze

Czasowa złożoność obliczeniowa

Sortowanie bąbelkowe

Uwaga:

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Sortowanie przez wybór

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Sortowanie przez wstawianie

Wstawianie elementu na listę uporządkowaną

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków