Jednoczesne znajdowanie minimalnego i maksymalnego elementu

Problem

W n-elementowym zbiorze Z znaleźć element maksymalny i minimalny.

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

Wejście

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

Wyjście:

Wartość najmniejszego i największego elementu w tablicy Z.

Zmienne pomocnicze

i	–	przebiega przez kolejne indeksy elementów Z. i   C
maxZ	–	tymczasowy element maksymalny
minZ	–	tymczasowy element minimalny

Numer Operacja Liczba wykonań 1 minZ ← Z[0] 1 2 maxZ ← Z[0] 1 3 i ← 1 1 4 Jeśli i = n, to idź do 9 n 5 Jeśli Z[i] < minZ, to minZ ← Z[i] n - 1 6 Jeśli Z[i] > maxZ, to maxZ ← Z[i] n - 1 7 i ← i + 1 n - 1 8 Idź do 4 n - 1 9 Pisz minZ, maxZ 1 10 Zakończ 1 Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy element zbioru z minZ oraz z maxZ. Tutaj tkwi nieefektywność. Obie operacje nr 5 i 6 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 minZ. Wystarczy porównanie z maxZ. To samo dotyczy elementu mniejszego – porównujemy go tylko z minZ. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z minZ i maxZ). 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 minZ. Element większy porównujemy z maxZ. 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.