Snímek 1 - MENDELU

Snímek 1 - MENDELU

Vnitn azen v poli (in sito) Je dn vektor N sel (celch, desetinnch, znak, etzc znak). Vytvote proceduru pro jejich vzestupn seazen. een: Za pedpokladu, e jsou definovny typy type INDEX = 0..MAXPOCET; SLOZKA = integer; {me bt real, string[20] atp.} A = array[INDEX] of SLOZKA; kde MAXPOCET je definovan konstanta nap. const MAXPOCET=20; omezujc pouitelnost dle uvedench procedur na zpracovn N-lennch vektor (N je maximln MAXPOCET). 1 K seazen poloek pouijeme metodu pmho vbru (straight selection). Princip: Ze vech poloek vektoru vyber nejmen hodnotu. Vym vzjemn nalezenou hodnotu s hodnotou v prv poloce vektoru. Pot vyber nejmen prvek ze zbylch N-1 prvk (z 2. a N-t poloky) a vym ho s druhou polokou atd. a zstane posledn Nt (maximln) prvek. 2 procedure STRSEL(var POLE:A; N:INDEX);

var I,J,K: INDEX; 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]

POM :SLOZKA; begin for I:=2 to N do begin POM:=POLE[I]; POLE[0]:=POM; J:=I-1; while POM

6 procedure BUBBLE(var POLE:A; N:INDEX); var I,J :INDEX; POM :SLOZKA; begin for I:=2 to N do for J:=N downto 2 do {s vhodou 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; 7 b) u bublinovho azen s vhodou (tzv. Ripple sort) je vzata v vahu skutenost, e vektor me bt setdn dve ne po N-1 krocch. Princip: Postupujeme zkoumnm J-t dvojice, pro J=1..N-I, v rmci I-tho kroku Testujeme, zda v I-tm kroku dolo k vmn alespo u jedn dvojice. Pokud ne, je ji vektor setdn. 8

procedure RIPPLE(var POLE:A; N:INDEX); var J,I : INDEX; POM : SLOZKA; SETRIDENO : Boolean; begin I:=1; repeat SETRIDENO := true; {setdno} for J:=1 to POC do if POLE[J+1]

jdeme tot opakovat do dalho kroku. Seazen vektoru nastv v okamiku, kdy ani pi prchodu zdola nahoru, ani pi prchodu shora dol neprovdme vmnu. 10 procedure SHAKER(var POLE:A; N:INDEX); var I,J,H,D : 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; 11 Pedchoz 3 metody (Bubble, Ripple a Shaker sort) vychzely z principu, e v kadm kroku se prohldly vechny dvojice sousednch poloek vektoru. Posledn z ukzanch jednoduchch metod azen, je metoda Shuttle sort. Princip: Metoda vychz opt z prohlen sousednch poloek tdnho vektoru, avak jakmile je zjitna nutnost proveden vmny, je provedena a vektor je opt prohlen od prvch dvou poloek. 12 procedure SHUTT(var POLE:A; N:INDEX); var I :INDEX; POM :INTEGER; begin I:=2; while I<=N do if POLE[I]

else I :=I+1 end; 13 K seazen vtho mnostv dat se pouvaj duchaplnj metody, z nich jmenujme alespo Quick sort, Shell sort a Heap sort. Metoda Quick sort vychz z nsledujcho principu: Z vektoru se vyhled vhodn hodnota POM1 (nap. hodnota umstn uprosted). Pak se prochz vektor azench hodnot zleva, a se najde slo vt ne POM1, nae se prohl vektor zprava, a se najde hodnota men ne POM1. Tato nalezen sla se vzjemn vymn. Uveden postup aplikujeme tak dlouho, dokud se vmna ned provst a vektor je rozdlen na dv sti (nap. poloviny); v lev polovin jsou sla men ne njak hodnota POM1, v prav polovin pak jsou sla vt ne njak hodnota POM1. Cel proces opakujeme s kadou polovinou hodnot samostatn (dle tvrtinou atd.), a nakonec seadme sousedn dvojice a tm je loha vyeena. 14 procedure QUICK(var POLE:A; N: INDEX); const M = 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 } 15 Rekurzivn obdoba pedchozho algoritmu: procedure QUICKR(var POLE:A; N: INDEX); 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} 16 Verz je mono vytvoit mnoho. Pstup 5 11 3

4 9 7 QUICK1 PRESKUP J 1 DM 1 DM 1 D 1 HM 8

HM 8 H 8 3 3 . . . QUICK1 3 11 5 4 3 3

3 4 2 J 2 9 H 7 J 4 5 9 POM 5 7

6 5 7 6 11 6 5 7 3 3 X D D 8

9 4 6 4 6 11 4 QUICK1 DM 1 DM 5 HM 3

HM 8 17 postihuje algoritmus s procedurami PRESKUP a QUICK1 Procedure 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 (DD 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; 18 Algoritmus zaloen na metod QUICKsort pin tak nsledujc een: 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]H; end;

begin ROZDEL; if DMD 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. 19 Pouit kad z ve uvedench adcch procedur vyaduje stejn definice a deklarace. Meme tedy vytvoit program nap. ve tvaru: program SETRIDENI; {* Definice typ, kter byly pedpokldny na zatku *} var POCET, K: INDEX; HODNOTY : A; {* Na tomto mst zapeme kteroukoliv z ve uvedench *} {* 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 mst zavolme deklarovanou proceduru, *} {* nap. SHUTT(HODNOTY,POCET); *}

writeln('Tisk serazenych hodnot:'); for K:=1 to POCET do writeln(K,'. hodnota je ',HODNOTY[K]:4); end. 20 Metoda Shell sort, neboli Shellova metoda azen (azen se sniujcm se prstkem) . Princip: Rozdlen azench hodnot na 4 skupiny tak, e prvky kad skupiny jsou od sebe vzdleny o 4 sloky (1. skupinu tvo 1., 5., 9. ... sloka azenho vektoru, 2. skupinu 2., 6., 10. ... atd). Kadou skupinu seadme zvl njakou znmou metodou azen. V dal etap rozdlme pole azench hodnot na 2 skupiny tak, e prvky kad skupiny jsou od sebe vzdleny o 2 sloky (tj. sloky 1., 3., 5. ... resp. 2., 4., 6. ...). V posledn fzi seadme celou posloupnost ppadnou vmnou sousednch dvojic. 21 Nsledujc program m stejnou logiku jako posledn ve uveden program. Za povimnut stoj pouze jin definice typu A nutn pro pouit 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; 22 procedure SHELL(var POLE:A; N: INDEX); 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

setdn nhodn poet prvk 256 512 Pm vbr 489 1907 509 1956 695 2675 12 23

366 1444 704 2836 Bubble sort 540 2165 1026 4054 1442 5931 Ripple sort 5 8 1104

4270 1645 6542 Shaker sort 5 9 961 3642 1619 6520 Shell sort 58 116 127

349 157 492 Quick sort 31 69 60 146 37 79 Pm vkldn 256 opan set. 512 256

512 25 Zvrem tohoto pkladu jet jednou poznamenejme, e tvar vech ve uvedench algoritm zstv zcela zachovn i pro azen selnch relnch hodnot, ppadn etzc znak, i jen znak. V sti definic programu je teba pouze zmnit definici typu SLOZKA na nap. SLOZKA = real nebo SLOZKA = string[20] nebo SLOZKA = char atp. 26

Recently Viewed Presentations

  • Gwen&#x27;s Canyon - &quot;સુરતી ઉંધીયુ&quot;

    Gwen's Canyon - "સુરતી ઉંધીયુ"

    Gwen agreed the canyon flowers are the best, and asked the Sky Pilot to tell her what it meant. For a long time Gwen lay quite still, and then said wistfully, while her lips trembled: "There are no flowers in...
  • LED ZEPPELIN - University of Minnesota

    LED ZEPPELIN - University of Minnesota

    The Band called themselves Led Zeppelin and would have a lasting impact and influence on the future of rock music. ... It has four symbols, which many claimed to be runes and believe to be the title of the album....
  • Records Management Network Legal & Risk Records Services

    Records Management Network Legal & Risk Records Services

    Imposes an obligation on Cwth entities to notify the Australian Information Commissioner (OAIC) and affected individuals of . eligible. data breaches within 30 days. UoM is not an 'entity' under the Cwth legislation
  • Lecture 1 - University of Pittsburgh

    Lecture 1 - University of Pittsburgh

    Invisible watermarks Useful as for identifying the source, author, owner, distributor or authorized consumer Permanently, unalterably mark the image Also used for tracing images in the event of their illicit distribution Unique watermark for each buyer Visible vs Invisible Watermarks...
  • Name of presentation - Helena High School

    Name of presentation - Helena High School

    Early forms of proto-capitalism and free markets were present in the early form. Merchant capitalism was developed between the 8th-12th centuries, which some refer to as ... Islamic luster-painted ceramics were imitated by Italian potters during the Renaissance. Calligraphy, an...
  • Smart Home - UCF Department of EECS

    Smart Home - UCF Department of EECS

    In 2012, these households are projected to spend 21% of their average after-tax income on energy. (DOE/EIA Short-Term Energy Outlook released in January 2012) The categories of home energy usage that this project aims to decrease are: Home Electronics 7.2%...
  • Section 3.8 Solving Trigonometric Equations with Horizontal ...

    Section 3.8 Solving Trigonometric Equations with Horizontal ...

    Use inverse trig. functions to find the solution(s) There are usually two solutions within one cycle (CAST) Use the reference angles to find the solution in standard position. Graphically: Make Y 1. equal to one side of the functionMake Y...
  • Characters in Lord of the Flies

    Characters in Lord of the Flies

    It also represents the island, on which the boys are stuck. Piggy's Glasses . ... the darkness of man's hear, and the fall through the air of true, wise friend called Piggy"( Golding 202). ... What is a literary analysis...