Uplynul dalÜφ m∞sφc a je tu tedy dalÜφ pokraΦovßnφ kurzu o programovßnφ. Minule jsme proÜli dalÜφ algoritmy urΦenΘ k ut°φd∞nφ prvk∙ pole podle velikosti, dnes si p°idßme n∞kterΘ dalÜφ a pak si povφme n∞co o vlastnostech t°φdicφch algoritm∙. TakΘ sestavφme program, kter²m zm∞°φme rychlost jednotliv²ch t°φdicφch algoritm∙. V p°edminulΘm kurzu se mi do t°φdicφch algoritm∙ vpletly malΘ, ale zßva₧nΘ chybiΦky, za kterΘ se velice omlouvßm a bude jim v∞novßn prvnφ odstavec.
void Bublinka(int *pPole, unsigned int dwVel)
{
int iVymena;
for(unsigned int i = 1; i < dwVel; i++)
{
for(unsigned int j = dwVel - 1; j >= i; j--) // pozor opraveno z minuleho dilu
{
if(pPole[j-1] > pPole[j]) // vetsi pred mensim
{
// prohodime prvky
iVymena = pPole[j-1];
pPole[j-1] = pPole[j];
pPole[j] = iVymena;
}
}
}
}
void Pretres(int *pPole, unsigned int dwVel)
{
unsigned int dwLevy = 1, dwPravy = dwVel - 1,
dwVymena = dwVel - 1;
int iVymena;
do
{
for(unsigned int i = dwPravy; i >= dwLevy; i--)
{
if(pPole[i-1] > pPole[i])
{
iVymena = pPole[i-1];
pPole[i-1] = pPole[i]; // vymena
pPole[i] = iVymena;
dwVymena = i; // posledni vymena
}
}
dwLevy = dwVymena + 1; // priste uz jen od posledniho vymeneneho prvku
for(i = dwLevy; i <= dwPravy; i++)
{
if(pPole[i-1] > pPole[i])
{
iVymena = pPole[i-1];
pPole[i-1] = pPole[i]; // vymena
pPole[i] = iVymena;
dwVymena = i; // posledni vymena
}
}
dwPravy = dwVymena - 1;
} while(dwLevy <= dwPravy);
}
N∞kterΘ algoritmy, se kter²mi jsme se doposud setkali pracovaly tak, ₧e vym∞≥ovaly prvky, kterΘ le₧φ vedle sebe (nap°. bublinkovΘ t°φd∞nφ). To m∞lo za nßsledek, ₧e pokud velk² prvek le₧el na prvnφm mφst∞ v poli, pak mu trvalo velice dlouho, ne₧ se dostal na svou pozici. Musel b²t porovnßn se vÜemi prvky, prob∞hlo tedy tolik v²m∞n, kolik prvk∙ se nachßzelo v poli. Algoritmus Shellova t°φd∞nφ, se kter²m se nynφ seznßmφme, pracuje trochu jinak - porovnßvß toti₧ prvky, kterΘ od sebe le₧φ dßle. Prvky, kterΘ budou vzdßlenΘ o urΦitou konstantu (krok) budeme porovnßvat a uspo°ßdßme je. Uspo°ßdßnφ provedeme nßm ji₧ znßm²m algoritmem p°φmΘho vklßdßnφ (viz. minulß lekce). Dostaneme tak pole, kterΘ je ut°φd∞nΘ s urΦit²m krokem. PotΘ pole set°φdφme znovu, ale s krokem, kter² je menÜφ. Tak pokraΦujeme a₧ se dostaneme na krok o velikosti 1, Φφm₧ vznikne ut°φd∞nΘ pole. V²hodou je, ₧e poka₧dΘ t°φdφme ΦßsteΦn∞ ut°φd∞nΘ pole a tφm se sni₧uje poΦet v²m∞n v ka₧dΘm z krok∙. Implementace:
void ShellSort(int *pPole, unsigned int dwVel)
{
unsigned int i, j, k;
int iPomocna; // vymeny prvku
unsigned int krok[3]; // pole velikosti kroku
// nastaveni velikosti kroku
krok[0] = 4;
krok[1] = 2;
krok[2] = 1;
for(unsigned int m = 0; m < 3; m++)
{
k = krok[m]; // zkopirujeme si velikost kroku se kterym prave pracujeme
// provedeme trideni primym vkladanim
for(i = k; i < dwVel; i++)
{
iPomocna = pPole[i];
j = i;
while((j >= k) && (iPomocna < pPole[j-k]))
{
pPole[j] = pPole[j - k];
j -= k;
}
pPole[j] = iPomocna;
}
}
}
V tomto p°φpad∞ jsme zvolili velikosti krok∙ jako posloupnost 4, 2, 1. Tato posloupnost ale nenφ moc vhodnß - stßle porovnßvßme prvky na sud²ch mφstech a k porovnßnφ s lich²mi p°ijde na °adu a₧ jako poslednφ. LepÜφch v²sledk∙ lze dosßhnout s pou₧itφm nßsledujφcφho vzorce pro v²poΦet posloupnosti krok∙:
h[maxkrok] = 1; h[k-1] = 3 * h[k] + 1
╚φslo maxkrok urΦφme ze vztahu:
maxkrok = [log3dwVel] - 1
HranatΘ zßvorky u logaritmu znamenajφ celou Φßst. dwVel je poΦet prvk∙ pole. Poslednφ Φleny tΘto posloupnosti jsou: 1, 4, 13, 40, 121, 364, ...
Jinou doporuΦovanou posloupnostφ je:
h[maxkrok] = 1; h[k-1] = 2 * h[k] + 1;
maxkrok = [log2dwVel] - 1
Posloupnost mß v tomto p°φpad∞ tvar: 1, 3, 7, 15, 31, 63, ... (pamatujme, ₧e krok 1 pou₧φvßme k t°φd∞nφ a₧ jako poslednφ). Pro napln∞nφ pole posloupnostφ pou₧ijeme cyklus:
unsigned int h[maxkrok];
h[maxkrok - 1] = 1; // posledni krok
for(int i = maxkrok - 2; i >= 0; i--)
{
h[i] = 3*h[i+1] + 1;
}
Identifikßtor maxkrok udßvß, jak dlouhß bude posloupnost a vypoΦteme ji pomocφ v²Üe uvedenΘho vzorce.
K≤d naleznete v sekci Downloads (projekt ShellSort).
Tento algoritmus se dß pou₧φt pouze v p°φpad∞, ₧e dop°edu znßme rozsah t°φd∞n²ch ·daj∙. Pro ka₧d² prvek nejprve spoΦteme, kolik existuje prvk∙ menÜφch. Podle toho pak umφstφme prvek v poli. Proto₧e musφme vytvo°it pole, kterΘ bude mφt hornφ index stejn∞ velk² jako nejv∞tÜφ prvek v t°φd∞nΘm poli, je tento algoritmus nevhodn² pro velmi velkß pole. Narozdφl od p°edchozφch metod musφme zadat navφc jeden parametr, kter²m je prßv∞ velikost nejv∞tÜφho prvku. Implementace:
void CountingSort(int *pPole, unsigned int dwVel, int
iMaxPrvek)
{
int *pC = new int[iMaxPrvek]; // pole pC obsahuje, kolikrat se vyskytuje cislo
v poli
int *pB = new int[dwVel + 1];
// vynulujeme pole cetnosti
for(int i = 0; i < iMaxPrvek; i++)
{
pC[i] = 0;
}
// projdeme postupne pole a spocteme vyskyt jednotlivych cisel
for(unsigned int j = 0; j < dwVel; j++)
{
pC[pPole[j]]++; // indexujeme primo cisly, ktera tridime
}
// provedeme secteni i-teho a predchazejiciho prvku v poli pC - pole pC bude
obsahovat indexy prvku
for(i = 1; i < iMaxPrvek; i++)
{
pC[i] += pC[i-1];
}
// tridene pole projdeme odzadu a budeme radit prvky podle indexu v poli pC
for(i = dwVel-1; i >= 0; i--)
{
pB[pC[pPole[i]]] = pPole[i];
pC[pPole[i]]--;
}
// v poli pB je vysledek, ktery prekopirujeme do puvodniho pole
for(j = 0; j < dwVel; j++)
{
pPole[j] = pB[j + 1];
}
// smazeme pomocna pole
delete [] pC;
delete [] pB;
}
K≤d naleznete v sekci Downloads (projekt CountingSort).
Pro dneÜek poslednφ ·lohou z oblasti t°φd∞nφ pro nßs bude nalΘzt v poli k-t² nejmenÜφ prvek. Prvnφ co nßs m∙₧e napadnout je set°φdit pole jednφm z v²Üe uveden²ch algoritm∙ a pak si v set°φd∞nΘm poli jen indexovat k-t² prvek. To je sice mo₧nΘ, ale existuje i lepÜφ °eÜenφ, kterΘ se naz²vß Hoar∙v algoritmus:
void Hoare(int *pPole,
int dwVel, int dwKty)
{
int i, j, dwLevy, dwPravy;
int iPom1, iPom2;
// pro vymeny prvku
dwLevy = 0;
dwPravy = dwVel - 1;
while(dwLevy < dwPravy)
{
iPom1 = pPole[dwKty];
// prvek vuci kteremu porovnavame
i = dwLevy;
j = dwPravy;
// algoritmus rozdeleni podobne jako u
algoritmu Quicksort
do {
while(pPole[i]
< iPom1) { i++; }
while(pPole[j]
> iPom1) { j--; }
if(i <= j)
{
iPom2 = pPole[i];
pPole[i] = pPole[j];
pPole[j] = iPom2;
// posun na dalsi prvky
i++;
j--;
}
} while (i < j);
// cyklus konci, pokud doslo k prekrizeni
indexu
if(j < dwKty) { dwLevy = i; }
// prvek iPom1 byl prilis maly ->
pokracujeme se spravnym usekem
if(dwKty < i) { dwPravy = j; }
// prvek iPom1 byl prilis velky ->
pokracujeme se spravnym usekem
}
}
Pokud pomocφ tΘto implementace chceme zφskat prvnφ nejmenÜφ prvek, pak zavolßme funkci Hoare(pPole, dwVel, 0). Prvek pak nalezneme na pozici pPole[0]. Chceme-li k-t² prvek, pak zavolßme funkci ve tvaru Hoare(pPole, dwVel, k - 1) a k-t² nejmenÜφ prvek nalezneme na pozici pPole[k - 1]. D∙vodem je, ₧e pole v jazyce C/C++ zaΦφnajφ indexem 0.
Prvek nalezneme rychleji, ale za cenu toho, ₧e pole nebude ·pln∞ ut°φd∞nΘ.
K≤d naleznete v sekci Downloads (projekt Hoare).
Nynφ znßme n∞kolik algoritm∙, pomocφ kter²ch m∙₧eme ut°φdit svoje data. OvÜem stojφme p°ed problΘmem, kter² z algoritm∙ vybrat. NapφÜeme si tedy program, kter²m budeme schopni otestovat t°φdicφ algoritmy na r∙zn∞ rozsßhl²ch polφch. Nßsleduje program:
#include <iostream>
#include <iomanip>
#include <time.h>
#include "Algoritmy.h"
using namespace std;
typedef void (*TRIDICIPROCEDURA)(int *pPole, unsigned int dwVel); // procedura
pro trideni
void TiskPole(int *pPole, unsigned int dwVel)
{
if(pPole)
{
for(unsigned int i = 0; i < dwVel; i++)
{
cout << pPole[i] << " ";
}
cout << endl << endl;
}
}
void NaplnPole(int *pPole, unsigned int dwVel, int iMaxHodnota)
{
if(pPole)
{
for(unsigned int i = 0; i < dwVel; i++)
{
pPole[i] = rand() % iMaxHodnota;
}
}
}
bool OverPole(int *pPole, unsigned int dwVel)
{
bool bRet = true;
for(unsigned int i = 1; i < dwVel; i++)
{
if(pPole[i - 1] > pPole[i]) // predchozi prvek je vetsi nezli prvek
nasledujici -> chyba algoritmu
{
bRet = false;
break;
}
}
return bRet;
}
int main(int argc, char* argv[])
{
srand((unsigned)time(NULL)); // abychom dostali pri kazdem spusteni jina cisla
bool bKonec = false;
unsigned int dwStart, dwStop; // zacatek a konec trideni
unsigned int dwMetoda = 0; // volba
int dwVel; // velikost trideneho pole
cout << "* Rychlostni test tridicich algoritmu *" << endl;
while(dwMetoda != 10)
{
dwVel = 0; // inicializace
cout << "Zadej velikost trideneho pole (0 = konec): ";
cin >> dwVel;
if(dwVel <= 0) { break; } // 0 ukoncime
// vytvorime dve pole - jedno tridene a druhe abychom mohli obnovit tridenou
posloupnost
int *pPole = new int[dwVel]; // pevne pole
int *pPolePrac = new int[dwVel]; // pole ve kterem budeme tridit
if(pPole && pPolePrac)
{
// naplneni pole nahodnymi cisly z rozmezi 0 - (MAXHODNOTA - 1)
NaplnPole(pPole, dwVel, MAXHODNOTA);
dwMetoda = 11; // inicializace
while(dwMetoda > 10)
{
cout << "0) Test vsech" << endl;
cout << "1) Primy vyber (Select Sort)" << endl;
cout << "2) Bublinkove trideni (Bubble Sort)" << endl;
cout << "3) Bublinkove trideni 2 (Bubble Sort) - optimalizace" << endl;
cout << "4) Pretrasani (Shake Sort)" << endl;
cout << "5) Prime vkladani (Insert Sort)" << endl;
cout << "6) Rychle trideni (Quick Sort)" << endl;
cout << "7) Slucovani (Merge Sort)" << endl;
cout << "8) Shellovo trideni (Shell Sort)" << endl;
cout << "9) Vypocet poradi (Counting Sort)" << endl;
cout << "10) Konec" << endl;
cout << "Vyber metodu: ";
cin >> dwMetoda;
}
TRIDICIPROCEDURA tridic;
BOOL bTestVse = false;
if(dwMetoda < 10)
{
while(1) // nekonecny cyklus se obcas hodi :-)
{
if(0 == dwMetoda || bTestVse)
{
bTestVse = true; // budem testovat vsechny
if(dwMetoda < POCETMETOD)
{
dwMetoda++; // posun na prvni metodu
}
else
{
dwMetoda = 11; // nastavime puvodni, jinak bychom byli na 10 a doslo by k
ukonceni programu
break; // jiz jsme prosli posledni metodou
}
}
// obnoveni puvodniho pole
for(int i = 0; i < dwVel; i++)
{
pPolePrac[i] = pPole[i];
}
switch(dwMetoda)
{
case 1: cout << "Primy vyber (Select Sort)" << endl;
tridic = PrimyVyber;
break;
case 2: cout << "Bublinkove trideni (Bubble Sort)" << endl;
tridic = Bublinka;
break;
case 3: cout << "Bublinkove trideni 2 (Bubble Sort) - optimalizace" << endl;
tridic = Bublinka2;
break;
case 4: cout << "Pretrasani (Shake Sort)" << endl;
tridic = Pretres;
break;
case 5: cout << "Prime vkladani (Insert Sort)" << endl;
tridic = PrimeVkladani;
break;
case 6: cout << "Rychle trideni (Quick Sort)" << endl;
tridic = QuickSort;
break;
case 7: cout << "Slucovani (Merge Sort)" << endl;
tridic = MergeSort;
break;
case 8: cout << "Shellovo trideni (Shell Sort)" << endl;
tridic = ShellSort;
break;
case 9: cout << "Vypocet poradi (Counting Sort)" << endl;
tridic = CountingSort;
break;
}
dwStart = GetTickCount();
tridic(pPolePrac, dwVel);
dwStop = GetTickCount();
cout << " Algoritmus setridil " << dwVel << " polozek v case " << dwStop -
dwStart << " milisekund" << endl;
cout << " Kontrola pole probehla s vysledkem: " << (OverPole(pPolePrac, dwVel)
? "OK":"ERROR") << endl;
if(!bTestVse) { break; } // testujeme jen jeden algoritmus
}
delete[] pPole;
delete[] pPolePrac;
}
}
}
return 0;
}
K≤d naleznete v sekci Downloads (projekt RychlTest).
P°idali jsme funkci pro ov∞°enφ sprßvnosti ut°φd∞nφ pole OverPole(). Funkci NaplnPole() nynφ p°edßvßme navφc parametr urΦujφcφ velikost nejv∞tÜφho prvku v poli, kterß je d∙le₧itß pro algoritmus Counting sort. Algoritmus CountingSort() byl takΘ upraven, aby jeho hlaviΦka m∞la stejn² tvar jako ostatnφ t°φdicφ algoritmy. Pak m∙₧eme pou₧φt ukazatele na t°φdicφ funkci pro zjednoduÜenφ t°φd∞nφ, ovÜem musφme brßt ohled na konstantu MAXHODNOTA definovanou v hlaviΦkovΘm souboru Algoritmy.h. Ta musφ v₧dy odpovφdat nejv∞tÜφ hodnot∞, kterß se v poli m∙₧e vyskytnout, jinak algoritmus CountingSort nebude fungovat.
P°i mal²ch polφch nepoznßme mezi t°φdicφmi algoritmy rozdφl, ale u polφ o °ßdov∞ 10000 prvcφch poznßme rozdφly. U algoritm∙ se zavßdφ pojem ΦasovΘ a pam∞¥ovΘ slo₧itosti.
U pam∞¥ovΘ to je jednoduchΘ, staΦφ spoΦφtat, kolik algoritmus pot°ebuje navφc alokovat pam∞ti. Nejvφce algoritm∙ t°φdφ v poli, vyu₧φvajφ navφc jen jednu Φi dv∞ prom∞nnΘ pro prohazovßnφ hodnot v polφch. Setkali jsme se vÜak i s algoritmy, kterΘ pot°ebujφ alokovat velkß pole. Nap°. algoritmus t°φd∞nφ slΘvßnφm pot°ebuje alokovat stejn∞ velkΘ pole, jako je pole p∙vodnφ. U algoritmu CountingSort pot°ebujeme pole dv∞, jedno stejn∞ velkΘ jako p∙vodnφ a druhΘ slou₧φcφ jako poΦφtadlo Φetnosti v²skytu hodnot v poli.
╚asovß slo₧itost vyjad°uje, kolik je nutno provΘst operacφ (zpravidla nejnßroΦn∞jÜφch) pro dan² poΦet prvk∙, vyjad°ujeme ji pomocφ funkce O. Nap°. algoritmus, kter² obsahuje dva vno°enΘ cykly, p°iΦem₧ ka₧d² z nich bude proveden nejv²Üe n-krßt, bude mφt slo₧itost O(n2). ╚asovß slo₧itost se vyjad°uje pro t°i p°φpady - nejhorÜφ, pr∙m∞rn² a nejlepÜφ. My si uvedeme jen v²sledky, proto₧e odvozenφ je v n∞kter²ch p°φpadech celkem slo₧itΘ. P°φmΘ algoritmy (p°φm² v²b∞r, bublinkovΘ t°φd∞nφ (a jeho variace), p°φmΘ vklßdßnφ majφ Φasovou slo₧itost O(n2). Hodφ se tedy na nep°φliÜ rozsßhlß data. Mezi lepÜφ t°φdicφ algoritmy se kter²mi jsme se setkali se °adφ algoritmy Quicksort a t°φd∞nφ slΘvßnφm. Ty majφ Φasovou slo₧itost O(n * log n) v pr∙m∞rnΘm p°φpad∞, ovÜem Quicksort mß v nejhorÜφm p°φpad∞ (poka₧dΘ zvolφme nejmenÜφ prvek) slo₧itost O(n2), kde₧to t°φd∞nφ slΘvßnφm si dr₧φ slo₧itost O(n * log n). Pak jsme se seznßmili se Shellov²m t°φd∞nφm, u n∞ho zßle₧φ na zvolenΘ posloupnosti. Pokud zvolφme posloupnost 1, 4, 13, 40 atd., pak se dß ukßzat, ₧e mß slo₧itost O(n3/2). Pro posloupnost 1, 3, 7, 15, atd. to pak je O(n1,2). Algoritmus CountingSort pak mß slo₧itost O(n), ale to je vykoupeno nutnostφ p°edem znßt rozsah hodnot ulo₧en²ch v poli (a tyto hodnoty musφ navφc b²t celß Φφsla) a takΘ musφme alokovat pomocnΘ pole.
P°φÜt∞ si jeÜt∞ povφme n∞co o stabilit∞ t°φdicφch algoritm∙ a prozatφm skonΦφme Φßst o t°φdicφch algoritmech funkcφ pro vyhledßnφ hodnoty v set°φd∞nΘm poli. PotΘ zaΦneme s datov²mi strukturami zalo₧en²mi na polφch - tj. frontou a zßsobnφkem. A₧ se seznßmφme se slo₧it∞jÜφmi datov²mi strukturami (stromy a halda), tak si jeÜt∞ ukß₧eme, jak se pomocφ nich dß t°φdit.
P°φÜt∞ nashledanou.