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.