subota, 29. prosinca 2012.

Pripreme za algoritme(20)



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