Sortiranje po Hoareu
(quicksort)
Ovo je jedan od najboljih postupaka sortiranja podataka. Kao
i u prethodnim slučajevima svodi se na pronalaženje dvaju elemenata koje treba
zamijeniti. Zamisao je sljedeća:
-
jedan element proglasi se glavnim
-
podaci se podijele u dva dijela: u prvi dio idu
elementi koji su manji od glavnog, u drugi dio idu elementi koji su veći od
glavnog
-
na ta dva dijela ponovno se primjenjuje ista
metoda sve dok se ne dođe do intervala duljine 1 elementa
a) Da bi mogli podijeliti niz brojeva u dva dijela potrebno
je glavni element smjestiti na njegovo pravo mjesto u sortiranom nizu. Za to
koristimo funkciju koja obavlja premještanje elemenata s vrijednostima manjim
od glavnog elementa na lijevu stranu, te premještanje elemenata s vrijednostima
većim od glavnog elementa na desnu stranu poretka. Funkcija pretražuje interval
s lijeve i desne strane i gleda jesu li brojevi veći ili manji od glavnog.
Pamti indeks onog elementa koji je na krivoj strani i zamjenjuje taj element i
glavni. Na kraju interval koji je funkcija pretraživala podijeljen je u dva
dijela. Lijevo od mjesta gdje je glavni element su podaci manji od njega, a
desno podaci koji su veći od njega. Naravno, mjesto glavnog elementa može biti
bilo koje mjesto i gledanom intervalu.
Dio programa za sortiranje:
function podjela(var
y:niz; var d,g:integer):integer;
var i, j, p,
glavni:integer;
neslozeno:boolean;
begin
glavni:=y[d]; {uzimamo 1. element iz intervala za glavni}
i:=d; {lijevi
interval počinjemo s donjom granicom}
j:=g; {desni
interval završavamo s gornjom granicom}
neslozeno:=true;
while neslozeno do
begin
while (y[i]<glavni)
and (i<g) do inc(i);
while
(y[j]>glavni) and (j>d) do dec(j);
{ovaj dio premješta element koji nije u pravom dijelu u dio
koji pripada}
if i<j then begin
p:=y[i];
y[i]:=y[j];
y[j]:=p;
end
else begin
podjela:=j;
neslozeno:=false;
end
end;
end;
procedure sort (var
y:niz; var donja_granica, gornja_granica:integer);
var p, r:integer;
begin
if donja_granica<gornja_granica
then
begin
p:=podjela(y,donja_granica,gornja_granica);
r:=p+1;
sort(y,
donja_granica,p);
sort(y,r,gornja_granica);
end;
end;
... u glavnom programu zovemo
proceduru sort
d_g:=1;
g_g:=n;
sort(y,d_g, g_g);
U ovom slučaju koristi se rekurzivna procedura (procedura
poziva samu sebe s drugim vrijednostima). U prvom pozivu procedura radi s
granicama d_g=1 i g_g=n, u sljedećem pozivu granice su one koje dobijamo
funkcijom podjela (funkcija vraća mjesto glavnog elementa u konačnom poretku).
1.
|
2.
|
3.
|
4.
|
5.
|
6.
|
d_g
|
g_g
|
glavni
|
smjer pretraživanja
|
i
|
j
|
zamjena
|
neslozeno
|
3
|
5
|
1
|
8
|
7
|
4
|
1
|
6
|
3
|
ß
|
1
|
3
|
y[1] i y[3]
|
|
1
|
5
|
3
|
8
|
7
|
4
|
à
|
2
|
3
|
y[2] i y[3]
|
true
|
|||
1
|
3
|
5
|
8
|
7
|
4
|
ß
|
2
|
2
|
y[2] i y[3]
|
false
|
Mjesto broja 3=2
p=2
r=3
1.
|
2.
|
3.
|
4.
|
5.
|
6.
|
d_g
|
g_g
|
glavni
|
smjer pretraživanja
|
i
|
j
|
zamjena
|
neslozeno
|
1
|
3
|
1
|
2
|
1
|
ß
|
1
|
1
|
false
|
Mjesto broja 1=1
p=2
r=3
1.
|
2.
|
3.
|
4.
|
5.
|
6.
|
d_g
|
g_g
|
glavni
|
smjer pretraživanja
|
i
|
j
|
zamjena
|
neslozeno
|
5
|
8
|
7
|
4
|
3
|
6
|
5
|
ß
|
3
|
6
|
y[3] i y[6]
|
true
|
||
4
|
8
|
7
|
5
|
à
|
4
|
6
|
y[4] i y[6]
|
true
|
|||||
4
|
5
|
7
|
8
|
ß
|
4
|
4
|
false
|
Mjesto broja 5=4
p=4
r=5
1.
|
2.
|
3.
|
4.
|
5.
|
6.
|
d_g
|
g_g
|
glavni
|
smjer pretraživanja
|
i
|
j
|
zamjena
|
neslozeno
|
4
|
5
|
3
|
4
|
4
|
3
|
4
|
true
|
||||||
ß
|
3
|
3
|
false
|
Mjesto broja 4=3
p=4
r=5
1.
|
2.
|
3.
|
4.
|
5.
|
6.
|
d_g
|
g_g
|
glavni
|
smjer pretraživanja
|
i
|
j
|
zamjena
|
neslozeno
|
7
|
8
|
5
|
6
|
4
|
5
|
6
|
true
|
||||||
ß
|
5
|
5
|
false
|
Mjesto broja 7=5
Konačno
1.
|
2.
|
3.
|
4.
|
5.
|
6.
|
1
|
3
|
4
|
5
|
7
|
8
|
b) U ovoj varijanti radimo samo s rekurzivnom procedurom.
Umjesto prvog člana u promatranom intervalu uzimamo srednji član.
Dio programa za sortiranje:
procedure sort(var y:niz; var donja_granica, gornja_granica:integer);
var p, glavni, i, j:integer;
begin
glavni:=y[(donja_granica+gornja_granica)div 2]; {uzimamo srednji element iz intervala za glavni}
i:=donja_granica;
j:=gornja_granica;
repeat
while y[i]<glavni do inc(i);
while
y[j]>glavni do dec(j);
if i<=j then
begin
p:=y[i];
y[i]:=y[j];
y[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if donja_granica<j then
sort(y, donja_granica,j);
if i<gornja_granica then
sort(y,i,gornja_granica);
end;
Prvi
poziv procedure u glavnom programu isti je kao i u prethodnom primjeru.
Nema komentara:
Objavi komentar