Algoritmy usporadúvania

Quick sort

Implementácia

void int_q_sort_vzostup(int *pole, int lavy, int pravy)
{
	int pivot_index, zac_lavy, zac_pravy;	//indexy
	int pivot;				//pivot

	//v zac_lavy, zac_pravy si uchovame pociatocnu hodnotu lavy a pravy
	zac_lavy = lavy;
	zac_pravy = pravy;

	//zvolime si pivot
	//za pivota vyberame prvy prvok v "lavej" casti pola,tj podla "laveho" indexu
	presuny++;
	pivot = pole[lavy];
  
	while (lavy < pravy){
		//testujeme ci je prvok v "pravej" casti pola vacsi ako pivot 
		//pre zostupne usporiadanie bude podmienka: 
		//while( (pole[pravy] <= pivot) && (lavy < pravy) )
		while( (pole[pravy] >= pivot) && (lavy < pravy) ){
			porovnania++;
			pravy--;
		}
		if(lavy < pravy) 
			porovnania++;

		//ak najdeme prvok mensi ako pivot(v pravej casti) a ich indexy sa nezhoduju,
		//tj su to dva rozne prvky, tak na miesto prvku, ktory je na pozicii lavy
		//dame tento mensi prvok z "pravej" casti
		//pricom pivot(hodnota)ostava nezmeneny
		if (lavy != pravy){
			presuny++;
			pole[lavy] = pole[pravy];
			lavy++;		
			//posunieme sa v lavej casti a prave skopirovany prvok z pravej casti sa
			//pri porovnavani lavej casti pola v tomto cykle uz neporovnava
			//pretoze uz vieme ze je mensi nez pivot
		}

		//testujeme, ci su prvky v "lavej" casti pola mensie ako pivot
		//pre zostupne usporiadanie bude podmienka: 
		//while( (pole[lavy] <= pivot) && (lavy < pravy) )
		while( (pole[lavy] <= pivot) && (lavy < pravy) ){
			porovnania++;
			lavy++;
		}
		if(lavy < pravy)
			porovnania++;

		//ak najde prvok vacsi ako pivot a tento sa nachadza v lavej casti
		//skopiruje tento prvok do pravej casti na miesto, z ktoreho bol predtym kopirovany
		//mensi prvok z pravej casti do lavej
		//ak predtym nebol najdeny ziaden prvok v pravej casti mensi ako pivot
		//tak indexy lavy a pravy sa rovnaju, 
		//tj. vstupne podmienky(lavy != pravy, lavy < pravy) su nesplnene
		if (lavy != pravy){
			presuny++;
			pole[pravy] = pole[lavy];
			pravy--;
		}
	}
	
	//nakoniec sa pivot skopiruje na miesto ktore oddeluje pravu a lavu cast pola
	//toto miesto je teraz dane indexom lavy
	presuny++;
	pole[lavy] = pivot;
	pivot_index = lavy;

	//do lavy a pravy dame hodnoty, ktore mali tieto indexy na zaciatku volania funkcie
	lavy = zac_lavy;
	pravy = zac_pravy;
	//volanie funkcie q_sort pre lavu cast prave spracovavaneho pola
	if (lavy < pivot_index){
		rek_volania++;
		int_q_sort_vzostup(pole, lavy, pivot_index-1);
	}
	//volanie funkcie q_sort pre pravu cast prave spracovavaneho pola
	if (pravy > pivot_index){  
		rek_volania++;
		int_q_sort_vzostup(pole, pivot_index+1, pravy);
	}

	return;
}