![](../hradTN.gif) |
Algoritmy usporadúvania |
Quick sort |
Implementácia |
Ako bolo spomenuté v popise, pri nerekurzívnej podobe algoritmu je potrebné indexy ľavý a pravý ukladať do zásobníka. Najskôr je teda potrebné implementovať zásobník. Nasleduje štruktúra prvku ukladaného v zásobníku, tj. prvok sa skladá z indexu ľavý a pravý. Samotný zásobník je reprezentovaný ako vektor, čo je vlastne zreťazený zoznam (C++). Pre zásobník stačí zadefinovať tri funkcie, ktorých implementácia a popis je nižšie.
|
typedef struct stack{
int lavy;
int pravy;
}stack;
vector zasobnik;
//******************************************************************
//testuje ci je zasobnik prazdny
bool CStack::S_isempty(void)
{
if(zasobnik.empty())
return true;
else return false;
}
//*********************************************************************
//********************************************************************
//vklada hodnotu do zasobnika
void CStack::S_push(int lavy, int pravy)
{
stack zas;
zas.lavy = lavy;
zas.pravy = pravy;
zasobnik.push_back(zas);
}
//********************************************************************
//*********************************************************************
//vybera hodnotu zo zasobnika, vrchol posuva nizsie
stack* CStack::S_pop()
{
if(S_isempty()) //tzn zas je prazdny
return NULL; //neuspech
//stack zas = zasobnik.RemoveTail();
stack zas;
zas = zasobnik[zasobnik.size()-1];
zasobnik.erase(&zasobnik.back());
return &zas;
}
//********************************************************************
|
|
Nasleduje funkcia v jazyku C, ktorá implementuje algoritmus Quick sort v jeho nerekurzívnej podobe. Uvedená funkcia vstupné pole celých čísel usporiada vzostupne.
Algoritmus pracuje rovnako ako rekurzívna podoba algoritmu, rozdiel je samozrejme v používaní zásobníka. Rekurzívne volanie je nahradené cyklom, ktorý sa vykonáva pokiaľ sú v zásobníku nejaké hodnoty. Nasledujúca funkcia je okomentovaná len na miestach, kde je rozdiel oproti predchádzajúcej implementácii.
//prve volanie funkcie
int_q_sort_vzostup_nerekurziv(pole_int, 0, dlzka-1);
//******QUICK SORT*******
//vstup: pole celych cisel urcene na usporiadanie, lavy a pravy index, medzi ktorymi bude pole usporiadane (pri prvom volani: lavy = 0 a pravy = dlzka-1)
//ucel: vzostupne usporiadanie zadaneho pola
//algoritmus: Quick sort, nerekurzivna podoba algoritmu
//vystup: (void) |
void int_q_sort_vzostup_nerekurziv(int *pole, int lavy, int pravy)
{
int pivot_index, zac_lavy, zac_pravy;
int pivot;
stack *vrchol;
CStack *zas;
//vytvorenie noveho zasobnika
zas = new CStack();
//vlozenie prvych vstupnych hodnot lavy a pravy do zasobnika
zas->S_push(lavy, pravy);
//cyklus bude bezat, pokial v zasobniku nieco bude
while(!(zas->S_isempty())){
//vyberieme hodnoty z vrchu zasobnika
vrchol = zas->S_pop();
//ulozime si ich do premennych lavy a pravy
lavy = vrchol->lavy;
pravy = vrchol->pravy;
zac_lavy = lavy;
zac_pravy = pravy;
presuny++;
pivot = pole[lavy];
while (lavy < pravy){
while( (pole[pravy] >= pivot) && (lavy < pravy) ){
porovnania++;
pravy--;
}
if(lavy < pravy)
porovnania++;
if (lavy != pravy){
presuny++;
pole[lavy] = pole[pravy];
lavy++;
}
while( (pole[lavy] <= pivot) && (lavy < pravy) ){
porovnania++;
lavy++;
}
if(lavy < pravy)
porovnania++;
if (lavy != pravy){
presuny++;
pole[pravy] = pole[lavy];
pravy--;
}
}
presuny++;
pole[lavy] = pivot;
pivot_index = lavy;
lavy = zac_lavy;
pravy = zac_pravy;
//namiesto volania funkcie nasleduje vlozenie hodnot do zasobnika
if (lavy < pivot_index){
zas->S_push(lavy, pivot_index-1);
}
if (pravy > pivot_index){
zas->S_push(pivot_index+1, pravy);
}
}
return;
} |
|
|