Jednoczesne znajdywanie maksymalnego i minimalnego elementu

Jednoczesne znajdywanie maksymalnego i minimalnego 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 min_Z oraz z max_Z. 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 min_Z. Wystarczy porównanie z max_Z. To samo dotyczy elementu mniejszego – porównujemy go tylko z min_Z. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z min_Z i max_Z). 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 min_Z.
Element większy porównujemy z max_Z.

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 Z, n N
Z	–	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:

Element minimalny i maksymalny w tablicy Z

Zmienne pomocnicze

i	–	przebiega przez kolejne indeksy elementów Z. i C
maxZ	–	tymczasowy element maksymalny
maxp	–	pozycja tymczasowego elementu maksymalnego

Lista kroków:

K01:	Jeśli n mod 2 = 1, Z[n] ← Z[n-1]	; jeśli nieparzysta liczba elementów, dublujemy ostatni
K02:	minZ ← największa liczba całkowita	; inicjujemy minZ i maxZ
K03:	maxZ ← najmniejsza liczba całkowita
K04:	i ← 0
K05:	Dopóki i < n wykonuj K06...K12	; wybieramy pary kolejnych elementów
K06:	Jeśli Z[i] > Z[i+1], to idź do K10	; rozdzielamy je na element mniejszy i większy
K07:	Jeśli Z[i] < minZ, to minZ ← Z[i]	; Z[i] - mniejszy, Z[i+1] - większy
K08:	Jeśli Z[i+1] > maxZ, to maxZ ← Z[i+1]
K09:	Idź do K12
K10:	Jeśli Z[i] > maxZ, to maxZ ← Z[i]	; Z[i] - większy, Z[i+1] - mniejszy
K11:	Jeśli Z[i+1] < minZ, to minZ ← Z[i+1]
K12:	i ← i + 2	; przechodzimy do następnej pary elementów
K13:	Pisz minZ, maxZ	; wyprowadzamy wyniki
K14:	Zakończ