Hľadanie extrému (minima a maxima) v poli

Algoritmus pre nájdenie najväčšieho alebo najmenšieho prvku v poli je síce zrejmý, ale pre istotu aj úplnosť som sa ho rozhodol uviesť.

Budem tu popisovať vyhľadanie maxima, vyhľadanie minima bude potom analogické. Algoritmus bude mať spočiatku v premennej uloženej východiskovej maximum. Potom prejde pole prvok po prvku a ak je nejaký prvok väčší, ako toto maximum, bude novým maximom tento prvok. Po prejdení pole bude v premennej určite maximum z daných hodnôt v poli.

Teraz ako je to s tým východiskovým maximom. Niektoré z vás iste napadlo dať mu hodnotu 0. Čo keď ale budeme mať pole plné záporných čísel? Naša maximum bude maximom aj po priechode poľom (pretože nič nebude väčšia ako 0) a jeho hodnota je úplne chybná, pretože sa v poli ani nevyskytuje. Dáme mu teda nejakú hodnotu z poľa, vôbec nezáleží akú. Ponúka sa napr. Prvý prvok, pretože k nemu máme najľahšie prístup.

V praxi sa tiež do premennej neukladá maximálna hodnota, ale index s maximálnym prvkom (v prípade predvoleného prvého prvku by bol teda 0). Veľakrát nás totiž zaujíma index, pod ktorým sa maximálna hodnota skrýva, viac, než koľko maximálna hodnota číselne je. Ak napr. Budeme mať v poli zamestnanca (objekty) a budeme chcieť vypísať toho s najvyšším platom, nebude nás zaujímať jeho plat, ale jeho meno. Keď budeme mať index toho zamestnanca, môžeme si potom vypísať jeho ľubovoľný údaj vrátane jeho platu alebo jeho mena.

Na záver možno dodať, že časová zložitosť algoritmu je O (n) a nemali by sme teda operáciu vykonávať príliš často. Ak tomu tak bude, mali by sme sa zamyslieť nad vhodnejšie dátovú štruktúrou, ako je pole. Ponúka sa napríklad zotriedené poľa alebo halda.

Zdrojové kódy

V zdrojových kódoch program v jednom priechodu spočíta minimum aj maximum z daného poľa.

// vrátí pozici minima ze zadaného pole
public static int minimum (int[] list) {
  int min = 0;
  for (int i = 0; i < list.length; i++)
  if (list[i] < list[min])
  min = i;
  return min;
}

// vrátí pozici maxima ze zadaného pole
public static int maximum (int[] list) {
  int max = 0;
  for (int i = 0; i < list.length; i++)
  if (list[i] > list[max])
  max = i;
  return max;
}

// vrátí pozici minima ze zadaného pole
public static int minimum (int[] list) {
  int min = 0;
  for (int i = 0; i < list.Length; i++)
  if (list[i] < list[min])
  min = i;
  return min;
}

// vrátí pozici maxima ze zadaného pole
public static int maximum (int[] list) {
  int max = 0;
  for (int i = 0; i < list.Length; i++)
  if (list[i] > list[max])
  max = i;
  return max;
}

// vrati minumum ze zadaneho pole
function minimum(var list: array of integer): integer;
var min, i: integer;
begin
  min:=0;
  for i:=0 to (length(list) - 1) do
  if (list[i] < list[min]) then
  min:=i;
  result:=min;
end;

// vrati minumum ze zadaneho pole
function maximum(var list: array of integer): integer;
var max, i: integer;
begin
  max:=0;
  for i:=0 to (length(list) - 1) do
  if (list[i] > list[max]) then
  max:=i;
  result:=max;
end;

# vrati pozici minima ze zadaneho pole
def minimum(list)
  min = 0
  list.length.times { |i| min = i if (list[i] < list[min]) }
  return min
end

# vrati pozici maxima ze zadaneho pole
def maximum(list)
  max = 0
  list.length.times { |i| max = i if (list[i] > list[max]) }
  return max
end