Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Vnitřní řazení v poli (in sito)

K seřazení položek použijeme metodu pří-mého výběru (straight selection).Princip: Ze všech položek vektoru vyber nejmenší hodnotu.Vyměň vzájemně nalezenou hodnotu s hodnotou v prvé položce vektoru.Poté vyber nejmenší prvek ze zbylých N-1 prvků (z 2. až N-té
Vnitřní řazení v poli (in sito) Je dán vektor N čísel (celých, K seřazení položek použijeme metodu pří-mého výběru (straight selection).Princip: Ze všech položek procedure STRSEL(var POLE:A; N:INDEX);  var I,J,K: INDEX; K seřazení položek použijeme metodu pří-mého vkládání (straight insertion).Princip: V i-tém kroku procedure STRINS(var POLE:A; N:INDEX);  var I,J :INDEX; K seřazení položek vektoru použijeme některou z metod přímé výměny. Metody jsou procedure BUBBLE(var POLE:A; N:INDEX); var I,J :INDEX;    POM :SLOZKA; b) u bublinového řazení s výhodou (tzv. Ripple sort) je vzata v procedure RIPPLE(var POLE:A; N:INDEX);  var J,I : INDEX; c) Další modifikací je Shaker sort. Princip: V určitém kroku prohlížíme řazený procedure SHAKER(var POLE:A; N:INDEX);  var I,J,H,D : INDEX; Předchozí 3 metody (Bubble, Ripple a Shaker sort) vycházely z principu, že procedure SHUTT(var POLE:A; N:INDEX); var I :INDEX;   POM :INTEGER; begin K seřazení většího množství dat se používají duchaplnější metody, z nichž jmenujme procedure QUICK(var POLE:A; N: INDEX);  const M = 12;  type Rekurzivní obdoba předchozího algoritmu:procedure QUICKR(var POLE:A; N: INDEX);  procedure SORT(H,D : Verzí je možno vytvořit mnoho. PřístupQUICK1PRESKUPQUICK1QUICK1…... postihuje algoritmus s procedurami PRESKUP a QUICK1 Procedure PRESKUP(DM,HM:byte; var J:byte); Algoritmus založený na metodě QUICKsort přináší také následující řešení:Program QUICKSORT000; uses CRT; Použití každé z výše uvedených řadících procedur vyžaduje stejné definice a deklarace. Metoda Shell sort, neboli Shellova metoda řazení (řazení se snižujícím se přírůstkem) Následující program má stejnou logiku jako poslední výše uvedený program. Za povšimnutí procedure SHELL(var POLE:A; N: INDEX);    type STRUKTURA begin    write('Zadej pocet nacitanych hodnot ke trideni: '); 79K posouzení efektivnosti zmíněných metod poslou-ží následující tab. časové náročnosti uvedených metod. Závěrem tohoto příkladu ještě jednou poznamenejme, že tvar všech výše uvedených algoritmů
Слайды презентации

Слайд 2 K seřazení položek použijeme metodu pří-mého výběru (straight

K seřazení položek použijeme metodu pří-mého výběru (straight selection).Princip: Ze všech

selection).

Princip:
Ze všech položek vektoru vyber nejmenší hodnotu.
Vyměň vzájemně

nalezenou hodnotu s hodnotou v prvé položce vektoru.
Poté vyber nejmenší prvek ze zbylých N-1 prvků (z 2. až N-té položky) a vyměň ho s druhou položkou atd. až zůstane poslední N-tý (maximální) prvek.

Слайд 3 procedure STRSEL(var POLE:A; N:INDEX);
var I,J,K: INDEX;

procedure STRSEL(var POLE:A; N:INDEX); var I,J,K: INDEX;   POM: SLOZKA;


POM: SLOZKA;
begin

for I:=1 to N-1 do
begin K:=I; POM:=POLE[I];
for J:= I+1 to N do
if POLE[J] begin K:=J;
POM:=POLE[J]
end;
POLE[K]:=POLE[I];
POLE[I]:=POM
end
end;


Слайд 4 K seřazení položek použijeme metodu pří-mého vkládání (straight

K seřazení položek použijeme metodu pří-mého vkládání (straight insertion).Princip: V i-tém

insertion).
Princip:
V i-tém kroku se zpracovává i-tá položka.
Buď

se ponechá na svém původním místě (je-li větší jak i-1. položka), nebo se vloží na správné místo.
Tomu předchází uvolnění místa příslušné položky posunutím hodnot, počínaje i-1. položkou a konče příslušnou položkou, vždy o jedno místo vpravo.

Слайд 5 procedure STRINS(var POLE:A; N:INDEX);
var I,J :INDEX;

procedure STRINS(var POLE:A; N:INDEX); var I,J :INDEX;   POM :SLOZKA;


POM :SLOZKA;
begin for

I:=2 to N do
begin POM:=POLE[I];
POLE[0]:=POM;
J:=I-1;
while POM begin
POLE[J+1]:=POLE[J];
J:=J-1
end;
POLE[J+1]:=POM
{též POLE[I]:=POM}
end
end;

Слайд 6 K seřazení položek vektoru použijeme některou z metod

K seřazení položek vektoru použijeme některou z metod přímé výměny. Metody

přímé výměny. Metody jsou založeny na principu srovnávání a

případné výměny sousedních položek vektoru tak dlouho, dokud není vektor seřazený:

a) bublinové třídění - Bubble sort

Princip:
V každém kroku porovnáváme všechny položky vektoru po sousedních dvojicích (J=1..N-1).
Je-li prvý prvek dvojice větší než druhý, provedeme výměnu.
V i-tém kroku nám probublá i-tá nejmenší hodnota na i-té místo od začátku (vrcholu) vektoru.
Po N-1 krocích máme jistotu, že vektor je setříděný.

Слайд 7 procedure BUBBLE(var POLE:A; N:INDEX);
var I,J :INDEX;

procedure BUBBLE(var POLE:A; N:INDEX); var I,J :INDEX;  POM :SLOZKA; begin

POM :SLOZKA;
begin for I:=2 to N

do
for J:=N downto 2 do
{s výhodou downto I}
if POLE[J-1]>POLE[J] then
begin POM:=POLE[J-1];
POLE[J-1]:=POLE[J];
POLE[J]:=POM
end
end
end;

Слайд 8 b) u bublinového řazení s výhodou (tzv. Ripple

b) u bublinového řazení s výhodou (tzv. Ripple sort) je vzata

sort) je vzata v úvahu skutečnost, že vektor může

být setříděný dříve než po N-1 krocích.

Princip:
Postupujeme zkoumáním J-té dvojice, pro J=1..N-I, v rámci I-tého kroku
Testujeme, zda v I-tém kroku došlo k výměně alespoň u jedné dvojice.
Pokud ne, je již vektor setříděn.

Слайд 9 procedure RIPPLE(var POLE:A; N:INDEX);
var J,I :

procedure RIPPLE(var POLE:A; N:INDEX); var J,I : INDEX;  POM :

INDEX;
POM : SLOZKA;

SETRIDENO : Boolean;
begin I:=1;
repeat SETRIDENO := true; {setříděno}
for J:=1 to POC do
if POLE[J+1] begin POM:=POLE[J];
POLE[J]:=POLE[J+1];
POLE[J+1]:=POM;
SETRIDENO:=false
end;
I:=I+1
until (I = N) or SETRIDENO
end;


Слайд 10 c) Další modifikací je Shaker sort.
Princip:
V

c) Další modifikací je Shaker sort. Princip: V určitém kroku prohlížíme

určitém kroku prohlížíme řazený vektor dvakrát.
Nejprve např. od

poslední (dolní) D. dvojice po horní H. dvojici.
Zapamatujeme si číslo J-té poslední dvojice, u které jsme byli nuceni provést výměnu.
Vzápětí prohlížíme vektor podruhé, tentokráte shora (od H = J+1. dvojice) dolů (po poslední dvojici (D)).
Opět si zapamatujeme místo poslední výměny (I=J) a jdeme totéž opakovat do dalšího kroku.
Seřazení vektoru nastává v okamžiku, kdy ani při průchodu zdola nahoru, ani při průchodu shora dolů neprovádíme výměnu.

Слайд 11 procedure SHAKER(var POLE:A; N:INDEX);
var I,J,H,D :

procedure SHAKER(var POLE:A; N:INDEX); var I,J,H,D : INDEX;  POM

INDEX;
POM : SLOZKA;

begin H := 2; D := N; I := N;
repeat for J := D downto H do
if POLE[J-1] > POLE[J] then
begin POM := POLE[J-1];
POLE[J-1] := POLE[J];
POLE[J] := POM;
I := J
end;
H := I + 1;
for J:= H to D do
if POLE[J-1] > POLE[J] then
begin POM := POLE[J-1];
POLE[J-1] := POLE[J];
POLE[J] := POM;
I := J
end;
D := I-1;
until H > D;
end;

Слайд 12 Předchozí 3 metody (Bubble, Ripple a Shaker sort)

Předchozí 3 metody (Bubble, Ripple a Shaker sort) vycházely z principu,

vycházely z principu, že v každém kroku se prohlédly

všechny dvojice sousedních položek vektoru.

Poslední z ukázaných jednoduchých metod řazení, je metoda Shuttle sort.

Princip:
Metoda vychází opět z prohlížení sousedních položek tříděného vektoru, avšak jakmile je zjištěna nutnost provedení výměny, je provedena a vektor je opět prohlížen od prvých dvou položek.

Слайд 13 procedure SHUTT(var POLE:A; N:INDEX);
var I :INDEX;

procedure SHUTT(var POLE:A; N:INDEX); var I :INDEX;  POM :INTEGER; begin I:=2;  while I

POM :INTEGER;
begin I:=2;
while

I<=N do
if POLE[I] then begin POM:=POLE[I];
POLE[I]:=POLE[I-1];
POLE[I-1]:=POM;
I:=2
end
else I :=I+1
end;

Слайд 14 K seřazení většího množství dat se používají duchaplnější

K seřazení většího množství dat se používají duchaplnější metody, z nichž

metody, z nichž jmenujme alespoň Quick sort, Shell sort

a Heap sort.

Metoda Quick sort vychází z následujícího principu:
Z vektoru se vyhledá vhodná hodnota POM1 (např. hodnota umístěná uprostřed).
Pak se prochází vektor řazených hodnot zleva, až se najde číslo větší než POM1, načež se prohlíží vektor zprava, až se najde hodnota menší než POM1. Tato nalezená čísla se vzájemně vymění.
Uvedený postup aplikujeme tak dlouho, dokud se výměna nedá provést a vektor je rozdělen na dvě části (např. poloviny); v levé polovině jsou čísla menší než nějaká hodnota POM1, v pravé polovině pak jsou čísla větší než nějaká hodnota POM1.
Celý proces opakujeme s každou polovinou hodnot samostatně (dále čtvrtinou atd.), až nakonec seřadíme sousední dvojice a tím je úloha vyřešena.

Слайд 15 procedure QUICK(var POLE:A; N: INDEX);
const M

procedure QUICK(var POLE:A; N: INDEX); const M = 12; type STRUKTURA

= 12;
type STRUKTURA = array[1..M] of record

H, D : INDEX
end;
var I, J, H, D : INDEX; S : 0..M;
POM1, POM2 : SLOZKA; Z : STRUKTURA;
begin S := 1; Z[1].H := 1; Z[1].D := N;
repeat H := Z[S].H; D := Z[S].D; S := S-1;
repeat I := H; J := D; POM1:=POLE[(H+D) div 2];
repeat while POLE[I] < POM1 do I := I+1;
while POM1 < POLE[J] do J := J-1;
if I <= J then
begin POM2 := POLE[I];
POLE[I] := POLE[J];
POLE[J] := POM2;
I := I+1; J := J-1
end
until I > J;
if I < D then begin S := S+1;
Z[S].H:=I; Z[S].D:=D;
end;
D := J
until H >= D
until S = 0
end; { konec procedury QUICK }

Слайд 16 Rekurzivní obdoba předchozího algoritmu:
procedure QUICKR(var POLE:A; N: INDEX);

Rekurzivní obdoba předchozího algoritmu:procedure QUICKR(var POLE:A; N: INDEX); procedure SORT(H,D :

procedure SORT(H,D : INDEX);
var

I, J : INDEX; POM1, POM2 : SLOZKA;
begin I := H; J := D;
POM1 := POLE[(H+D) div 2];
repeat while POLE[I] < POM1 do I := I+1;
while POM1 < POLE[J] do J := J-1;
if I <= J then
begin POM2 := POLE[I];
POLE[I] := POLE[J];
POLE[J] := POM2;
I := I+1; J := J-1
end
until I > J;
if H < J then SORT(H,J);
if I < D then SORT(I,D);
end; {konec procedury SORT}
begin SORT(1,N)
end; {konec procedury QUICKR}

Слайд 17 Verzí je možno vytvořit mnoho. Přístup
QUICK1
PRESKUP
QUICK1
QUICK1

.
.
.

Verzí je možno vytvořit mnoho. PřístupQUICK1PRESKUPQUICK1QUICK1…...

Слайд 18 postihuje algoritmus s procedurami PRESKUP a QUICK1
Procedure

postihuje algoritmus s procedurami PRESKUP a QUICK1 Procedure PRESKUP(DM,HM:byte; var J:byte);

PRESKUP(DM,HM:byte; var J:byte);
var D, H :byte;

POM,X : COSI;
begin POM:=A[DM]; J:=DM; H:=HM; D:=DM;
repeat while (H>D) and (A[H]>=POM) do H:=H-1;
J:=H;
if H<>D then begin X:=A[D];
A[D] := A[H];
A[H]:=X;
while (D J:=D;
if H<>D then begin X:=A[H];
A[H]:=A[D];
A[D]:=X
end
end
until D=H;
A[J]:=POM
end;
Procedure QUICK1(DM,HM:byte);
var J:byte;
begin if DM QUICK1(DM,J-1);
QUICK1(J+1,HM)
end;
end;


Слайд 19 Algoritmus založený na metodě QUICKsort přináší také následující

Algoritmus založený na metodě QUICKsort přináší také následující řešení:Program QUICKSORT000; uses

řešení:
Program QUICKSORT000;
uses CRT;
type COSI=integer;
var A

: array[1..20] of COSI;
N,I : byte;
Procedure QUICKRRR(DM,HM:byte);
var D, H :byte;
POM,X : COSI;
Procedure ROZDEL;
begin POM:=A[(DM+HM) div 2]; H:=HM; D:=DM;
repeat while A[H]>POM do H:=H-1;
while A[D] if D<=H then begin X:=A[D];
A[D] := A[H];
A[H]:=X;
D:=D+1;
H:=H-1
end
until D>H;
end;
begin ROZDEL;
if DM if HM>D then QUICKRRR(D,HM);
end;
begin ClrScr;
Write('Zadej pocet vstupnich hodnot: '); Readln(N);
for I:=1 to N do begin Write('Zadej ',I,'. hodnotu: '); Readln(A[I]) end;
QUICKRRR(1,N);
for I:=1 to N do write(A[I]:3)
end.

Слайд 20 Použití každé z výše uvedených řadících procedur vyžaduje

Použití každé z výše uvedených řadících procedur vyžaduje stejné definice a

stejné definice a deklarace. Můžeme tedy vytvořit program např.

ve tvaru:

program SETRIDENI;
{* Definice typů, které byly předpokládány na začátku *}
var POCET, K: INDEX; HODNOTY : A;
{* Na tomto místě zapíšeme kteroukoliv z výše uvedených *}
{* deklarací procedur na řazení (např. proceduru SHUTT) *}
begin write('Zadej pocet nacitanych hodnot k razeni: ');
readln(POCET);
for K:=1 to POCET do begin write('Zadej ',K,'. hodnotu: ');
readln(HODNOTY[K])
end;
{* Na tomto místě zavoláme deklarovanou proceduru, *}
{* např. SHUTT(HODNOTY,POCET); *}
writeln('Tisk serazenych hodnot:');
for K:=1 to POCET do writeln(K,'. hodnota je ',HODNOTY[K]:4);
end.

Слайд 21 Metoda Shell sort, neboli Shellova metoda řazení (řazení

Metoda Shell sort, neboli Shellova metoda řazení (řazení se snižujícím se

se snižujícím se přírůstkem) .

Princip:
Rozdělení řazených hodnot na 4

skupiny tak, že prvky každé skupiny jsou od sebe vzdáleny o 4 složky (1. skupinu tvoří 1., 5., 9. ... složka řazeného vektoru, 2. skupinu 2., 6., 10. ... atd).
Každou skupinu seřadíme zvlášť nějakou známou metodou řazení.
V další etapě rozdělíme pole řazených hodnot na 2 skupiny tak, že prvky každé skupiny jsou od sebe vzdáleny o 2 složky (tj. složky 1., 3., 5. ... resp. 2., 4., 6. ...).
V poslední fázi seřadíme celou posloupnost případnou výměnou sousedních dvojic.

Слайд 22 Následující program má stejnou logiku jako poslední výše

Následující program má stejnou logiku jako poslední výše uvedený program. Za

uvedený program. Za povšimnutí stojí pouze jiná definice typu

A nutná pro použití procedury SHELL:

Program SETRIDENI;
const MAXPOCET= 30;
PS = 4;
type SLOZKA = integer;
INDEX = 0..MAXPOCET;
A = array[-9..MAXPOCET] of SLOZKA;
var POCET, K: INDEX;
HODNOTY : A;

Слайд 23 procedure SHELL(var POLE:A; N: INDEX);

procedure SHELL(var POLE:A; N: INDEX);  type STRUKTURA = array[1..PS]

type STRUKTURA = array[1..PS] of INDEX;

var I, J, R, S : integer;
POM : SLOZKA;
M : 0..PS;
PO : STRUKTURA;
begin PO[1]:=9; PO[2]:=5; PO[3]:=3; PO[4]:=1;
for M:=1 to PS do
begin R:=PO[M]; S:=-R;
for I:=R+1 to N do
begin POM:=POLE[I]; J:=I-R;
if S=0 then S:=-R;
S:=S+1; POLE[S]:=POM;
while POM begin POLE[J+R]:=POLE[J];
J:=J-R
end;
POLE[J+R]:=POM
end
end
end; { konec procedury SHELL }

Слайд 24 begin
write('Zadej pocet nacitanych hodnot

begin  write('Zadej pocet nacitanych hodnot ke trideni: ');  readln(POCET);

ke trideni: ');
readln(POCET);

for K:=1 to POCET do
begin write('Zadej ',K,'. hodnotu: ');
readln(HODNOTY[K])
end;
SHELL(HODNOTY,POCET);
writeln('Tisk setridenych hodnot:');
for K:=1 to POCET do
writeln(K,'. hodnota je ',HODNOTY[K]:4);
end.


Слайд 25 79
K posouzení efektivnosti zmíněných metod poslou-ží následující tab.

79K posouzení efektivnosti zmíněných metod poslou-ží následující tab. časové náročnosti uvedených

časové náročnosti uvedených metod. Z tabulky je patrné, že

na metodě bubli-nového řazení je zajímavý snad její název.

  • Имя файла: vnitřní-řazení-v-poli-in-sito.pptx
  • Количество просмотров: 164
  • Количество скачиваний: 0