Algoritmy pre neusporiadané polia

Vyhľadávanie extrému (maxima)

Popis
Doteraz sme sa zaoberali prípadmi, kedy sme hľadali v poli nami zadaný prvok. Tento algoritmus je určený na nájdenie prvku, ktorý má v celom poli najmenšiu (resp. najvyššiu hodnotu). Pred spustením algoritmu túto hodnotu nepoznáme, ale algoritmus nám po prehľadaní poľa túto hodnotu oznámi.

Vstupy algoritmu
Vstupom tohto algoritmu je iba pole prvkov, v ktorom chceme vyhľadávať. Ďalším vstupom môže byť počet prvkov v poli. Ak je pole ukončené ukončovacím znakom, nie je tento ďalší vstup potrebný a algoritmus po nájdení ukončovacieho znaku hľadanie minima (resp. maxima) ukončí.

Princíp činnosti
Algoritmus na začiatku označí prvý prvok poľa za minimum (resp. maximum). Postupne prechádza ďalšie prvky poľa a ak nájde prvok menší ako minimum (resp. väčší ako maximum), označí tento prvok za nové minimum (resp. maximum) poľa. Algoritmus sa zastaví po prehľadaní všetkých prvkov poľa.

Výstupy algoritmu
Keďže v každom prípade v poli nejaký extrém nájdeme, výstupom algoritmu je práve tento hľadaný prvok. Väčšinou nás zaujíma práve jeho hodnota, ktorá môže byť výstupom algoritmu, ale niekedy môžeme potrebovať nájsť miesto, kde sa táto hodnota nachádza. Vtedy býva výstupom algoritmu index tohto prvku v poli.

Vývojový diagram

Implementácia

 
//najdenie maximalneho prvku (s najvacsou hodnotou) v poli "pole" s poctom prvkov "velkost"
//funkcia vracia hodnotu maxima
int najdi_sekv_hodnotu_max(int* pole, int velkost){
	int hodn_max=pole[0];
	int index=1;
	while (index < velkost) { 
		if (pole[index] > hodn_max) hodn_max=pole[index];
		index++;
	}
	return hodn_max;
}

Vizualizácie

Časová zložitosť
Pri spustení označí algoritmus prvý prvok poľa za extrém. Ďalej potom porovnáva vždy extrém s aktuálnym prvkom poľa. Preto počet porovnaní bude n-1. Keďže budeme zároveň kontrolovať, či aktuálny prvok nie je ukončovacím prvkom poľa alebo či sme už nevykonali požadovaný počet porovnaní (podľa počtu prvkov v poli), algoritmus vykoná ďalších n porovnaní. Celkový počet porovnaní bude teda vždy 2*n-1, teda približne 2*n.

Porovnanie s predchádzajúcimi algoritmami
Keďže algoritmus hľadá nejakú vlastnosť poľa a nie priamo hľadaný prvok, musí vždy prehľadať celé pole. Počet porovnaní sa nedá pre hľadanie jedného extrému nijako zmenšiť. Keďže je tento typ úlohy iný ako predchádzajúce, nebudeme sa zaoberať ani ich porovnaním. Časová zložitosť je však s predchádzajúcimi algoritmami približne rovnaká.