Algorytmy Sortujące

Sortowanie danych (ang. data sort) 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.

Artykuł ma na celu dokładne zapoznanie uczniów z podstawowymi algorytmami sortującymi, ich własnościami oraz umiejętnym doborem algorytmów sortujących dla danego zadania. 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.

Z problemem sortowania powiązane są problemy wyszukiwania danych. Dlatego zapraszamy naszych czytelników do zapoznania się z artykułem o algorytmach wyszukujących.

Prezentowane w artykule algorytmy wzbogaciliśmy o proste przykłady programów utworzonych w poniższych językach programowania::

Pascal (Lazarus)
C++ (Code::Blocks)
Basic (FreeBasic)
JavaScript (skrypt zwykle w kodzie strony)
Python (dodatek w 2026)

Wszystkie są darmowo dostępne w sieci Internet. Programy nie są celem artykułu, lecz jedynie dodatkiem do niego. Podstawą jest zawsze algorytm, który w artykule zostaje dokładnie omówiony. Dlatego programy dokładnie odzwierciedlają dany algorytm i nie stosujemy w nich różnych "sztuczek", które mają na celu poprawę ich efektywności. Pamiętaj, iż artykuł ten jest głównie przeznaczony dla zdolnego ucznia szkoły ponadpodstawowej i nie spełnia wymogów publikacji akademickiej.

do podrozdziału do strony

Zbiór uporządkowany (ang. ordered set) to taki, w którym elementy występują w określonym porządku, czyli kolejności. Jeśli elementy są liczbami, to porządek może być:

rosnący - każdy następny element zbioru jest większy od swojego poprzednika. W zbiorze nie ma elementów równych. Taki porządek nazywamy porządkiem mocnym.
Np. {0 2 4 7 12 13 16 74 125 200 333 ...}
malejący - każdy następny element jest mniejszy od swojego poprzednika. W zbiorze nie ma elementów równych - porządek mocny.
Np. (100 96 64 32 15 10 8 4 2 -4 -9 -22 ... }
niemalejący - każdy następny element jest równy lub większy od swojego poprzednika. Elementy o tych samych wartościach mogą występować wielokrotnie obok siebie. Taki porządek nazywamy porządkiem słabym.
Np. { 1 1 1 3 4 4 5 8 12 12 12 33 40 ... }
nierosnący - każdy następny element jest równy lub mniejszy od swojego poprzednika. Elementy o tych samych wartościach mogą się powtarzać - porządek słaby.
Np. {100 95 75 75 40 23 12 12 12 7 6 4 2 2 1 1 1 ... }

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.

do podrozdziału do strony

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 - memory complexity). 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·log(n))	-	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.

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×10¹⁰ sekund = 317 lat 1 miesiąc 4 dni 17 godzin 46 minut 40 sekund

Widzimy więc, iż algorytm ten spisuje się dobrze tylko przy niewielkiej liczbie elementów. Gdy liczba sortowanych elementów jest duża, czas oczekiwania na rozwiązanie może być nie do zaakceptowania. Dlatego właśnie informatycy poświęcili tak dużo swojego wysiłku na opracowanie odpowiednio szybkich algorytmów sortujących (te najszybsze mają klasę złożoności O(n log n)).

Oprócz złożoności czasowej rozważa się również złożoność pamięciową. Określa ona ilość zasobów komputera, których wymaga dany algorytm w zależności od liczby danych wejściowych. Tutaj także ma zastosowanie notacja omikron. Przy określaniu złożoności algorytmu należy wziąć pod uwagę oba typy złożoności obliczeniowej.

Ze względu na złożoność pamięciową algorytmy sortujące dzielimy na dwie podstawowe grupy:

Algorytmy sortujące w miejscu (ang. in place) - wymagają stałej liczby dodatkowych struktur danych, która nie zależy od liczby elementów sortowanego zbioru danych (ani od ich wartości). Dodatkowa złożoność pamięciowa jest zatem klasy O(1). Sortowanie odbywa się wewnątrz zbioru. Ma to bardzo istotne znaczenie w przypadku dużych zbiorów danych, gdyż mogłoby się okazać, iż posortowanie ich nie jest możliwe z uwagi na brak pamięci w systemie. Większość opisanych tu algorytmów sortuje w miejscu, co jest ich bardzo dużą zaletą.
Algorytmy nie sortujące w miejscu - wymagają zarezerwowania w pamięci dodatkowych obszarów, których wielkość jest uzależniona od liczby sortowanych elementów lub od ich wartości. Tego typu algorytmy są zwykle bardzo szybkie w działaniu, jednakże okupione to jest dodatkowymi wymaganiami na pamięć. Zatem w pewnych sytuacjach może się okazać, iż taki algorytm nie będzie w stanie posortować dużego zbioru danych, ponieważ system komputerowy nie posiada wystarczającej ilości pamięci RAM.

Algorytmy sortujące dzieli się również na dwie grupy:

Algorytmy stabilne - zachowują kolejność elementów równych. Oznacza to, iż elementy o tych samych wartościach będą występowały w tej samej kolejności w zbiorze posortowanym, co w zbiorze nieposortowanym. Czasami ma to znaczenie, gdy sortujemy rekordy bazy danych i nie chcemy, aby rekordy o tym samym kluczu zmieniały względem siebie położenie.
Algorytmy niestabilne - kolejność wynikowa elementów równych jest nieokreślona (zwykle nie zostaje zachowana).

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wstęp

Uwagi na temat języków programowania

Porządek w zbiorze

Czasowa złożoność obliczeniowa