Střední škola stavební Jihlava
Sada 1 - Základy programování 17. Řadící algoritmy Digitální učební materiál projektu: SŠS Jihlava – šablony registrační číslo projektu:CZ.1.09/1.5.00/34.0284 Šablona: III/2 - inovace a zkvalitnění výuky prostřednictvím ICT
Jaromír Železný © 2013
Projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky
Řadící algoritmy • slouží k setřídění jednotlivých prvků vstupního souboru (obvykle seznamu, pole) dle jejich velikosti • v každém svém kroku porovnají (a případně „prohodí“) dvě hodnoty ze vstupního seznamu pomocí operace menší nebo rovno, čímž zjistí jejich uspořádání v rámci výsledného seřazeného seznamu
Bubble sort • Bubble sort (bublinkové řazení) je jednoduchý řadící algoritmus • vylepšením bubble sortu je tzv. Shaker sort (oboustranný bubble sort)
Bubble sort - princip • mějme pole o N prvcích • algoritmus se inicializuje (začíná) na indexu I=1 a porovnává se „aktivní“ prvek s prvkem sousedním prvkem • pokud je nižší číslo nalevo od vyššího, tak je prohodí (nižší číslo se posouvá ke konci pole) a se stejnou logikou algoritmus pokračuje na dalším indexu • pokud jsou čísla ve správném pořadí, tak je neprohodí, ale pouze postoupí dále
Bubble sort - princip • na konci každého průchodu posloupností se tímto způsobem na konec vždy dostane nejnižší číslo • při následujícím průchodu algoritmus skončí na pozici N-1 (na poslední pozici pole je již to správné číslo), při každém následujícím opět o jednu pozici méně • po N-1 průchodech (poslední bublinka je seřazena triviálně) je pole seřazeno
Bubble sort – ukázka (1/2) • • • • • • • • • •
(3 (3 (3 (3 (3 (3 (3 (3 (3 (3
2 2 2 2 2 8 8 8 8 8
•
(3 na (3 (8 (8
8 7 6 2) // nový (druhý) průchod polem posledním místě je nejmenší prvek, řazení tedy skončí na pozici N-1 8 7 6 2) // 8 > 3, prohoďme je, posuneme se na další index 3 7 6 2) // 7 > 3, prohoďme je, posuneme se na další index 7 3 6 2) // 6 > 3, prohoďme je, na pozici N a N-1 máme 2 nejmenší
• • •
8 8 8 8 8 2 2 7 7 7
7 7 7 7 7 7 7 2 2 6
6) 6) 6) 6) 6) 6) 6) 6) 6) 2)
// // // // // // // // // //
zadání pole, budeme řadit mě od největšího k nejmenšímu začneme na pozici i=1 3 a 2 jsou ve správném pořadí pořadí posuneme se na další index (i=2) 2 < 8, prohodíme je posuneme se na další index (i=3) 2 < 7, prohodíme je posuneme se na další index (i=4) 6 > 2, prohodíme je na pozici N je nejmenší prvek
Bubble sort – ukázka (2/2) •
• •
• • •
(8 7 6 3 2) // nový (třetí) průchod polem, na posledním místě je nejmenší prvek, na předposledním je druhý nejmenší prvek, řazení tedy skončí na pozici N-2 (8 7 6 3 2) // 8 a 7 jsou ve správném pořadí, postoupíme na další index (8 7 6 3 2) // 7 a 6 jsou ve správném pořadí, na pozici N a N-1 a N-2 máme 3 nejmenší (8 7 6 3 2) // nový (třetí) průchod polem (8 7 6 3 2) // 8 a 7 jsou ve správném pořadí (8 7 6 3 2) // SEŘAZENO
Bubble sort program BubbleSort; var x : array [1..5] of integer; pomoc, I, J, N : integer; Begin N:=5; {nase pole ma 5 prvku} Writeln ('Zadej jednotlive prvky pole'); For I:=1 to N do Read (X[I]); writeln; For I := 1 to N-1 do begin for J := 1 to N-I do if (X[J+1] > X[J]) then begin pomoc := X[J+1]; X[J+1] := X[J]; X[J] := pomoc; End; End; For i:=1 to N do writeln (x[i]); readln; End.
Insertion sort • insertion sort (řazení vkládáním) je algoritmus založený na principu porovnávání řazených hodnot a vkládání na správné místo
Insertion sort - princip • mějme pole o N prvcích • první prvek je triviálně („správně“) zařazen • vezmeme druhý prvek a zařadíme jej na správné místo podle velikosti • vezmeme následující prvek a zařadíme jej na správné místo v již seřazených prvcích • dokud pole obsahuje nezařazené prvky (dokud se neposuneme na poslední prvek), provádíme předchozí krok
Insertion sort - ukázka • • • • • •
(3 (3 (3 (8 (8 (8
2 2 2 3 7 7
8 8 8 2 3 6
7 7 7 7 2 3
6) 6) 6) 6) 6) 2)
// // // // // //
Zadání, prvek 3 je triviálně seřazen Vezmeme dvojku a vložíme jí na správné místo (tam už je) 8 vložíme na první místo, zbytek čísel posuneme 7 vložíme mezi 8 a 3, 3 a 2 posuneme 6 vložíme mezi 7 a 3, čísla 3 a 2 posuneme seřazeno
Insertion sort (1/3) program insertsort; var X : array[1..5] of integer; i, j, n, pozice, hodnota : integer; hotovo : boolean; begin N:= 5; {nase pole ma 5 prvku} Writeln ('Zadej jednotlive prvky pole'); For I:=1 to N do Read (X[I]); writeln;
Insertion sort (2/3) for j :=1 to N do begin hodnota := X[i]; pozice := i; hotovo := false; while not hotovo do begin if pozice <= 1 then hotovo := true else if hodnota >= X[pozice-1] then hotovo := true else begin X[pozice] := X[pozice-1]; pozice := pozice-1 ; end; end; X[pozice] := hodnota; end;
Insertion sort (3/3) {na zaver program vypise serazene pole} for i := 1 to n do write(X[i],' '); readln; readln; end.
Selection sort • Selection sort (řazení výběrem) je jednoduchý řadící algoritmus • v porovnání s dalšími kvadratickými algoritmy je selection sort v obecném případě rychlejší než bubble sort, avšak pomalejší než insertion sort
Selection sort • Selection sort vychází z myšlenky, že pokud řadíme pole od největšího prvku k nejmenšímu, tak první bude nejvyšší prvek, za ním nejvyšší prvek ze zbytku pole atd. • potom pouze postupně vybíráme nejvyšší prvky z neseřazené části pole a umísťujeme je na konec již seřazené části pole
Selection sort - ukázka • • • • • •
(3 (3 (8 (8 (8 (8
2 2 2 7 7 7
8 8 3 3 6 6
7 7 7 2 2 3
6) 6) 6) 6) 3) 2)
// // // // // //
zadání pole, řadíme od největšího k nejmenšímu nejvyšší je 8, prohodíme ho tedy s 3 na pozici nejvyšší je 7, prohodíme ho tedy s 2 na pozici nejvyšší je 6, prohodíme ho tedy s 3 na pozici nejvyšší je 3, prohodíme ho tedy s 2 na pozici seřazeno
1 2 3 4
Selection sort (1/3) program SelectSort; var X : array [1..5] of integer; I, J, PomocX, PomocI, N : integer; begin N:= 5; {nase pole ma 5 prvku} Writeln ('Zadej jednotlive prvky pole'); For I:=1 to N do Read (X[I]); writeln;
Selection sort (2/3) for I := 1 to N - 1 do begin pomocI:=i; pomocX:=X[I]; for J := (I + 1) to N do begin if (X[J] > PomocX) then begin PomocX := X[j]; PomocI := j; end; end; PomocX := X[i]; X[i] := X[PomocI]; X[PomocI] := PomocX; end;
Selection sort (3/3) {na zaver program vypise serazene pole} for i := 1 to n do write(X[i],' '); readln; end.
Řadící algoritmy - závěr • největší část algoritmů řazení je založena na porovnávání dvojic prvků • jedná se o univerzální metodu, kterou lze seřadit libovolná data v libovolné reprezentaci (stačí příslušná relace uspořádání) • pro některé konkrétní reprezentace nějak vymezené množiny dat lze sestrojit algoritmy, které fungují na jiném principu, např. na základě reprezentace řazených čísel v poziční číselné soustavě
Zdroje: TurboPascal 6.0 - příručka uživatele (help) http://www.algoritmy.net/article/3/Bubble-sort http://www.algoritmy.net/article/8/Insertion-sort http://www.algoritmy.net/article/4/Selection-sort Literatura: Radek HYLMAR: Programování pro úplné začátečníky, Computer Press, Brno, 2009, ISBN 978-80-251-2129-0 Januš DRÓZD, Rudolf KRYL: Začínáme s programováním, GRADA a.s., Praha, 1992, ISBN 80-85424-41-X Tomáš HRUŠKA: Pascal pro začátečníky, SNTL, Praha 1989, ISBN 80-0300345-8 Materiál je určen k bezplatnému používání pro potřeby výuky a vzdělávání na všech typech škol a školských zařízení. Autorem materiálu a všech jeho částí, není-li uvedeno jinak, je : Jaromír Železný Pokud není uvedeno jinak, byly při tvorbě použity volně přístupné internetové zdroje. Autor souhlasí se sdílením vytvořených materiálů a jejich umístěním na www.ssstavji.cz.
