Uplynul další měsíc a je tu tedy i pokračování kurzu věnovaného datovým strukturám. V minulém opakovacím dílu jsme si připomenuli datové struktury, se kterými se setkáme ve většině dnešních překladačů. Končili jsme poli a dnes se budeme zabývat jednorozměrnými poli. Ukážeme si, jak v poli hledat hodnotu, pak se budeme věnovat zajímavějšímu - setřídění údajů uložených v poli, přičemž nezůstaneme jen u jednoho způsobu.
Protože doposud jsme neprobrali žádný z algoritmů třídění pole, pak naše pole pro tento odstaveček bude polem nesetříděným podle velikosti prvků. Jediným způsobem, jak v takovémto poli nalézt zadanou hodnotu je prozkoumat prvky pole. V nejhorším případě tedy budeme muset prozkoumat úplně všechny prvky pole. Později si ukážeme, jak lze v setříděném poli nalézt zadanou hodnotu mnohem rychleji.
Předpokládejme, že se v prohledávaném poli hledaná hodnota nachází pouze jednou. Pokud bychom chtěli nalézt až n-tý výskyt, pak stačí přidat parametr a počítadlo výskytů. Ukážeme si tedy první implementaci vyhledání prvku se zadanou hodnotou:
#include <iostream.h>
int Hledani(int *pPole, unsigned int dwVelikost, int iHodnota)
{
int iIndex = -1;
// nastavime priznak, ze jsme nenalezli
for(unsigned int i = 0; i < dwVelikost; i++)
{
if(iHodnota == pPole[i])
// pokud bude hodnota v poli vicekrat,
dostaneme se az na posledni vyskyt hodnoty v poli
{
iIndex = i;
}
// pro vyhledani prvniho vyskytu staci pouzit podminku ve tvaru
// if((Hodnota == pPole[i]) && (-1 == iIndex))
}
return iIndex;
}
int Pole[20];
int *pPole;
int main(int argc, char* argv[])
{
pPole = new int[20];
for(int i = 0; i < 20; i++)
{
Pole[i] = i;
// nastavime nejake hodnoty
pPole[i] = 20-i;
}
int iIndex = Hledani(Pole, 20, 19);
// pro hledani v dynamickem poli staci
zamenit Pole za pPole
if(iIndex != -1)
{
cout << "Hledana hodnota je na pozici : " << iIndex << " a je to cislo " <<
Pole[iIndex] << endl;
}
else
{
cout << "Hledana hodnota se v poli nevyskytuje" << endl;
}
char c;
cin >> c;
delete pPole; //
nezapomeneme smazat dynamicke pole
return 0;
}
Kód naleznete v sekci Downloads (projekt ProhledaniPole).
Algoritmus sice provádí to, co se po něm chce, ale není nejefektivnější. Představte si, že se hledaná hodnota nachází hned v prvním prvku pole. Cyklus se však nezastaví a zbytečně tedy projde všechny prvky pole. Pro vyřešení tohoto problému stačí přidat po nastavení návratové hodnoty buď příkaz pro přerušení cyklu break nebo rovnou vrátit nalezený index pomocí return. Další možností je přepsání funkce s využitím cyklu while. Poslední možností je pak ještě přepsání s pomocnou hodnotou typu boolean, která určuje zda-li se má pokračovat v hledání prvku:
int Hledani(int *pPole,
unsigned int dwVelikost, int
iHodnota)
{
bool bDalsi = true;
// nastavime priznak, ze chceme hledat
int iIndex = -1;
unsigned int i = 0;
while(bDalsi)
{
if(iHodnota == pPole[i])
{
bDalsi = false;
iIndex = i;
// nalezli jsme prvek
}
else if(i == (dwVelikost - 1))
{
bDalsi = false;
// jsme na konci
}
else
{
i++;
// dalsi prvek
}
}
return iIndex;
}
Kód naleznete v sekci Downloads (projekt ProhledaniPole2).
Jako další možnost vyhledávání v nesetříděném poli si ukážeme metodu hledání se zarážkou, která se pak s výhodou využívá u lineárních spojových seznamů. Celá věc spočívá v tom, že jako poslední prvek umístíme do pole námi hledanou hodnotu. Máme tedy jistotu, že tento prvek najdeme vždy a nemusíme tedy testovat překročení indexu pole. Jediným problémem je, že pole musí mít o jeden prvek navíc, abychom měli místo na uložení této zarážky:
int Hledani(int *pPole,
unsigned int dwVelikost, int iHodnota)
{
// predpokladame, ze pole je o 1 vetsi
pPole[dwVelikost] = iHodnota;
// posledni platny prvek je pPole[nVelikost-1]
unsigned int i = 0;
while(iHodnota != pPole[i])
{
i++;
}
if(i < dwVelikost)
{
return i;
}
return -1;
}
Kód naleznete v sekci Downloads (projekt ProhledaniPole3).
Všechny funkce se navenek chovají stejně, vrátí index do pole na kterém se nachází hledaná hodnota. Pokud v poli hodnota není, pak vrací hodnotu -1 a je na volajícím, aby omylem neindexoval pole záporným číslem. Jediným rozdílem je, že pro poslední vyhledávací funkci musí být velikost pole o 1 větší, jinak dojde k chybě přístupu do paměti.
Hledání bylo napsáno pouze pro jednoduché proměnné typu int, ale s využitím objektů a přetěžování operátorů je možno tyto algoritmy upravit na setřídění pole složeného z libovolných datových typů.
Tříděním budeme rozumět uspořádání údajů podle velikosti (vzestupně nebo sestupně) na základě klíče, což může být libovolný údaj spojený s prvkem datové struktury. Jako příklad nám poslouží vzestupné setřídění jednorozměrného pole obsahujícího celočíselné prvky.
K čemu se nám může hodit uspořádání prvků podle velikosti? Jestliže víme, že pole naplníme hodnotami a v průběhu programu v něm budeme vyhledávat hodnoty, pak je vhodné pole setřídit některým z mnoha třídicích algoritmů podle velikosti prvků. Nakonec si totiž ukážeme algoritmus pro vyhledávání v setříděném poli, který je mnohem rychlejší než výše uvedené algoritmy.
Algoritmy pro třídění se dělí např. následovně:
vnitřní třídění - třídění které probíhá přímo v poli uloženém v operační paměti počítače
vnější třídění - třídění velkého množství dat, které není možné najednou uložit do operační paměti počítače. Data se třídí po částech a postupně se z nich tvoří delší úseky. K odkládání dat se používají soubory
V dalším textu se budeme zabývat algoritmy vnitřního třídění. Mimoto dnešní operační systémy pracují s odkládacími soubory, které mohou v případě nedostatku nahradit fyzickou paměť, takže není problém třídit i velká pole.
Nejprve si však pro úplnost vytvoříme proceduru, která vypíše obsah pole předaného parametrem:
void TiskPole(int *pPole, unsigned int dwVel)
{
if(pPole)
{
for(unsigned int i = 0; i < dwVel; i++)
{
cout << pPole[i] << " ";
}
cout << endl;
}
}
Abychom měli nějaká data, která bychom mohli třídit, pak si napíšeme ještě proceduru pro naplnění pole náhodnými čísly:
void NaplnPole(int *pPole, unsigned int
dwVel)
{
if(pPole)
{
for(unsigned int i = 0; i < dwVel; i++)
{
pPole[i] = rand();
// generuje nahodna cisla od 0 do
konstanty RAND_MAX (0x7FFF)
}
}
}
Funkce rand() je definována v hlavičkovém souboru stdlib.h, který tedy musíme vložit. Jestliže chceme čísla pouze do určité hodnoty, pak stačí na funkci rand() použít operátor modulo (%). Chceme-li čísla od 0 do 100 napíšeme:
cislood0do100 = rand() % 100;
Pokud zkusíte vygenerovat náhodná čísla, program vypnete a znovu spustíte, dostanete stejná náhodná čísla. Je to tím, že čísla nejsou úplně náhodná, ale jen pseudonáhodná. Pro vyřešení tohoto problému použijeme funkci srand(int seed), která nastaví počáteční bod pro generování posloupností náhodných čísel. Funkci srand(int seed) se předává parametr typu int, my použijeme hodnotu času, která se stále mění. Budeme tedy navíc potřebovat hlavičkový soubor time.h, který obsahuje funkci time(). Tato funkce vrací počet vteřin, které uběhly od půlnoci 1.1.1970. Mezi prvními příkazy ve funkci main() tedy bude následující řádek:
int main(int argc, char* argv[])
{
srand((unsigned)time(NULL)); // abychom dostali pri kazdem spusteni jina cisla
...
}
Většině funkcí pro třídění předáváme pouze ukazatel na pole a velikost tohoto pole, lze je samozřejmě použít jak na staticky, tak na dynamicky alokovaná pole.
Prvním algoritmem, kterým se budeme zabývat je přímý výběr. Tento algoritmus spočívá ve vybírání nejmenšího čísla z čísel, která jsme ještě nezatřídili. V levé části pole tak postupně vzniká uspořádaná posloupnost čísel a vpravo jsou čísla neuspořádaná. Z pravého úseku v každém průběhu algoritmu vybereme nejmenší číslo, které pak jen připojíme na konec levého úseku (prohodíme nalezený menší prvek a původní prvek):
void PrimyVyber(int *pPole, unsigned int
dwVel)
{
unsigned int dwNejmensi; // index, ne hodnota !!!
int iVymena; // pro vymenu prvku
for(unsigned int i = 0; i < (dwVel - 1); i++)
{
dwNejmensi = i; // index prvku, ke kteremu hledame mensi
for(unsigned int j = i + 1; j < dwVel; j++)
// hledame od dalsiho nesetrideneho
{
// najdeme index nejmensiho prvku, pokud
existuje
if(pPole[j] < pPole[dwNejmensi])
{
dwNejmensi = j;
}
}
if(dwNejmensi > i) // pokud jsme nasli mensi prvek
{
iVymena = pPole[i];
pPole[i] = pPole[dwNejmensi]; // vymenime oba prvky
pPole[dwNejmensi] = iVymena;
}
}
}
Kód naleznete v sekci Downloads (projekt PrimyVyber).
Podmínka (iNejmensi > i) není nutná, ale pokud v nesetříděném úseku nenajdeme menší prvek než poslední v setříděném úseku, ušetříme zbytečné přístupy do paměti pro "prohození" stejných prvků.
Další třídění je založené na porovnávání sousedních prvků. Pokud po větším číslu následuje číslo menší, pak dojde k prohození. Na konci algoritmu jsou seřazeny všechny dvojice a tedy i celé pole. Ukážeme si jednoduchou implementaci:
void Bublinka(int *pPole, unsigned int dwVel)
{
int iVymena;
for(unsigned int i = 1; i < dwVel; i++)
{
for(unsigned int j = dwVel; j >= i; j--)
{
if(pPole[j-1] > pPole[j]) // vetsi pred mensim
{
// prohodime prvky
iVymena = pPole[j-1];
pPole[j-1] = pPole[j];
pPole[j] = iVymena;
}
}
}
}
Kód naleznete v sekci Downloads (projekt Bublinka).
Protože pole procházíme od posledního prvku, pak se při prvním průchodu na první místo dostane nejmenší prvek. Ve druhém průchodu se dostane na druhé místo druhý nejmenší prvek, takže nemusíme již procházet celé pole. Největší prvek klesá pokaždé o jedno místo dolů.
Tato implementace algoritmu má také nevýhodu, že nepozná utříděný úsek pole, dochází tedy ke zbytečným průchodům přes setříděné prvky. Proto ho vylepšíme a budeme sledovat, jestli nastalo prohození pomocí bool hodnoty. Pokud nedojde k prohození, pak je pole již setříděné a můžeme třídění ukončit:
void Bublinka2(int *pPole, unsigned int dwVel)
{
bool bProhoz = true; // musi byt nastaveno,
aby zacal cyklus
int iVymena;
// Budeme prochazet pole, dokud budou nastavat prohozeni
while(bProhoz)
{
// pred pruchodem polem neni zadne prohozeni
bProhoz = 0;
// Zkontroluj vedle sebe lezici prvky
for(unsigned int i = 0; i < (dwVel - 1); i++)
{
if(pPole[i] > pPole[i+1]) // vetsi pred mensim
{
// prohodime prvky
iVymena = pPole[i+1];
pPole[i+1] = pPole[i];
pPole[i] = iVymena;
bProhoz = true; // nastala vymena
}
}
}
}
Kód naleznete v sekci Downloads (projekt Bublinka2).
V jednotlivých průchodech dochází vždy k prohození dvou sousedních prvků, které neleží ve správném pořadí. Nedojde tedy k přesunutí nejmenšího prvku na první místo, jako tomu bylo v předchozí implementaci.
Zajímavou úpravu bublinkového třídění si ukážeme v následujícím odstavečku.
V první implementaci bublinkového třídění se nám postupně dostávaly na správná místa nejrychleji nejmenší prvky pole. Upravíme tedy algoritmus tak, že budeme střídavě procházet pole z obou stran, nejprve se tedy na začátek dostane nejmenší prvek, potom se největší prvek dostane na poslední místo atd. Tak nám na obou okrajích pole budou vznikat uspořádané úseky. Pokud se indexy setříděných úseků překříží, pak je třídění ukončeno:
void Pretres(int *pPole, unsigned int dwVel)
{
unsigned int dwLevy = 1, dwPravy = dwVel - 1, dwVymena = dwVel;
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);
}
Kód naleznete v sekci Downloads (projekt Pretres).
Dnes jsme se seznámili s některými metodami třídění polí, příště si ještě několik metod přidáme a porovnáme algoritmy z hlediska rychlosti, podíváme se tedy na jejich složitost. Také přidáme funkci, která bude v setříděném poli vyhledávat zadanou hodnotu. V příštím dílu také s největší pravděpodobností začneme s odvozenými datovými strukturami.
Příště nashledanou.