Wyszukiwanie elementu minimalnego (minimum) / maksymalnego (maksimum)
Znajdowanie elementu minimalnego jest bardzo często wykorzystywanym algorytmem. Algorytm taki jest wykorzystywany m.in. w niektórych algorytmach sortowania. Warto zatem dowiedzieć się, w jaki sposób znaleźć element minimalny.
UWAGA: Na identycznej zasadzie działa algorytm znajdowania elementu maksymalnego. Zatem jeśli chcesz się dowiedzieć, jak znaleźć element maksymalny, również przeczytaj ten artykuł.
Sprecyzujmy warunki algorytmu:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator mniejszy niż
za pomocą którego będziemy porównywać elementy
Wynik: Indeks (numer) pierwszego najmniejszego elementu spośród n podanych elementów (czyli liczba 1 ... n)
Algorytm w postaci listy kroków
- Zmiennej pomocniczej k przypisujemy 1
-
Dla zmiennej i od 2 do n wykonujemy:
- Jeśli element x[i] jest mniejszy (w sensie użytego operatora) od elementu x[k], to zmiennej k przypisujemy wartość i
- Element minimalny to element o indeksie k. Jego wartość to x[k]. Kończymy algorytm.
Algorytm jest bardzo prosty. Oto idea algorytmu (różni się od realizacji): Zakładamy, że elementem najmniejszym jest pierwszy element. Następnie każdy następny element porównujemy z elementem pierwszym i jeśli element ten jest mniejszy od pierwszego elementu, to teraz wszystkie elementy będziemy porównywać z tym nowym elementem.
W powyższym algorytmie, tak naprawdę porównujemy tylko indeksy elementów - dzięki temu, jeśli elementy będą bardzo duże, nie będziemy musieli tracić miejsca w pamięci na przechowywanie dużej zmiennej pomocniczej.
Dodatkowo w powyższym algorytmie wiemy, który element jest elementem najmniejszym. Jest to element k. Zauważ ponadto, że zawsze znajdujemy indeks pierwszego najmniejszego elementu, tzn. jeśli mamy elementy 2 3 2, to za element najmniejszy zostaje uznane pierwsze wystąpienie liczby 2.
