Bubblesort - optimalizace algoritmu
Obsah lekce:
- Optimalizace algoritmu Bubblesort
Bubblesort - varianta 3
Třetí verze: Třetí verze je ještě optimalizovanější díky absenci všech zmíněných neduh z verzí předchozích.
k:=1;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=1 to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
end;
k:=k+1;
end;
WHILE
První cyklus FOR byl nahrazen cyklem WHILE, který nám umožní měnit čítač a pomocí libovolné podmínky ovlivňovat počet kroku cyklu (cyklus FOR má v některých jazycích tu vlastnost, že v něm nelze měnit čítač cyklu a FOR tedy musí proběhnout nutně zadaný počet kroků – cyklus WHILE je tedy daleko obecnější a ovladatelnější). Dále použijeme proměnou typu boolean (tedy TRUE/FALSE). Před cyklem WHILE tedy nastavíme proměnnou „s“ (seřazeno) na hodnotu FALSE (s:=false;), abychom cyklus vůbec spustili. Hned za BEGIN předpokládáme, že jsou čísla seřazena a nastavíme tedy s:=true; tímto krokem ošetříme případ, kdy už jsou čísla seřazena. Pokud tedy ale nejsou, tak se nám už ve známé podmínce IF p[i]>p[i+1] THEN … změní proměnná „s“ zpět na (s:=false) a v tom případě se cyklus WHILE zopakuje. Pokud by čísla seřazená už byla (nebo se tak stalo např.: po druhém průchodu celým cyklem), cyklus WHILE se už opakovat nebude, neboť podmínka IF už platná není a tudíž zůstane s:=true.
Rozdíl mezi pmax-1 a pmax-k
Princip schodů ošetříme stejně jako ve druhé verzi v cyklu FOR i:=1 to pmax-k. Zde je ale ještě důležité, aby se před samotným cyklem WHILE proměnná „k“ nastavila na hodnotu 1 (tedy k:=1), číslo jedna právě proto, neboť kdyby tam byla nula (k:=0) tak program nebude fungovat vůbec. Také tam nemůže být třeba dvojka, trojka či pětka, neboť bychom se při prvním průchodu cyklem FOR nedostali na konec pole. Dále je nutné, aby se na konci cyklu WHILE (předtím než se cyklus zopakuje) hodnota „k“ zvedla o jedno (k:=k+1), díky tomu bude fungovat „princip schodů“. Optimalizovali jsme některé možnosti, které mohou vzniknout při seřazování a tím zredukovali počet průchodů cyklem, což má za následek rychlejší běh.
Jako ukázku uvedeme následující graf. V něm jsou uvedeny hodnoty pro pmax=10 000, které ukazují množství průchodů cyklem (tedy jakoby počet řádků) a množství porovnávaných čísel.
Bubblesort - varianta 4 - poslední optimalizace
k:=1;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=(0+k) to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
end;
FOR i:=(pmax-k) downto (1+k) DO
begin
IF p[i]
pom:=p[i];
p[i]:=p[i-1];
p[i-1]:=pom;
s:=false;
end;
end;
k:=k+1;
end;
Poslední optimalizace přináší zrychlení řazení. Tato varianta dělá právě to, že při prvním průchodu cyklem WHILE máme největší číslo na konci a nejmenší na začátku. V každém dalším kroku se už porovnávají čísla v rozmezí 1+k až pmax-k, kdy k se při každém průchodu cyklem zvětšuje o jedno. Schéma vypadá jako převrácená pyramida.
Pro srovnání s předešlými verzemi uvádíme další graf:
Zdrojový kód použitý k porovnání rychlosti variant optimalizace
Následující zdrojový kód si můžete stáhnout zde: bubblesortcomparison.pas.
const pmax=1000;
type pole=array[1..pmax] of integer;
var k,i,pom,opakovani:integer;
p,pz:pole;
s:boolean;
pocetk,poceti:longint;
begin
Randomize;
opakovani:=0;
WHILE opakovani<10 DO
begin
FOR i:=1 to pmax DO p[i]:=random(3000);
FOR i:=1 to pmax DO pz[i]:=p[i];
{start neoptimalizovane bez K}
pocetk:=0;
poceti:=0;
FOR k:=1 to (pmax-1) DO
begin
FOR i:=1 to (pmax-1) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
end;
poceti:=poceti+1;
end;
pocetk:=pocetk+1;
end;
writeln('Pocet K neop: ',pocetk);
writeln('Pocet I neop: ',poceti);
{konec neoptimalizovane bez K}
{start neoptimalizovane s K}
FOR i:=1 to pmax DO p[i]:=pz[i];
pocetk:=0;
poceti:=0;
FOR k:=1 to (pmax-1) DO
begin
FOR i:=1 to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
end;
poceti:=poceti+1;
end;
pocetk:=pocetk+1;
end;
writeln('Pocet K neop s k: ',pocetk);
writeln('Pocet I neop s k: ',poceti);
{konec neoptimalizovane s K}
{start optimalizovane}
FOR i:=1 to pmax DO p[i]:=pz[i];
k:=1;
pocetk:=0;
poceti:=0;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=1 to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
poceti:=poceti+1;
end;
k:=k+1;
pocetk:=pocetk+1;
end;
writeln('Pocet K optimal: ',pocetk);
writeln('Pocet I optimal: ',poceti);
{konec optimalizovane}
{start optimalizovane 2}
FOR i:=1 to pmax DO p[i]:=pz[i];
k:=1;
pocetk:=0;
poceti:=0;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=(0+k) to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
poceti:=poceti+1;
end;
FOR i:=(pmax-k) downto (1+k) DO
begin
IF p[i]<p[i-1] THEN
begin
pom:=p[i];
p[i]:=p[i-1];
p[i-1]:=pom;
s:=false;
end;
poceti:=poceti+1;
end;
k:=k+1;
pocetk:=pocetk+2;
end;
writeln('Pocet K optimal2: ',pocetk);
writeln('Pocet I optimal2: ',poceti);
{konec optimalizovane 2}
opakovani:=opakovani+1;
writeln('Pocet kompletniho cyklu ',opakovani);
writeln;
end;
readln;
end.
Domácí úkol
Nalezněte na Internetu alespoň dva další algoritmy na třídění čísel a jeden realizujte v jazyce Pascal.
Otázky
- Popište princip algoritmu Bubblesort.
- Jaké optimalizace lze v algoritmu Bubblesort realizovat?
- Uveďte alespoň dva další příklady třídících algoritmů.