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;

}