Razni
načini sortiranja niza podataka
Sortiranje podataka je postupak kojim želimo bilo koju
kombinaciju ulaznih podataka postaviti u ulazni ili silazni redosljed. Postoje
razni algoritmi koji se međusobno razlikuju po složenosti odnosno brzini.
Brzina je važna kad moramo sortirati veliki
broj podataka (čest zahtjev u zadacima s natjecanja). Ovdje ćemo razmotriti
nekoliko načina. Smjer sortiranja će biti od najmanjeg prema najvećem.
Sortiranje
zamjenom susjednih elemenata
U prvom prolasku kroz početni niz uspoređuju se susjedni
elementi (y[k] i y[k+1]). Ako je element y[k] veći od y[k+1] što znači da nije
u pravom redosljedu zamjenjujemo im mjesto. Na taj način kada prođemo cijeli
interval na zadnjem mjestu u nizu biti će sigurno najveći broj. 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).
Ovo je najsporiji
način sortiranja koji možemo primjenjivati ako ne radimo s velikim brojem
podataka.
Dio programa za sortiranje:
for i:=n-1 downto 1 do
for j:=1 to i do begin
if y[j]>y[j+1]
then
begin
{zamjena susjednih
elemenata ako su u krivom poretku}
t:=y[j];
y[j]:=y[j+1];
y[j+1]:=t;
end;
end;
1.
|
2.
|
3.
|
4.
|
5.
|
zamjene
|
|
7
|
5
|
1
|
8
|
4
|
1. krug na intervalu od 1. do 5. elementa
|
y[1] i y[2]
|
5
|
7
|
1
|
8
|
4
|
y[2] i y[3]
|
|
5
|
1
|
7
|
8
|
4
|
y[4] i y[5]
|
|
5
|
1
|
7
|
4
|
8
|
stanje nakon 1. kruga
|
|
5
|
1
|
7
|
4
|
8
|
2. krug na intervalu od 1. do 4. elementa
|
y[1] i y[2]
|
1
|
5
|
7
|
4
|
8
|
y[3] i y[4]
|
|
1
|
5
|
4
|
7
|
8
|
stanje nakon 2. kruga
|
|
1
|
5
|
4
|
7
|
8
|
3. krug na intervalu od 1. do 3. elementa
|
y[2] i y[3]
|
1
|
4
|
5
|
7
|
8
|
stanje nakon 3. kruga
|
|
1
|
4
|
5
|
7
|
8
|
4. krug na intervalu od 1. do 2. elementa
|
Kod ovog sortiranja broj izvedenih zamjena ovisi o početnom
rasporedu podataka i naravno najnepovoljniji je onda kad su podaci sortirani u
suprotnom redu.
Nema komentara:
Objavi komentar