ortowanie jest chyba najbardziej sztandarowym zagadnieniem informatyki. Je╢li bΩdziesz mia│ z ni▒ kiedykolwiek do czynienia, sortowanie CiΩ na pewno nie ominie. Jest ono obecne wszΩdzie, chcia┐by przy tworzeniu tabelki w Wordzie. Nas jednak nie to interesuje. Spr≤bujΩ Ci przybli┐yµ w podstawowym stopniu zagadnienie sortowania, przedstawiµ kilka najpopularniejszych algorytm≤w u┐ywanych do tego. Nie bΩdΩ tutaj porusza│ matematycznych aspekt≤w z│o┐ono╢ci obliczeniowej, nie o to bowiem chodzi. Por≤wnamy jedynie kilka metod sortowania, kt≤re bΩdziesz m≤g│ potem zaimplementowaµ w swoich programach.
Na pocz▒tek nale┐y ustaliµ kilka rzeczy. Najpierw - co bΩdziemy sortowaµ. BΩd▒ to pewne obiekty(nie kojarzyµ z typem obiektowym!!!), np. napisy, liczby, znaki, rekordy. Ka┐dy z sortowanych obiekt≤w identyfikujemy za pomoc▒ tzw. klucza, czyli takiej jego czΩ╢ci, na podstawie kt≤rej mo┐na okre╢liµ wzglΩdne po│o┐enie pewnych obiekt≤w po posortowaniu. Brzmi to dosyµ zagmatwanie. Przyk│ad powinien jednak rozwiaµ w▒tpliwo╢ci. Przyjmijmy, ┐e mamy posortowaµ zbi≤r rekord≤w, z kt≤rych ka┐dy zawiera trzy pola: imie, nazwisko i wiek. Ot≤┐, je╢li sortujemy je wed│ug nazwiska, to w≤wczas m≤wimy, ┐e kluczem jest nazwisko. Gdyby╢my sortowali je wed│ug wieku, to wiek by│by kluczem. Chyba jest to jasne? W naszych przyk│adach bΩdziemy sortowaµ pojedyncze liczby umieszczone w tablicy. Tak wiΩc to w│a╢nie pojedyncze liczby bΩd▒ pe│niµ rolΩ kluczy.
Algorytm sortowania nazywamy stabilnym, kiedy podczas sortowania nie zostaje zmieniona wzajemna kolejno╢µ element≤w o tych samych kluczach. W zrozumieniu tego terminu pomo┐e nam przyk│ad. Przyjmijmy, ┐e mamy do posortowania tablicΩ z rekordami o dw≤ch polach: IMIE i NAZWISKO, a kluczem w procesie sortowania bΩdzie NAZWISKO. W tablicy tej znajduj▒ siΩ miΩdzy innymi dwa rekordy z identycznymi polami NAZWISKO, na przyk│ad Nowak. Jeden z nich ma pole IMIE="Jan", a drugi "Anna". Jan Nowak le┐y w tablicy na lewo od Anny Nowak. U┐yty przez nas algorytm jest stabilny, je╢li daje pewno╢µ, ┐e po posortowaniu Jan Nowak nadal bΩdzie bardziej na lewo w tablicy ni┐ Anna Nowak. Oczywi╢cie stabilno╢µ algorytmu sortowania jest po┐▒dana.
Innym wa┐nym elementem jest r≤wnie┐ z│o┐ono╢µ obliczeniowa algorytmu, czyli wielko╢µ informuj▒ca o ilo╢ci zasob≤w komptera zajmowanych przez program. Wi▒┐e siΩ z tym czas sortowania i ilo╢µ potrzebnej pamiΩci. To w│a╢nie czas wykonania zadania w tym problemie bΩdzie podstawowym kryterium przy wyborze algorytmu. Nie bΩdΩ tu przedstawia│ wywod≤w matematycznych, gdy┐ mo┐na je znale╝µ w fachowej literaturze. ChcΩ jedynie przedstawiµ zasady dzia│ania najpopularniejszych algorytm≤w.
Sortowanie b▒belkowe jest w miarΩ prostym sposobem sortowania. Polega ono na tym, ┐e tablicΩ przegl▒damy od do│u do g≤ry przy pomocy dw≤ch wska╝nik≤w, kt≤re maj▒ jedynie okre╢laµ obecnie analizowane pola tablicy. Wska╝niki te s▒ oddalone o jedno pole, wiΩc wystarczy zadeklarowaµ jedn▒ zmienn▒, dajmy na to WSK. Drugi wska╝nik oznaczamy w zale┐no╢ci od przyjΩtej konwencji jako WSK-1 lub WSK+1. Zmienna WSK bΩdzie wiΩc u┐ywana jako indeks tablicy. TablicΩ przegl▒damy w ten spos≤b, ┐e pocz▒tkowo wska╝niki znajduj▒ siΩ "na dole" tablicy. Tworzymy pΩtlΩ, w kt≤rej inkrementujemy ka┐d▒ zmienn▒, a┐ dojdziemy do ko±ca tablicy. Jednocze╢nie w ka┐dej pΩtli sprawdzamy, czy dana w tablicy pod indeksem ni┐szego wska╝nika jest wiΩksza od danej wskazywanej przez drugi, wy┐szy wska╝nik. Je╢li tak, to zamieniamy zawarto╢ci kom≤rek wskazywanych przez wska╝niki. W ten spos≤b przy pomocy pΩtli przegl▒damy ca│▒ tablicΩ. TΩ pΩtlΩ zagnie┐d┐amy w innej, kt≤ra bΩdzie wykonywana tak d│ugo, a┐ podczas jej wykonania nie zostanie wykonana ┐adna zamiana. Oznacza to, ┐e tablica jest ju┐ posortowana. Zrozumienie tego algorytmu sprowadza siΩ do zauwa┐enia faktu, i┐ w ka┐dym przebiegu zagnie┐d┐onej pΩtli najwiΩksza nieposortowana dot▒d warto╢µ jest "wypychana niczym b▒belek" na swoje ostateczne miejsce. I tak, w pierwszym przeszukaniu, najwiΩksza warto╢µ z tablicy zostaje umieszczona na ostatnim jej miejscu na prawo. W kolejnym przebiegu druga pod wzglΩdem wielko╢ci warto╢µ dostaje siΩ na ostateczne miejsce na przedostatnim miejscu w tablicy (ostatnie jest ju┐ zajΩte przez warto╢µ najwiΩksz▒).
Algorytm ten mo┐na bardzo │atwo zaimpelentowaµ, co pokazuje poni┐szy przyk│ad:
Program Babelki;
const n=5; {Ilo╢µ element≤w w tablicy}
type tablica = array[1..n] of integer;
var tab: tablica; {Tablica z losowymi danymi}
x: integer;
procedure sortuj_babelkowo(var t:tablica); {Procedura sortuj▒ca}
var
zmiana: boolean;{Czy w pΩtli wykonano zamianΩ}
wsk: integer;{Wska╝nik wy┐szy}
temp: integer;{Zmienna potrzebna przy zamianie}
begin
repeat
wsk:=1;
zmiana:=false;
while n>wsk do begin {Przeszukaj ca│▒ tablicΩ}
wsk:=wsk+1;
if t[wsk-1]>t[wsk] then begin {Zamieniaj}
zmiana:=true;
temp:=t[wsk];
t[wsk]:=t[wsk-1];
t[wsk-1]:=temp
end
end;
until zmiana=false {Tablica posortowana}
end;
begin
for x:=1 to n do tab[x]:=random(100); {Losowanie danych}
sortuj_babelkowo(tab) {Sortowanie}
end.
Pozostaje sprawdziµ z│o┐ono╢µ obliczeniow▒ tego algorytmu. Wyniki s▒ z│e: algorytm wykonuje siΩ nies│ychanie wolno. Jest to chyba najwolniejszy algorytm sortowania. O ile np. do posortowania 100 element≤w na szybkim komputerze wystarcza, o tyle posortowanie na tablicy z 30000 element≤w nawet na bardzo szybkim komputerze jest koszmarem ze wzglΩdu na niewsp≤│mierny wzrost ilo╢ci instrukcji do wzrostu element≤w do posortowania. W zasadzie algorytm ten nie ma ┐adnego zastosowania w rzeczywisto╢ci, wspomina siΩ o nim tylko przy wprowadzaniu do sortowania. Je╢li chcesz zrobiµ dobry program, w kt≤rym trzeba co╢ sortowaµ, to mo┐esz zapomnieµ o tym algorytmie. Jak stwierdzi│ wielki Nilaus Wirth, algorytm ten nie mo┐e nam zaoferowaµ nic poza zabawn▒ nazw▒.
Sortowanie przez selekcjΩ(wyb≤r) jest ju┐ nieco bardziej intuicyjne ni┐ b▒belkowe. Najpierw szukamy najmniejszego elementu w sortowanej tablicy, a potem zamieniamy go z elementem pierwszym od lewej. NastΩpnie znowu szukamy najmniejszego elementu, ale tym razem na prawo od poprzednio ustawionego(pierwszego) i zamieniamy go z elementem drugim. NastΩpnie zn≤w znajdujemy najmniejszy element, ale na prawo od drugiego. Zamieniamy go z trzecim. W ten spos≤b postΩpujemy, a┐ tablica zostanie posortowana, czyli n-1 razy, gdzie n - ilo╢µ element≤w tablicy. Ten algorytm jest do╢µ prosty, bardziej intuicyjny, lecz jego implementacja mo┐e wydawaµ siΩ minimalnie bardziej z│o┐ona od algorytmu b▒belkowego. Nie nale┐y siΩ jednak zniechΩcaµ. Poni┐ej podajΩ znowu przyk│ad, w kt≤rym mamy posortowaµ tablicΩ n element≤w:
Program Selekcja;
const n=20; {Ilo╢µ element≤w w tablicy}
type tablica = array[1..n] of integer; {Typ tablicy}
var tab: tablica; {Tablica z losowymi danymi}
x: integer; {Licznik iteracji}
procedure sortuj_selekcja(var t:tablica); {Procedura sortuj▒ca}
var
l: integer; {Lewa granica nie posortowanego ci▒gu}
min: integer; {Indeks aktualnie najmiejszego elementu}
i: integer; {Licznik iteracji przy znajdowaniu najmniejszej warto╢ci}
temp: integer; {Zmienna potrzebna przy zamianie element≤w}
begin
for l:=1 to n-1 do {Dla ka┐dego elementu}
begin
min:=l; {Pocz▒tkowy indeks najmniejszego}
for i:=l+1 to n do {Dla ka┐dego elementu na prawo od posortowanych}
if t[min]>t[i] then min:=i; {Znajduj indeks najmniejszego}
temp:=t[l]; {Pocz▒tek zamiany}
t[l]:=t[min];
t[min]:=temp {Koniec zamiany}
end
end;
begin
for x:=1 to n do tab[x]:=random(100); {Losowanie danych}
sortuj_selekcja(tab) {Sortowanie}
end.
Sortowanie przez wstawianie polega na wstawianiu po kolei ka┐dego elementu tablicy pocz▒wszy od drugiego w uporz▒dkowan▒ czΩ╢µ tablicy na lewo od aktualnie wstawianego elementu. Odbywa siΩ to w ramach nastΩpuj▒cego algorytmu:
Program Selekcja;
const n=20; {Ilo╢µ element≤w w tablicy}
type tablica = array[0..n] of integer; {Typ tablicy}
var tab: tablica; {Tablica z losowymi danymi}
x: integer; {Licznik iteracji}
procedure sortuj_wstawianie(var t:tablica); {Procedura sortuj▒ca}
var
i: integer; {Wskazuje na obecnie wstawiany element}
j: integer; {Wskazuje na miejsce do wstawienia}
w: integer; {Warto╢µ wstawianego elementu}
begin
for i:=2 to n do begin {Dla ka┐dego elementu opr≤cz pierwszego}
j:=i;
w:=t[i]; {Wstawiany element - warto╢µ}
while (t[j-1]>w) do begin {Szukanie miejsca}
t[j]:=t[j-1];
j:=j-1;
end;
t[j]:=w; {Wstawianie}
end;
end;
begin
tab[0]:=-10; {-niesko±czono╢µ}
for x:=1 to n do tab[x]:=random(100); {Losowanie}
sortuj_wstawianie(tab);{Sortowanie}
end.
A teraz obja╢nienia. Zmiennej w przypisuje siΩ wstawian▒ warto╢µ, a nastΩpnie na lewo od tej warto╢ci postΩpuje siΩ w ten spos≤b, ┐e wy┐szemu elementowi przypisuje siΩ warto╢µ mniejszego s▒siada przesuwaj▒c siΩ jednocze╢nie zawsze o jeden indeks w lewo. Tak postΩpuje siΩ, a┐ mniejszy s▒siad na kt≤rym siΩ zatrzymali╢my bΩdzie wiΩkszy od w. W≤wczas mo┐na mu przypisaµ warto╢µ w. W instrukcji wstawiania mamy indeks J a nie J-1, bo zosta│ on w ostatniej pΩtli zmniejszony o jeden.
Trzeba sobie powiedzieµ jeszcze o dodatkowym elemencie jakim jest tab[0]. Jest to "-niesko±czono╢µ". Chodzi o to, ┐e w pΩtli w procedurze sortuj▒cej mog│oby doj╢µ do wyj╢cia poza zakres tablicy przy sprawdzaniu warunku. Sta│oby siΩ tak, gdyby╢my pr≤bowali wstawiµ najmniejszy element tablicy. Dlatego w│a╢nie dodajemy jeden indeks tablicy. Chodzi o to, zby mia│ on warto╢µ mniejsz▒ ni┐ jakakolwiek liczba w tablicy. W ten spos≤b zawsze ka┐da liczba bΩdzie wstawiania na prawo od niego. Warto╢µ -10 jest przypadkowa. U nas wystarczy dowolna liczba ujemna, co wynika z przedzia│u liczb dostarczanych prez funkcjΩ RANDOM, kt≤ra nigdy nie poda warto╢ci ujemnych.
Sortowanie szybkie (quicksort) jest w praktyce najczΩ╢ciej u┐ywanym algorytmem, gdy┐ daje on najlepsze wyniki dla losowych danych. RadzΩ por≤wnaµ szybko╢ci dzia│ania program≤w opartych na poznanych metodach sortowania i skompilowanych w Turbo Pascalu. Oka┐e siΩ, ┐e quicksort daje rezultaty naprawdΩ rewelacyjne. Nawet dla ogromnej liczby danych sortowanie przebiega bardzo szybko.
Spos≤b dzia│ania tego algorytmu jest ju┐ bardziej z│o┐ony i jego zrozumienie wymaga dok│adnego zastanowienia. Najpierw przyjmijmy, ┐e sortowany przez nas ci▒g jest ograniczony od lewej indeksem l, a od prawej indeksem p. Wybieramy sobie element wskazywany przez indeks l. Naszym zadaniem jest takie przekszta│cenie ci▒gu, aby po lewej stronie wybranego elementu znalaz│y siΩ wszystkie elementy mniejsze od niego, a po prawej wszystkie elementy wiΩksze od niego. Elementy r≤wne niemu mog▒ siΩ znale╝µ po dowolnej jego stronie. NastΩpnie, postΩpujemy identycznie z podci▒giem na lewo od wybranego, umieszczonego ju┐ w ostatecznym miejscu elementu. Identycznie robimy z podci▒giem na prawo od tego┐ elementu. Ca│a filozofia sprowadza siΩ do tego, ┐eby wybrany element umie╢ciµ w ostatecznym miejscu. BΩdziemy potrzebowaµ do tego dw≤ch zmiennych bΩd▒cych wska╝nikami odpowiednich p≤l tablicy. Jeden bΩdziemy przesuwaµ przez ci▒g od lewej do prawejs strony a┐ do znalezienia elementu wiΩkszego lub r≤wnego wybranemu. NastΩpnie podobnie postΩpujemy, przesuwaj▒c drugi wska╝nik od prawej do lewej a┐ do znalezienia elementu mniejszego lub r≤wnemu wybranemu. Je╢li wska╝niki podczas przesuwania siΩ nie minΩ│y, tzn. lewy wskazuje warto╢µ bardziej na lewo ni┐ prawy, wskazywane przez nie pola zamieniamy miejscami. PostΩpujemy w ten spos≤b a┐ do wyminiΩcia siΩ wska╝nik≤w. W≤wczas wybrany element trzeba zamieniµ z elementem wskazywanym przez wska╝nik kt≤ry zacz▒│ przeszukiwanie od lewej strony. Potem wywo│ujemy rekurencyjnie sortowanie podci▒gu miΩdzy pierwszym elementem z lewej a elementem wskazywanym przez wska╝nik, kt≤ry wΩdrowa│ od lewej strony. Identycznie wywo│ujemy sortowanie dla podci▒gu miΩdzy elementem wskazywanym przez wska╝nik, kt≤y wΩdrowa│ od lewej, a ostatnim elementem z prawej. Oczywi╢cie przedtem nale┐y sprawdziµ, czy ci▒g, kt≤rego sortowanie chcemy rekurencyjnie wywo│aµ, ma d│ugo╢µ wiΩksz▒ ni┐ 1. A oto implementacja algorytmu:
Program Quicksort;
const
n = 20; {Ilo╢µ obiekt≤w w tablicy}
var
t: array[0..n+1] of integer; {Deklaracja tablicy z elementami do sortowania}
x:integer; {Licznik iteracji}
procedure Sortowanie_szybkie(l,p:integer); {Procedura sortuj▒ca tablicΩ}
var
lw,pw: integer; {Wska╝niki wΩdruj▒ce w prawo (lw) i w lewo (pw)}
temp: integer; {Zmienna pomocnicza pomagaj▒ca zamieniµ dwa pola tablicy}
begin
lw:=l;
pw:=p+1;
repeat
repeat
lw:=lw+1;
until t[lw]>=t[l];
repeat
pw:=pw-1;
until t[l]>=t[pw];
if lw<pw then begin {Je╢li siΩ nie rozminΩ│y}
temp:=t[lw]; {Zamiana}
t[lw]:=t[pw]; {odpowiednich}
t[pw]:=temp; {warto╢ci}
end;
until lw>=pw; {A┐ siΩ rozmin▒}
temp:=t[l]; {Wstawianie wybranego}
t[l]:=t[pw]; {elementu w}
t[pw]:=temp; {odpowiednie miejsce}
if lw-l>1 then sortowanie_szybkie(l,lw-1); {Sortuj ci▒g z lewej}
if p-pw>1 then sortowanie_szybkie(pw+1,p); {Sortuj ci▒g z prawej}
end;
begin
t[n+1]:=101;
t[0]:=-1;
for x:=1 to n do t[x]:=random(100);
sortowanie_szybkie(1,n); {Sortowanie}
end.
Dodatkowe pola w tablicy o indeksach 0 i n+1 zapobiegaj▒ wyj╢ciu poza tablicΩ w czasie przeszukiwania jej przy pomocy wska╝nik≤w.
