Triedenie poľa.
- je to usporiadanie poľa A[X..Y] aby platilo A[I]>=A[succ(I)] (zostupne) alebo A[I]<=A[succ(I)] (vzostupne), kde I je každý prípustný index poľa A z rozsahu X až Y-1. Index I je samozrejme ordinálneho typu.
Poznáme 3 druhy triedenia poľa: 1.Triedenie vsúvaním
2.Triedenie výberom
3.Triedenie výberom
Poznáme aj rekurzívny druh triedenia, ale pre komplikovanosť sa nim nebudeme zaoberať.
1.Triedenie vsúvaním:
Pole je rozdelené na 2 časti, utriedenú (A[D]..A[K]) a neutriedenú (A[K+1]..A[H]). Vyberie za zložka A[K+1] a vsunie sa medzi zložky A[U]..A[N] tak, že novovzniknutá časť je usporiadaná. Na vsunutie zložky použijeme lineárne alebo binárne vyhľadávanie. Proces treba opakovať tak, aby sme nakoniec dostali usporiadané pole.
Príklad na triedenie vsúvaním pomocou lineárneho vyhľadávania:
type typ=array[1..100] of integer;
var i:integer;
B:typ;
procedure TRIEDENIE (var A:typ; D,H:integer);
var I,J,K,M:integer;
begin
for K:=D+1 to H do
begin
M:=A[K];
I:=D;
while (M>A[I]) do I:=I+1;
A[J+1]:=M;
for J:=K-1 downto I do A[J+1]:=A[J];
A[I]:=M;
end;
end;
begin
randomize;
for i:=1 to 100 do B[i]:=random(10);
TRIEDENIE(B,20,30); {utriedi prvky 20 až 30 poľa B vzostupne}
end.
2.Triedenie výberom:
Pole je rozdelené na 2 časti, utriedenú (A[D]..A[K]) a neutriedenú (A[K+1]..A[H]) pričom však platí, že každá zložka usporiadanej časti je menšia ako lubovolna zložka neusporiadanej časti poľa. Vkladanie je na (K+1)-vé miesto a to takýmto spôsobom: Linearnym vyhľadávaním najdeme najmešiu zložku zo zložiek A[K+1]..A[H] a vymeníme ju zo zložkou A[K+1]. Príklad na triedenie výberom:
type typ=array[1..100] of integer;
var i:integer;
B:typ;
procedure TRIEDENIE (var A:typ; D,H:integer);
var I,J,K,M:integer;
begin
for I:=D to H-1 do
begin
J:=I;
for K:=I+1 to H do
if A[K]
M:=A[I];
A[I]:=A[J];
A[J]:=M;
end;
end;
begin
randomize;
for i:=1 to 100 do B[i]:=random(10);
TRIEDENIE(B,50,80); {utriedi prvky 50 až 80 poľa B vzostupne}
end.
3.Triedenie výmenou:
-bublinková metóda
Porovnávame 2 susedné zložky v neusporiadanej časti poľa a podľa potreby ich vymieňame.
Príklad na triedenie výmenou:
type typ=array[1..100] of integer;
var i:integer;
B:typ;
procedure TRIEDENIE (var A:typ; D,H:integer);
var I,J,KH:integer
BOLAVYMENA:boolean;
begin
BOLAVYMENA:=true;
KH:=H;
while (KH>D) and BOLAVYMENA do
begin
BOLAVYMENA:=false;
I:=D;
while I if A[I]>A[I+1] then begin
BOLAVYMENA:=true;
J:=A[I];
A[I]:=A[I+1];
A[I+1]:=J;
end;
I:=I+1;
end;
KH:=KH-1;
end;
begin
randomize;
for i:=1 to 100 do B[i]:=random(10);
TRIEDENIE(B,1,84); {utriedi prvky 1 až 84 poľa B vzostupne}
end.
Triedenie vsúvaním je oproti triedeniu výberom a výmenou je pomalšie. Rychlejšie je triedenie výmenou.