- 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]
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.
