Jeden z algoritmů je tzv. Probublávání (boublesort).
princip boublesortu
Program prohledá všechna zadaná čísla, najde největší z nich a v každé fázi největší číslo (ze zbyvajicich) probublá až na konec (doprava). To dělá pořád dokola, až není co probublávat:)
Novou věcí zde je pojem POLE (v pascalštině array). Zde je použito jednorozměrné pole. Chápejme ho jako řadu čísel. Dvourozměrné pole si představme jako tabulku, kdy každé číslo je určeno souřadnicí X a souřadnicí Y. Třírozměrné pole si představme jako kvádr (souřadnice X, Y, Z). Čtyřrozměrné pole si raději nepředstavujme vůbec.
Program BubbleSort;
const
MAX = 100;
debug = false; { Pro testovaci ucely }
var
pole : array [1..MAX] of Integer;
pole_max : Word;
{ zde zacina definice jednotlivych procedur }
{ Vypsani cisel z pole. }
procedure vypis;
var i : Word;
begin
for i := 1 to pole_max do begin
if i > 1 then Write(', ');
Write(pole[i]);
end;
WriteLn;
end;
{ Vymeni cisla na indexech i a j. }
procedure vymen(i, j: Word);
var swap : Integer;
begin
swap := pole[i];
pole[i] := pole[j];
pole[j] := swap;
end;
{ BubbleSort
==========
Porovnavame dve cisla a kdyz jsou ve spatnem poradi, tak je prehodime. }
procedure bubble_sort;
var i, j : Word;
begin
for i := 1 to pole_max-1 do { Faze. V kazde fazi nejvetsi cislo (ze zbyvajicich) probubla az na konec (doprava). }
for j := i+1 to pole_max do { Plati: i < j }
if pole[i] > pole[j] then vymen(i,j);
end;
{ InsertSort
==========
Pracujeme ve fazich. V i-te fazi najdeme i-te nejmensi cislo a to umistime. }
procedure insert_sort;
var i, j, k : Word;
begin
for i := 1 to pole_max-1 do { Pocet fazi }
begin
k := pole[i]; { Tady je chyba, ale objevte ji sami }
for j := i+1 to pole_max do
if pole[k] > pole[j] then k := j;
if debug then WriteLn('Vymenuji ', i, ' <-> ', k);
if debug then vypis;
vymen(i, k);
if debug then vypis;
end;
end;
{ QuickSort
=========
}
function partition(start, finish, level : Word) : Word;
const randomized = false; { Randomizovany QuickSort : pivota vyberu nahodne. }
var i, j, q, pivot : Word;
begin
if randomized then begin
{ Nahodne vybereme pivota a umistime ho na konec. }
i := start + random(finish - start + 1);
if debug then begin for q := 0 to level do Write(' '); WriteLn('Randomizuji [', i, '] = ', pole[i]); end;
vymen(i, finish);
end;
pivot := pole[finish];
i := start;
j := finish;
if debug then begin for q := 0 to level do Write(' '); WriteLn('Pivot = ', pivot); end;
while i < j do begin
while (pole[i] <= pivot) and (i < j) do i := i + 1;
if pivot < pole[i] then begin
vymen(i, j);
if debug then begin for q := 0 to level do
Write(' '); WriteLn('Vymenuji [', i, '] = ', pole[i], ' <=> [', j, '] = ', pole[j]); end;
end;
while (pivot < pole[j]) and (i < j) do j := j - 1;
if pole[j] < pivot then begin
vymen(i, j);
if debug then begin for q := 0 to level do
Write(' '); WriteLn('Vymenuji [', i, '] = ', pole[i], ' <=> [', j, '] = ', pole[j]); end;
end;
end;
pole[j] := pivot;
partition := j;
end;
procedure quick_sort_special(start, finish, level : Word);
var split, q : Word;
begin
if finish <= start then exit;
if debug then begin for q := 0 to level do
Write(' '); Write('Tridim ');
for q := start to finish do Write(pole[q], ' '); WriteLn(' start = ', start, ', finish = ', finish); end;
split := partition(start, finish, level);
if debug then begin
for q := 0 to level do Write(' ');
Write('Po rozdeleni ');
for q := start to split-1 do Write(pole[q], ' ');
Write('|', pole[split], '| ');
for q := split+1 to finish do Write(pole[q], ' ');
WriteLn;
end;
quick_sort_special(start, split-1, level+1);
quick_sort_special(split+1, finish, level+1);
if debug then begin for q := 0 to level do
Write(' '); Write('Setrideno '); for q := start to finish do Write(pole[q], ' '); WriteLn; end;
end;
procedure quick_sort;
begin
quick_sort_special(1, pole_max, 0);
end;
{ zde konci definice jednotlivych procedur }
{vlastni program}
var i : Word;
begin
{ Inicializace }
if debug then randomize;
{ to je tu jen kvuli ladeni programu, neres to, nepremyslej o tom }
{ Nacteni cisel }
repeat
Write('Zadej pocet cisel: ');
ReadLn(pole_max);
until (1 <= pole_max) and (pole_max <= MAX);
for i := 1 to pole_max do
if not debug then begin
Write('Zadej ', i, '. cislo: ');
ReadLn(pole[i]);
end else pole[i] := random(100);
WriteLn('Zadana cisla:');
vypis;
{ Trideni }
bubble_sort;
{ insert_sort; }
{ quick_sort; }
WriteLn('Setridena cisla:');
vypis;
{ to, co nasleduje je fakt produkt lammerstvi nejvyssiho kalibru -> vylepsit!!! }
readln (i);
{ to, tu je jenom proto, aby se dala precist obrazovka s vysledky -> vylepsit!!! }
end.
zdroj: http://www.ms.mff.cuni.cz/~malej9am/vyuka/pascal/?lang=cs
-------------------------------------------------------------------------------------------------------
úkoly:
- upravte tento program dle naučeného standardu (= motání programu dokola s koncovým dotazem "Znovu? A/N")
- vytvořte simulační tabulku pro jednotlivé proměnné tohoto programu
- vstupem jsou jednotlivé číslice po sobě jdoucí v Ludolfově čísle
- vytvořte vývojový diagram popisující tento program
- pro ty, co by snad chtěli jedničku:
- upravte tento program tak, aby byl výsledek seřazen opačně (nyní je od nejmenšího po největší, opačně znamená, aby výpis byl od největšího po nejmenší)
Žádné komentáře:
Okomentovat