Zadanie znajdowania elementu maksymalnego lub minimalnego jest typowym zadaniem wyszukiwania, które rozwiązujemy przy pomocy algorytmu wyszukiwania liniowego. Za tymczasowy maksymalny (minimalny) element przyjmujemy pierwszy element zbioru. Następnie element tymczasowy porównujemy z kolejnymi elementami. Jeśli któryś z porównywanych elementów jest większy (mniejszy) od elementu tymczasowego, to za nowy tymczasowy element maksymalny (minimalny) przyjmujemy porównywany element zbioru. Gdy cały zbiór zostanie przeglądnięty, w elemencie tymczasowym otrzymamy element maksymalny (minimalny) w zbiorze.

Poniżej podajemy algorytm wyszukiwania max. Wyszukiwanie min wykonuje się identycznie, zmianie ulega tylko warunek porównujący element tymczasowy z elementem zbioru w kroku K03.

 

Algorytm wyszukiwania elementu maksymalnego w zbiorze

Wejście

n	–	liczba elementów w tablicy T, n N
T	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n  - 1.

Wyjście:

tmax  – wartość elementu maksymalnego.

Zmienne pomocnicze

i	–	przebiega przez kolejne indeksy elementów T. i   C
tmax	–	tymczasowy element maksymalny

Lista kroków:

 

Czasami zależy nam nie tylko na wartości elementu maksymalnego (minimalnego), lecz również na jego pozycji w zbiorze. W tym przypadku musimy, oprócz wartości samego elementu maksymalnego (minimalnego), zapamiętywać jego pozycję, którą na końcu zwracamy jako wynik pracy algorytmu.

 

Algorytm wyszukiwania pozycji elementu maksymalnego w zbiorze

Wejście

n	–	liczba elementów w tablicy T, n N
T	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n  - 1.

Wyjście:

pmax  – pozycja (indeks) elementu maksymalnego
tmax  – wartość elementu maksymalnego.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów T. i   C

Lista kroków:

 

Jeśli do wyszukiwania elementu max  i min  zastosujemy standardowy algorytm, to otrzymamy:

Wejście

n	–	liczba elementów w tablicy T, n N
T	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n  - 1.

Wyjście:

tmax  – wartość elementu maksymalnego.
tmin  – wartość elementu minimalnego.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów T. i   C

 

 

Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy element zbioru z tmin  oraz z tmax. Tutaj tkwi nieefektywność. Obie operacje z kroków K05 i K06 są wykonywane po n  - 1 razy, co daje w sumie 2n  - 2 porównania w całym zbiorze.

Wyobraźmy sobie, iż ze zbioru bierzemy parę 2 elementów i porównujemy je ze sobą. Element większy nie może być minimalnym, zatem nie musimy go już porównywać z tmin. Wystarczy porównanie z tmax. To samo dotyczy elementu mniejszego – porównujemy go tylko z tmin. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z tmin  i tmax). Teraz mamy:

 

Jedno porównanie dwóch elementów, które rozdzieli je na element mniejszy i element większy.
Element mniejszy porównujemy z tmin.
Element większy porównujemy z tmax.

 

Daje to 3 porównania zamiast 4. Ponieważ ze zbioru pobieramy po dwa kolejne elementy, to ich liczba musi być parzysta. Jeśli zbiór ma nieparzystą liczbę elementów, to po prostu dublujemy ostatni element i dostaniemy parzystą liczbę elementów.

Porównanie pary elementów dzieli zbiór na dwa podzbiory – zbiór elementów większych i mniejszych. W podzbiorze elementów większych szukamy elementu maksymalnego, a w podzbiorze elementów mniejszych szukamy minimalnego. Ponieważ ich liczebność jest o połowę mniejsza od liczebności zbioru wejściowego, to wykonamy mniej operacji porównań.

Metoda rozwiązywania problemów przez podział na mniejsze części w informatyce nosi nazwę Dziel i Zwyciężaj (ang. Divide and Conquer). Dzięki niej często udaje się zmniejszyć złożoność obliczeniową wielu algorytmów.

 

Algorytm jednoczesnego wyszukiwania max i min w zbiorze

Wejście

n	–	liczba elementów w tablicy T, n N
T	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n  - 1. Tablica musi umożliwiać dodanie elementu, jeśli n  jest nieparzyste.

Wyjście:

tmax  – wartość elementu maksymalnego.
tmin  – wartość elementu minimalnego.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów Z. i C

Lista kroków: