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.