Informatyka dla klas II

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.

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.

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:

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).

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.

 5 4 3 2 1 

 4 5 3 2 1 

 4 3 5 2 1 

 4 3 2 5 1 

 4 3 2 1 5 

 4 3 2 1 5 

 3 4 2 1 5 

 3 2 4 1 5 

 3 2 1 4 5 

 3 2 1 4 5 

 3 2 1 4 5 

 2 3 1 4 5 

 2 1 3 4 5 

 2 1 3 4 5 

 2 1 3 4 5 

 2 1 3 4 5 

 1 2 3 4 5 

 1 2 3 4 5 

 1 2 3 4 5 

 1 2 3 4 5 

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).

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

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.

 4 7 2 9 3  

 2 7 4 9 3 

 2 7 4 9 3 

 2 3 4 9 7 

 2 3 4 9 7 

 2 3 4 9 7 

 2 3 4 9 7 

 2 3 4 7 9 

 2 3 4 7 9 

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

Zmienne pomocnicze

i, j	- zmienne sterujące pętli, i, j  N
pmin	- pozycja elementu minimalnego w zbiorze d[ ],  pmin 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:

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:

 8  4  5  6  9 

 8 
    4  5  6  9 

    8 
    4  5  6  9 

    8 
 4 <<< 5  6  9 

       8 
 4     5  6  9 

       8 
 4  5 <<< 6  9 

          8 
 4  5     6  9 

          8 
 4  5  6 <<< 9 

             8 
 4  5  6     9 

 4  5  6  8  9 

Przykład:

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

 7  3  8  5  2 

          5 
 7  3  8     2 

             5 
 7  3  8     2 

             5 
 7  3  8  2 <<<

 7  3  8  2  5 

       8 
 7  3     2  5 

          8 
 7  3     2  5 

          8 
 7  3  2 <<< 5 

             8 
 7  3  2     5 

             8 
 7  3  2  5 <<<

 7  3  2  5  8 

    3 
 7     2  5  8 

       3 
 7     2  5  8 

       3 
 7  2 <<< 5  8 

          3 
 7  2     5  8 

 7  2  3  5  8 

 7 
    2  3  5  8 

    7 
    2  3  5  8 

    7 
 2 <<< 3  5  8 

       7 
 2     3  5  8 

       7 
 2  3 <<< 5  8 

          7 
 2  3     5  8 

          7 
 2  3  5 <<< 8 

             7 
 2  3  5     8 

 2  3  5  7  8 

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

Zmienne pomocnicze

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