Danas ćemo se baviti sa još nekoliko vrsta sortiranja.
Bubble sort
Ovo je zapravo poboljšano sortiranje zamjenom. Radi se o
istom principu samo se sortiranje prekida kada su brojevi u pravom redosljedu.
Dio programa za sortiranje:
granica:=n-1;
repeat
sortirano:= true;
for k:=1 to granica do
begin
if y[k]>y[k+1] then
begin
t:=y[k];
y[k]:=y[k+1];
y[k+1]:=t;
sortirano:=false;
end;
end;
granica:=granica-1;
until sortirano;
1.
|
2.
|
3.
|
4.
|
5.
|
zamjene
|
sortirano
|
|
true
|
|||||||
7
|
5
|
1
|
8
|
4
|
1. krug na intervalu od 1. do 5. elementa
|
y[1] i y[2]
|
false
|
5
|
7
|
1
|
8
|
4
|
y[2] i y[3]
|
false
|
|
5
|
1
|
7
|
8
|
4
|
y[4] i y[5]
|
false
|
|
5
|
1
|
7
|
4
|
8
|
stanje nakon 1. kruga
|
true
|
|
5
|
1
|
7
|
4
|
8
|
2. krug na intervalu od 1. do 4. elementa
|
y[1] i y[2]
|
false
|
1
|
5
|
7
|
4
|
8
|
y[3] i y[4]
|
false
|
|
1
|
5
|
4
|
7
|
8
|
stanje nakon 2. kruga
|
true
|
|
1
|
5
|
4
|
7
|
8
|
3. krug na intervalu od 1. do 3. elementa
|
y[2] i y[3]
|
false
|
1
|
4
|
5
|
7
|
8
|
stanje nakon 3. kruga
|
true
|
|
4. krug na intervalu od 1. do 2. elementa
|
y[1] i y[2]
|
true
|
Na odabranom primjeru se ne vidi ubrzanje bubble sort metode
jer su početni podaci u takvom rasporedu da se i jednom i drugom metodom izvodi
isti broj provjeravanja. Ova metoda je brža za slučaj da je samo nekoliko
podataka na krivom mjestu.
Npr.
1.
|
2.
|
3.
|
4.
|
5.
|
zamjene
|
sortirano
|
|
true
|
|||||||
1
|
8
|
4
|
5
|
7
|
1. krug na intervalu od 1. do 5. elementa
|
y[2] i y[3]
|
false
|
1
|
4
|
8
|
5
|
7
|
y[3] i y[4]
|
false
|
|
1
|
4
|
5
|
8
|
7
|
y[4] i y[5]
|
false
|
|
1
|
4
|
5
|
7
|
8
|
stanje nakon 1. kruga repeat petlje
|
true
|
|
1
|
4
|
5
|
7
|
8
|
2. krug na intervalu od 1. do 4. elementa
|
true
|
|
petlja se prekida jer su svi podaci sortirani
|
Sortiranje izlučivanjem
najvećeg elemenata iz intervala
U prvom prolasku kroz početni niz traži se najveći element.
Na kraju pretraživanja najveći element i onaj na kraju intervala zamjenjuju
mjesta. U svakom sljedećem prolasku interval koji gledamo smanjuje se za 1 sve
dok u zadnjem prolasku interval čine samo y[1] i y[2]. Očito je da je broj
ponavljanja vanjske petlje n-1 (n je
broj elemenata niza).
Ovaj način je nešto brži od sortiranja zamjenom
Dio programa za sortiranje:
for i:=n downto 2 do
begin
rbmax:=1;
for
j:=1 to i do
begin
if y[j]>y[rbmax] then rbmax:=j; {trazenje najveceg}
t:=y[rbmax]; {stavljanje najveceg pronadjenog na zadnje mjesto u
intervalu}
y[rbmax]:=y[i];
y[i]:=t;
end;
end;
1.
|
2.
|
3.
|
4.
|
5.
|
rbmax
|
zamjena
|
|
7
|
5
|
1
|
8
|
4
|
1. krug na intervalu od 1. do 5. elementa
|
4
|
y[4] i y[5]
|
7
|
5
|
1
|
4
|
8
|
2. krug na intervalu od 1. do 4. elementa
|
1
|
y[1] i y[4]
|
4
|
5
|
1
|
7
|
8
|
3. krug na intervalu od 1. do 3. elementa
|
2
|
y[2] i y[3]
|
4
|
1
|
5
|
7
|
8
|
4. krug na intervalu od 1. do 2. elementa
|
1
|
y[1] i y[2]
|
1
|
4
|
5
|
7
|
8
|
Sortiranje po
Shellu
Zamisao autora ovog algoritma je da se sortiranje može
ubrzati ako se početno uspoređuju i po potrebi međusobno zamjenjuju elementi koji
su smješteni na većem razmaku. Napredovanjem algoritma taj se razmak smanjuje
sve dok se ne dođe do razmaka duljine 1 kad se uspoređuju susjedni elementi.
Pokazalo se da je najjednostavnije za početni razmak uzeti polovicu broja
elemenata, a zatim ga smanjivati dijeljenjem s 2.
Dio programa za sortiranje:
udaljenost:=n;
while udaljenost>1 do begin
udaljenost
:=udaljenost div 2;
repeat
sortirano:=true;
for i:=1
to n-udaljenost do
if
y[i]>y[i+udaljenost] then
begin
t:=y[i];
y[i]:=y[i+udaljenost];
y[i+udaljenost]:=t;
sortirano:=false;
end;
until sortirano;
end;
ili isti kod na malo drugačiji
način
udaljenost:=n div 2; {pocetni razmak}
repeat
repeat
sortirano:=true;
for i:=1 to
n-udaljenost do
if
y[i]>y[i+udaljenost] then
begin
t:=y[i];
y[i]:=y[i+udaljenost];
y[i+udaljenost]:=t;
sortirano:=false;
end;
until sortirano;
udaljenost:=udaljenost
div 2;
until udaljenost<1;
1.
|
2.
|
3.
|
4.
|
5.
|
for
|
zamjene
|
udaljenost
|
sortirano
|
|
2
|
true
|
||||||||
7
|
5
|
1
|
8
|
4
|
1. krug repeat petlje
|
1 to 3
|
y[1] i y[3]
|
false
|
|
1
|
5
|
7
|
8
|
4
|
y[3] i y[5]
|
false
|
|||
1
|
5
|
4
|
8
|
7
|
stanje nakon 1. kruga
|
true
|
|||
1
|
5
|
4
|
8
|
7
|
2. krug petlje
|
1 to 4
|
y[2] i y[3]
|
1
|
false
|
1
|
4
|
5
|
8
|
7
|
y[4] i y[5]
|
false
|
|||
1
|
4
|
5
|
7
|
8
|
stanje nakon 2. kruga
|
0
|
true
|
Primjer sa 6 brojeva:
1.
|
2.
|
3.
|
4.
|
5.
|
6.
|
for
|
zamjene
|
udaljenost
|
sortirano
|
|
3
|
true
|
|||||||||
3
|
5
|
1
|
8
|
7
|
4
|
1. krug repeat petlje
|
1 to 3
|
true
|
||
3
|
5
|
1
|
8
|
7
|
4
|
stanje nakon 1. kruga
|
true
|
|||
1
|
true
|
|||||||||
3
|
5
|
1
|
8
|
7
|
4
|
2. krug repeat petlje
|
1 to 5
|
y[2] i y[3]
|
false
|
|
3
|
1
|
5
|
8
|
7
|
4
|
y[4] i y[5]
|
false
|
|||
3
|
1
|
5
|
7
|
8
|
4
|
false
|
||||
3
|
1
|
5
|
7
|
4
|
8
|
stanje nakon 2. kruga
|
||||
3
|
1
|
5
|
7
|
4
|
8
|
3. krug repeat petlje
|
1 to 5
|
false
|
||
1
|
3
|
5
|
7
|
4
|
8
|
false
|
||||
1
|
3
|
5
|
4
|
7
|
8
|
stanje nakon 3. kruga
|
1 to 5
|
|||
1
|
3
|
5
|
4
|
7
|
8
|
4. krug repeat petlje
|
1 to 5
|
false
|
||
1
|
3
|
4
|
5
|
7
|
8
|
stanje nakon 4. kruga
|
0
|
true
|
Ovaj način sortiranja je relativno brz (bitno brži od
prethodnih algoritama) pa ga treba koristiti kod većeg broja podataka.
U sljedećoj lekciji obraditi ćemo najbrži tip sortiranja.
U sljedećoj lekciji obraditi ćemo najbrži tip sortiranja.
Nema komentara:
Objavi komentar