Sortowanie

Sortowanie to jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwieniu stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.

Wiadomosci wstępne

Sortowanie to proces ustawiania zbioru obiektów w określonym porządku. Jest on stosowany w celu ułatwienia późniejszego wyszukiwania elementów. W wielu dziedzinach ta działalność jest podstawowa i w zasadzie jedyna. Przykłady to tworzenie katalogów bibliotecznych, książek telefonicznych itp. Istnieje wiele sposobów (algorytmów) sortowania. Wybór zależy od struktury przetwarzanych danych.

Rozróżniamy.

• metody sortowania tablic (metody wewnętrzne), ponieważ tablice przechowywane są w najczęściej w wewnętrznej pamięci operacyjnej,

• metody sortowania plików (metody zewnętrzne) - pliki są najczęściej przechowywane w wolniejszych lecz bardziej pojemnych pamięciach zewnętrznych.

Różnice tak zdefiniowanych zadań ilustruje przykład sortowania kart:

• sortowania tablicy to sortowanie odkrytych, leżących na stole kart,

• sortowanie pliku to sortowanie talii, gdy widoczne są tylko karty leżące na wierzchu.

Metodę sortowania nazywamy stabilną, jeżeli podczas procesu sortowania pozostaje nie zmieniony względny porządek obiektów o identycznych kluczach. Jest to istotna cecha, gdy dysponujemy pewnymi uporządkowanymi już podciągami według tzw. drugorzędowych kluczy.

Podstawowe wymaganie stawiane algorytmom sortowania tablic to oszczędność pamięci. Wszystkie działania powinny być wykonywane in situ (w miejscu). Metody operujące na dwóch tablicach: wejściowej i wynikowej mają mniejsze znaczenie.

Miarą efektywności metody mogą być:

• liczba Po koniecznych porównań kluczy,

• liczba Pr koniecznych przesunięć obiektów.

Dobre algorytmy sortowania wymagają nlog₂(n) porównań. Na wstępie omówimy tzw. metody proste wymagające rzędu (około) n porównań. Za metodami prostymi przemawiają następujące fakty.

• są one proste i nadają się do wyjaśnienia głównych zasad sortowania,

• realizujące je procedury są krótkie, a programy też zajmują pamięć,

• skomplikowane metody są lepsze dopiero dla dużych n.

 

Sortowanie przez proste wstawianie

Metoda sortowania przez proste wstawianie jest stosowana powszechnie przez grających w karty. Ciąg (tablicę) dzielimy umownie na:

ciąg wynikowy a¹ . . a^i-l

ciąg źródłowy aⁱ . . . aⁿ .

W każdym kroku, począwszy od i=2, zwiększając i o jeden, i-ty element ciągu  źródłowego przenosi się do ciągu wynikowego, wstawiając go w odpowiednim  miejscu. Proces ten można zapisać w postaci następującego algorytmu:

for i:=2 to n do   begin     x:=a[i]; 1 i , ,     " wstaw x w odpowiednim miejscu w a^1 ...a^i   end

Ilustruje to poniższy przykład:

Start	44	55	12	42	94	18	06	67
i=2	44	55	12	42	94	18	06	67
i=3	12	44	55	42	94	18	06	67
i=4	12	42	44	55	94	18	06	67
i=5	12	42	44	55	94	18	06	67
i=6	12	18	42	44	55	94	06	67
i=7	06	12	18	42	44	55	94	67
i=8	06	12	18	42	44	55	67	94

Podczas znajdowania odpowiedniego miejsca wygodnie jest stosować na przemian  porównania i przesunięcia:

• "przesiewać" x przez porównanie go z następnym obiektem a[j],

• następnie albo wstawić x albo przesunąć a[j] na prawo,

• postąpić analogicznie z kolejnym elementem na lewo.

Zakończenie tego procesu może nastąpić z dwóch powodów.

• znalezienia obiektu a[j] o kluczu mniejszym niż klucz x,

• osiągnięcia lewego końca ciągu wynikowego.

Jest to przykład iteracji z dwoma warunkami kończącymi. Pełny algorytm jest sformułowany poniżej. W elemencie o indeksie 0 "trzymamy" przestawiany element. Pełni on rolę wartownika, kończącego jeden z warunków procesu.

procedure ProsteWstawianie;   var     i,j : Indeks;     x   : Obiekt;   begin     for i:=2 to n do     begin              { petla po elementach ciagu poczawszy 0d drugiego }       x := a[i];       { x - element, ktory chcemy przestawic }       a[0] := x;       { "wartownik", element ciagu o indeksie O }       j := i-l;        { j - miejsce gdzie chcemy wstawic x }       while x.Klucz < a[j].Klucz do    { petla szukania miejsca dla x }       begin            { jesli klucz x'a jest mniejszy od klucza a[jl }         a[j+l].=a[j];  { przesuwamy wyrazy ciagu o jeden "w prawo" }         j := j-l       { szukamy dalej miejsca dla x - zmniejszamy j }       end;             { UWAGA: petla moze chodzic az do j=0 }       a[j+l] := x      { po sukcesie przemieszczamy wyraz x }     end   end;

Algorytm prostego wstawiania można łatwo poprawić, jeżeli zauważymy, że ciąg wynikowy a¹...a^i-1, w którym należy umieścić obiekt, jest już uporządkowany. Można więc zastosować szybszą metodę ustalenia miejsca wstawienia nowego obiektu. Najprostsze rozwiązanie to przeszukiwanie połówkowe - próbkowanie ciągu wynikowego w środku, podział na połowę, aż do znalezienia miejsca wstawienia nowego obiektu.

Wyobraźmy sobie przeszukiwanie tablicy a[l..n], którego celem jest znalezienie najmniejszego indeksu i składowej o wartości x. Realizuje to następujący ciąg instrukcji:

i:=0;   repeat     i:=i+l   until (a[i]=x) or (i=n)   if a[i]<>x then " nie ma "

W zacytowanym fragmencie programu są dwa warunki kończące pętlę: a[i]=x lub  i=n. Zamiast tego podwójnego warunku, którego wielokrotne sprawdzanie jest kosztowne, możemy ustawić na końcu tablicy wartownika, co uprości znacznie warunek zakończenia iteracji. W tym przypadku tablica musi być inaczej zadeklarowana (trzeba przewidzieć wyraz o indeksie n+l - a[l..n+l]). Fragment programu realizujący to przeszukiwanie ulegnie niewielkiej modyfikacji.

i:=0; a[i+l]:=x;   repeat     i:=i+l   until a[i]=x   if i>n then " nie ma "

I

nstrukcja przypisania a[n+l]:=x to tzw. aktualizacja selektywna (dotyczy ona tylko jednego elementu tablicy). Bez względu na liczbę wykonań instrukcji i:=i+l - czyli bez względu na wielkość i - dla j=l. . i-l zawsze jest spełniony warunek a[j]<>x nazywany niezmiennikiem pętli.

W przypadku gdy elementy rozpatrywanego ciągu zostały wstępnie uporządkowane można zastosować metodę bisekcji (przeszukiwania połówkowego).

Metoda bisekcji może być zastosowana do poszukiwania miejsca zerowego funkcji w przedziale, w którym jest dokładnie jeden taki punkt.

W naszym zadaniu zrealizuje ją następujący ciąg instrukcji:

i:=l; j:=n;          { i - lewy koniec ciagu, j - prawy }   repeat     k'=(i+j) div 2;    { k - punkt srodkowy przeszukiwanego ciagu }     if x>a[k] then     { jezeli x jest na prawo od punktu srodkowego }       i:=k+l           { lewy koniec ciagu staje sie rowny k+l }     else               { x jest na prawo od punktu srodkowego }       j:=k-l           { prawy koniec przedzialu staje sie k-l }   until (a[k]=x) or (i>j)

Na końcu pętli pojawia się znowu podwójny warunek. Jeżeli po wykonaniu powyższego ciągu instrukcji i>j to znaczy, że nie istnieje taki element ciągu, że a[m]=x, l~m~n. Powracając do metod sortowania bisekcję wykorzystamy formułując algorytm ..

Sortowania przez przeszukiwanie i wstawianie połówkowe.

procedure WstawianiePolowkowe.   var     i,j,l,p,m   : Indeks;     x           : Obiekt;   begin     for i: =2 to n do          { petla po poszczegolnych elementach tablicy }     begin       x := a[i];               { zmienna robocza x - wyraz a[il }       l:=1;                    { startowy lewy koniec ciagu }       p:=i-l;                  { startowy prawy koniec ciagu }       while l<=p do            { ogranicznik konczacy proces poszukiwania }       begin         m:=(l+p) div 2;        { m - punkt miedzy lwym i prawym }         if x.klucz<a[m] then   { jezel i x " na lewo" od m }           p:=m-l               { prawy koniec przedzialu staje sie m-l }         else                   { jezeli x "na prawo" od m }           l:=m+l               { lewy koniec przedzialu staje sie m+l }       end       for j:=i-l downto 1 do   { petla przesuwajaca elementy }         a[j+l]:=a[j];          { przesuniecie elementu }         a[l]:=x;               { przestawienie elementu x w miejsce a[ll }      end   end;

W metodzie przeszukiwania połówkowego zmniejsza się tylko liczba niezbędnych porównań. Liczba niezbędnych przesunięć pozostaje niezmieniona. Ponieważ przesuwanie sortowanych obiektów jest w praktyce znacznie kosztowniejsze od porównywania usprawnienie nie jest znaczące. Co więcej algorytm ten w przypadku powtórnego sortowania uporządkowanej tablicy zabiera więcej czasu niż proste wstawianie z liniowym przeszukiwaniem. Jest to rodzaj memento. oczywiste ulepszenia mogą mieć często znaczenie marginalne lub powodować nawet skutek odwrotny do zamierzonego.

5

---