Grafy a tabuľky

Priemerné počty porovnaní vybraných implementácií

//najdenie zadanej (k-tej najmensej) hodnoty v poli
//funkcia vracia zadanu hodnotu v poli 
//(ak je v poli menej prvkov ako k, funkcia vracia maximum,
//ak je k <= 0, funkcia vracia minimum)
template < class T, int velkost_ > 
T CPole < T, velkost_ > ::najdi_k_tu_hodnotu2(int k){
	int lavy_o=0;
	int pravy_o=velkost_-1;
	int Q;

	while(++p_a_porovnani_ && lavy_o!=pravy_o) {
		++p_a_cyklov_;
		triedenie(lavy_o, pravy_o, Q);
		int M=Q-lavy_o+1;
		if (++ p_a_porovnani_ && k <=M) pravy_o=Q;
		else {
			lavy_o=Q+1;
			k=k-M;
		}
	}
	return pole_[lavy_o];
}

//pomocna funkcia na ciastocne triedenie pola "pole" 
//medzi zadanym lavym "lavy_o" a pravym "pravy_o" okrajom 
//prvky s mensim indexom ako Q su po ukonceni funkcie mensie alebo rovne ako pivot
//prvky s vacsim indexom ako Q su po ukonceni funkcie vacsie alebo rovne ako pivot
//pocet prvkov mensich alebo rovnych ako pivot je ulozeny na adresu &Q
template < class T, int velkost_ > 
void CPole < T, velkost_ > ::triedenie(int lavy_o, int pravy_o, int& Q){
	int i=lavy_o;
	int j=pravy_o;
	T pivot=pole_[(lavy_o+pravy_o)/2];

	do {
		++p_b_cyklov_;
		while (++p_b_porovnani_ && pole_[i] < pivot) i++;
		while (++p_b_porovnani_ && pole_[j] > pivot) j--;
		if (++p_a_porovnani_ && i <= j) {
			T pomocna;
			pomocna=pole_[i]; pole_[i]=pole_[j]; pole_[j]=pomocna;		
			i++; j--;
		}
	} while (++p_c_porovnani_ && i <= j);
	Q=i-1;
}

//najdenie zadanej (k-tej najmensej) hodnoty v poli medzi lavym "lavy_o" a
//pravym "pravy_o" okrajom
//pre vyhladavanie v celom poli treba zadat lavy_o=0 a pravy_o=velkost-1
//funkcia vracia zadanu hodnotu v poli 
//(ak je v poli menej prvkov ako k, funkcia vracia maximum,
//ak je k <= 0, funkcia vracia minimum)
template < class T, int velkost_ > 
T CPole < T, velkost_ > ::najdi_k_tu_hodnotu(int lavy_o, int pravy_o, int k){
	int M, Q;

	if (++p_a_porovnani_ && lavy_o==pravy_o) return pole_[lavy_o];
	else {
		++p_a_cyklov_;
		triedenie(lavy_o, pravy_o, Q);
		M=Q-lavy_o+1;
		if (++ p_a_porovnani_ && k <= M) najdi_k_tu_hodnotu(lavy_o, Q, k);
		else najdi_k_tu_hodnotu(Q+1, pravy_o, k-M);
	}
}

//pomocna funkcia na ciastocne triedenie pola "pole" 
//medzi zadanym lavym "lavy_o" a pravym "pravy_o" okrajom 
//prvky s mensim indexom ako Q su po ukonceni funkcie mensie alebo rovne ako pivot
//prvky s vacsim indexom ako Q su po ukonceni funkcie vacsie alebo rovne ako pivot
//pocet prvkov mensich alebo rovnych ako pivot je ulozeny na adresu &Q
template < class T, int velkost_ > 
void CPole < T, velkost_ > ::triedenie(int lavy_o, int pravy_o, int& Q){
	int i=lavy_o;
	int j=pravy_o;
	T pivot=pole_[(lavy_o+pravy_o)/2];

	do {
		++p_b_cyklov_;
		while (++p_b_porovnani_ && pole_[i] < pivot) i++;
		while (++p_b_porovnani_ && pole_[j] > pivot) j--;
		if (++p_a_porovnani_ && i <= j) {
			T pomocna;
			pomocna=pole_[i]; pole_[i]=pole_[j]; pole_[j]=pomocna;		
			i++; j--;
		}
	} while (++p_c_porovnani_ && i <= j);
	Q=i-1;
}

Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola

Porovnanie algoritmu s predchádzajúcimi algoritmami