Lekce 1 - 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

{PHP}
// vrátí pozici minima ze zadaného pole
function minimum(array $list) {
  $min = 0;
  for ($i = 0; $i < count($list); $i++)
      if ($list[$i] < $list[$min])
        $min = $i;
  return $min;
}

// vrátí pozici maxima ze zadaného pole
function maximum(array $list) {
  $max = 0;
  for ($i = 0; $i < count($list); $i++)
    if ($list[$i] > $list[$max])
        $max = $i;
  return $max;
}


$list = [4, 20, 8, 14, 2, 17, 19, 2];
echo "Pozice minima: ". minimum($list);
echo "\n<br>";
echo "Pozice maxima: ". maximum($list);

{/PHP}

V další lekci, Sekvenční vyhledávání, si ukážeme velmi jednoduchý algoritmus pro vyhledávání prvku v nesetříděné datové struktuře (poli, seznamu) a jeho následné vylepšení malým trikem.

Článek pro vás napsal David Hartinger

Uživatelské hodnocení:

37 hlasů

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.

Aktivity