8594

1. Sortowanie

Proces porządkowania danych nazywa się w programowaniu sortowaniem. Porządkowanie może oznaczać uszeregowanie danych różnowartościowych w porządku rosnącym lub malejącym. Jeśli dane powtarzają się to można je uszeregować niemalejąco lub nierosnąco. Sortować można zarówno dane numeryczne jak i nienumeryczne, np.: można porządkować znaki według ich kolejności występowania w alfabecie. Sposób sortowania zależy między innymi od struktury danych, w której zapisane zostały porządkowane informacje. Ten wykład poświęcony jest sortowaniu tablic i omówione zostaną w nim cztery różne algorytmy pozwalające rozwiązać ten problem. W ostatniej części wykładu zostaną omówione operacje znajdowania maksimum i minimum, które ulegają znacznemu uproszczeniu w tablicach posortowanych, a także zostanie zaprezentowany algorytm wyszukiwania¹ dla tablic posortowanych, który jest wydajniejszy od tych. które są stosowane dla tablic nieposortowanych.

2. Algorytmy sortowania tablic

Wszystkie opisane tu algorytmy będą algorytmami sortowanie wewnętrznego, tzn. cały proces sortowania będzie odbywał się z użyciem pamięci wewTiętrznej. natomiast żadne dane nie będą zapisywane na dysku podczas tej czynności. Dodatkowo sortownie wykonywane przez te algorytmy będzie sortowaniem stabilnym - jeśli w tablicy znajdą się dwie jednakowe wartości, to ich początkowa kolejność względem siebie nie będzie zmieniona po wykonaniu sortowania. Ta cecha tej operacji ma znaczenie w przypadku, kiedy sortujemy zestawy danych, takie jak rekordy, które poznamy na kolejnych wykładach. Załóżmy, że każdy z takich zestawów zawiera takie dane jak imię i nazwisko osoby i że chcemy je posortować według właśnie tych danych. Musimy to zrobić w dwóch krokach: najpierw posortować według nazwisk, następnie według imion^{2 3} lub odwrotnie. Załóżmy, że posortowaliśmy nasze zestawy według imion, a następnie sortujemy je w^redług nazwisk. Jeśli sortowanie byłoby niestabilne, to porządek imion mógłby zostać zakłócony i np.: dane Jana Kowalskiego mogłyby się znaleźć przed danymi Anny Kowalskiej. Wszystkie algorytmy, które zostaną tu opisane mają jeszcze jedną cechę: wykonują sortow^ranie w miejscu, tzn. do wykonania operacji sortowania wystarczy tablica, w której przechowywane są dane, nie potrzebna jest dodatkow^ra pamięć, w której przechowywane byłyby wartości elementów podczas sortowania'¹.

2

1

   Operacje wyszukiwani i sortowania, według D.E.Knutha są najczęściej wykonywanymi operacjami przez współczesne komputery.

2

   To według czego sortujemy takie zestawy danych nazywamy kluczami.

3

   To stwierdzenie nie do końca Jest prawdziwe, bo są potrzebne zmienne przechowujące pojedyncze wartości elementów. Jeśli algorytm nie sortuje w miejscu, to oznacza, że podczas tej czyn-