Algoritmy pre neusporiadané polia

Vyhľadávanie k-tej hodnoty

Popis
Tak ako sme si v predchádzajúcich algoritmoch ukázali hľadanie prvého najmenšieho a prvého najväčšieho prvku poľa, ukážeme si teraz hľadanie ľubovolného prvku poľa podľa jeho poradia pri zoradení od najmenšieho po najväčší prvok. Ak by sme chceli nájsť napríklad druhý najmenší prvok v poli, mohli by sme to docieliť nájdením minima, vyradením tohto minima z poľa a následným opätovným vyhľadaním minima. Pre 3., 4. a ďalšie najmenšie prvky je však evidentné, že tento spôsob nie je efektívny a je preto treba nájsť spôsob iný. Riešením takéhoto problému je nasledujúci algoritmus.

Vstupy algoritmu
Vstupmi tohto algoritmu sú pole prvkov, ľavý a pravý okraj poľa a poradie hľadaného prvku pri zoradení vzostupne. To znamená, že ak chceme nájsť 2. najmenší prvok, posledným vstupom tohto algoritmu bude práve číslo 2.

Princíp činnosti
Algoritmus najprv vyberie zo stredu poľa (hranicami sú ľavý a pravý okraj poľa) jeden prvok. Tento budeme nazývať ďalej pivot. Algoritmus potom pole čiastočne usporiada tak, aby naľavo od určitej pozície v poli boli iba prvky neväčšie ako pivot a napravo od tejto pozície iba prvky nemenšie. Podľa toho, koľko existuje v poli čísiel menších ako pivot a väčších ako pivot pokračuje ďalej vo vyhľadávaní. Ak hľadá taký prvok, ktorého poradie je menšie alebo rovné ako počet čísiel nie väčších ako pivot, pokračuje vo vyhľadávaní v ľavej časti poľa. Novým pravým okrajom sa stane taká pozícia v poli, od ktorej sú napravo iba čísla rovné alebo väčšie ako pivot. Ak hľadá také číslo, ktorého poradie je väčšie ako počet čísiel menších ako pivot, pokračuje vo vyhľadávaní v pravej časti poľa. Novým ľavým okrajom sa stane pozícia od ktorej sú naľavo iba čísla rovné alebo menšie ako pivot. Takto sa postupne ľavá a pravá hranica k sebe približujú. V momente ako sa po niekoľkých cykloch okraje stotožnia, našiel algoritmus prvok, ktorému by v zoradenom poli patrilo nami zadané poradie.

Výstupy algoritmu
Výstupom algoritmu je hľadaný prvok. Pri hľadaní tohto prvku dochádzalo k čiastočnému zoraďovaniu prvkov v poli. Preto by sme mohli povedať, že výstupom algoritmu je aj čiastočné usporiadanie v niektorých častiach poľa.

Vývojový diagram

Implementácia

 
//najdenie zadanej (k-tej najmensej) hodnoty v poli "pole" 
//so zadanym poctom prvkov "velkost"
//funkcia vracia zadanu hodnotu v poli 
//ak je v poli menej prvkov ako k, funkcia vracia maximum
//ak je k <= 0, funkcia vracia minimum
int najdi_k_tu_hodnotu2(int* pole, int velkost, int k){
	int lavy_o=0;
	int pravy_o=velkost-1;
	int Q;

	while(lavy_o!=pravy_o) {
		triedenie(pole, lavy_o, pravy_o, Q);
		int M=Q-lavy_o+1;
		if (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
void triedenie(int* pole, int lavy_o, int pravy_o, int& Q){
	int i=lavy_o;
	int j=pravy_o;
	int pivot=pole[(lavy_o+pravy_o)/2];

	do {
		while (pole[i] < pivot) i++;
		while (pole[j] > pivot) j--;
		if (i <= j) {
			int pomocna;
			pomocna=pole[i]; pole[i]=pole[j]; pole[j]=pomocna;		
			i++; j--;
		}
	} while (i <= j);
	Q=i-1;
}

Vizualizácie

Časová zložitosť
Časová zložitosť tohto algoritmu nie je taká zreteľná ako časové zložitosti iných algoritmov. V [2] je uvedené, že časová zložitosť bola odvodená pre najhorší prípad rádovo n*n. To je ale pre prípad vyhľadávania minima alebo maxima a na to sú vhodnejšie algoritmy, ktoré sme si už opísali. Pre priemerný prípad je podľa [2] počet porovnaní rádovo n.

Porovnanie s predchádzajúcimi algoritmami
Tento algoritmus je jediný uvedený algoritmus tohto druhu. Preto je ťažké posúdiť ho vzhľadom k ostatným. V každom prípade môžeme vidieť, že svojou časovou zložitosťou zapadá medzi ostatné algoritmy a rieši problém, ktorého riešenie by sme efektívne pomocou predchádzajúcich algoritmov nedosiahli. Riešiť tento problém postupným hľadaním miním alebo maxím by bolo zbytočným mrhaním času.