referaty.sk – Všetko čo študent potrebuje
Lenka
Štvrtok, 4. júna 2020
Pascal - algoritmy na triedenie poľa
Dátum pridania: 30.11.2002 Oznámkuj: 12345
Autor referátu: sova
 
Jazyk: Slovenčina Počet slov: 235
Referát vhodný pre: Stredná odborná škola Počet A4: 0.6
Priemerná známka: 2.97 Rýchle čítanie: 1m 0s
Pomalé čítanie: 1m 30s
 
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.
 
   1  |  2    ďalej ďalej
 
Copyright © 1999-2019 News and Media Holding, a.s.
Všetky práva vyhradené. Publikovanie alebo šírenie obsahu je zakázané bez predchádzajúceho súhlasu.