Hledání extrému (minima a maxima) v poli

Algoritmy Vyhledávání Hledání extrému (minima a maxima) v poli

Algoritmus pro nalezení největšího nebo nejmenšího prvku v poli je sice zřejmý, ale pro jistotu i úplnost jsem se ho rozhodl uvést.

Budu zde popisovat vyhledání maxima, vyhledání minima bude potom analogické. Algoritmus bude mít zpočátku v proměnné uložené výchozí maximum. Potom projede pole prvek po prvku a pokud je nějaký prvěk větší, než toto maximum, bude novým maximem tento prvek. Po projetí pole bude v proměnné jistě maximum z daných hodnot v poli.

Teď jak je to s tím výchozím maximem. Některé z vás jistě napadlo dát mu hodnotu 0. Co když ale budeme mít pole plné záporných čísel? Naše maximum bude maximem i po průchodu polem (protože nic nebude větší než 0) a jeho hodnota je naprosto chybná, protože se v poli ani nevyskytuje. Dáme mu tedy nějakou hodnotu z pole, vůbec nezáleží jakou. Nabízí se např. první prvek, protože k němu máme nejsnažší přístup.

V praxi se také do proměnné neukládá maximální hodnota, ale index s maximálním prvkem (v případě výchozího prvního prvku by byl tedy 0). Mnohdy nás totiž zajímá index, pod kterým se maximální hodnota skrývá, více, než kolik maximální hodnota číselně je. Když např. budeme mít v poli zaměstnance (objekty) a budeme chtít vypsat toho s nejvyšším platem, nebude nás zajímat jeho plat, ale jeho jméno. Když budeme mít index toho zaměstnance, můžeme si potom vypsat jeho libovolný údaj včetně jeho platu nebo jeho jména.

Na závěr lze dodat, že časová složitost algoritmu je O(n) a neměli bychom tedy operaci provádět příliš často. Pokud tomu tak bude, měli bychom se zamyslet nad vhodnější datovou strukturou, než je pole. Nabízí se například setříděné pole nebo halda.

Zdrojové kódy

Ve zdrojových kódech program v jednom průchodu spočítá minimum i maximum z daného pole.

// 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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (3 hlasů) :
55555


 


Miniatura
Všechny články v sekci
Vyhledávací algoritmy
Miniatura
Následující článek
Sekvenční vyhledávání

 

 

Komentáře
Zobrazit starší komentáře (1)

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

:) To je, jako kdybyste pod návod na pečení chleba napsal: "Nebo si ho stačí koupit v obchodě". Zaprvé všechny jazyky nemají takhle chytré a předpřipravené kolekce a zadruhé se často setkáte s tím, že si budete potřebovat napsat nějakou sám, a na míru. Obecně je dobré vědět, jak to uvnitř funguje a mít možnost si to popřípadě upravit dle potřeb.

Odpovědět  +2 20.12.2011 9:55
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
xnash
Neregistrovaný
Avatar
xnash:

chtel jsem se prosimte zeptat, kdyz budu potrebovat nejcastejsi prvek pole,jaky mam pouzit algortimus?

 
Odpovědět 12.11.2012 14:35
Avatar
matesax
Redaktor
Avatar
matesax:

LINQ - GroupBy...

array.GroupBy(item => item).OrderByDescending(g => g.Count()).Select(g => g.Key).First();
 
Odpovědět 12.11.2012 17:19
Avatar
vasek
Neregistrovaný
Avatar
vasek:

ahoj, poradil by mi někdo prosím Vás jak napsat kod pro hledání minima řádku matice? bez knihovny array ale bohužel děkuji

 
Odpovědět 27.11.2012 12:00
Avatar
Veganekk
Člen
Avatar
Veganekk:

Jak bych našel 2 největší prvek v tom poli jestli se mohu zeptat.
Napadlo me seradit pole od nejvetsiho po nejmensi a vypsat treba 2 prvek z pole ale je i jina moznost pomoci maxima hledat ale nejsem si jist jak na to. Dekuji

Odpovědět 7.3.2013 23:20
Rád se učím novým věcem. A věci co nechápu rád pochopím a naučím.
Avatar
martinsakra
Redaktor
Avatar
Odpovídá na Veganekk
martinsakra:

ukládáš si prostě místo 1 maximální hodnoty , 2 hodnoty - max, a druhou max. A každej novej udaj kontorluješ, a) větší než max (true do druhý max = max a do max = aktuální) false - kontroluješ zda je hodnota větší než druhý max

Odpovědět 8.3.2013 10:34
Democracy is two wolves and a lamb voting on what to have for lunch. Liberty is a well-armed lamb contesting the vote.
Avatar
Veganekk
Člen
Avatar
Veganekk:

Trosku nechapu. O kod bych poprosit nemohl pokud bys byl tak laskav.
Zkousel jsem to ve skole ale vzdy mi to vypise neco jineho nez ten 2 prvek...

Editováno 8.3.2013 17:00
Odpovědět 8.3.2013 16:59
Rád se učím novým věcem. A věci co nechápu rád pochopím a naučím.
Avatar
Зайчик
Člen
Avatar
Odpovídá na David Čápka
Зайчик:

hoj, nebylo by to lepší takhle?

public int minimum (Integer[] list) {
  int min = list[0];
  for (int i = 0; i < list.length; i++)
  if (list[i] < min)
      min = list[i];
  return min;
}

a pak použít

int min = myclass.minimum(myarray);

Tím co tam máš, mi to takhle bude vracet 1 nebo 0.

Editováno 13.3.2013 18:57
Odpovědět 13.3.2013 18:57
Коммунизм для нашего будущего!
Avatar
Lubos857
Člen
Avatar
Odpovídá na Зайчик
Lubos857:

Ty vracíš jako návratovou hodnotu hodnotu minima, kdežto sdraco vrací pozici v seznamu, na které se dané minimum nachází.
Nemáš náhodou minimum a maximum seznamu na první a druhé pozici?
Podle mně je ta verze v článku lepší, což je tam mimo jiné i zmíněno ;-)

Odpovědět 13.3.2013 19:37
Protože bagr nežere cukr.
Avatar
Зайчик
Člen
Avatar
Odpovídá na Lubos857
Зайчик:

To je fakt, já si teď potřeboval vytáhnout max,min a moje verze mi přišla lepší. Nepotřeboval jsem index ale přímo hodnotu. Na to je to podle mě lepší. ( můj názor ) :)

Editováno 13.3.2013 19:40
Odpovědět 13.3.2013 19:40
Коммунизм для нашего будущего!
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 11. Zobrazit vše