Algorytm jednoczesnego wyszukiwania minimum i maksimum

W wielu zadaniach algorytmicznych zachodzi potrzeba znalezienia najmniejszego (minimum) oraz największego (maksimum) elementu w zbiorze danych, na przykład w tablicy liczb. Najprostszym rozwiązaniem tego problemu jest wykonanie dwóch osobnych przeglądów danych – jednego w celu znalezienia minimum, a drugiego w celu znalezienia maksimum. Podejście to jest poprawne, lecz nieefektywne, ponieważ wymaga dużej liczby porównań.

Algorytm jednoczesnego wyszukiwania minimum i maksimum umożliwia znalezienie obu wartości w jednym przebiegu danych. Jego istotą jest odpowiednia organizacja porównań, najczęściej poprzez porównywanie elementów parami, co pozwala ograniczyć ich liczbę i zwiększyć efektywność obliczeń.

Warto zauważyć, że algorytm ten można zapisać zarówno w formie iteracyjnej, wykorzystującej pętle, jak i w formie rekurencyjnej, opartej na dzieleniu problemu na mniejsze podproblemy i łączeniu uzyskanych wyników. Dzięki temu algorytm stanowi dobry przykład ilustrujący różne podejścia do rozwiązywania tego samego problemu algorytmicznego.

Metoda „dziel i zwyciężaj”

Strategię „dziel i zwyciężaj” można podzielić na trzy etapy:

• Podziel problem na podproblemy.

• Znajdź rozwiązanie dla każdego podproblemu.

• Połącz rozwiązania podproblemów w rozwiązanie problemu głównego.

Należy pamiętać, że problem musi zostać podzielony na takie same lub bardzo do siebie podobne podproblemy (przynajmniej dwa). Ponadto zbiory danych, dla których rozwiązywane są podproblemy, powinny być niemal jednakowe i stanowić stałą część całego zbioru danych.

Zastosowane techniki „dziel i zwyciężaj” do równoczesnego wyszukiwania w zbiorze największej i najmniejszej wartości.

Algorytm jednoczesnego wyszukiwania wartości minimalnej i maksymalnej, który wykorzystuje strategię dziel i zwyciężaj, składa się z następujących kroków:

1. Sprawdź rozmiar tablicy. Jeśli rozmiar wynosi 1, zwróć element jako minimum i maksimum.

2. Podziel tablicę na dwie równe części.

3. Rekurencyjnie wywołaj algorytm dla dwóch połówek tablicy.

4. W wyniku wywołania rekurencyjnego otrzymasz wartości minimalne i maksymalne dla każdej połówki.

5. Porównaj wartości minimalne i maksymalne dla obu połówek i zwróć wyniki.

6. Porównaj wartości minimalne i maksymalne z obu połówek i wybierz mniejszą wartość jako minimum całej tablicy oraz większą wartość jako maksimum całej tablicy.

7. Zwróć minimum i maksimum jako wynik.

Kroki 2‑5 są wykonywane rekurencyjnie dla każdej połówki tablicy aż do momentu, gdy rozmiar tablicy wynosi 1. W tym przypadku algorytm zwraca jedyny element tablicy jako zarówno minimum, jak i maksimum.

Algorytm wykorzystuje strategię „dziel i zwyciężaj”, dzieląc problem na mniejsze części. Następnie łączy wyniki z mniejszych problemów, aby uzyskać wynik dla całego problemu. W tym przypadku dzieli tablicę na dwie równe części, znajduje wartości minimalne i maksymalne dla każdej połowy, a następnie porównuje je, aby znaleźć wartości minimalne i maksymalne dla całej tablicy.

Pseudokod algorytmu:

funkcja ZnajdzMinMax(tablica, pocz, kon)
    jeżeli kon = pocz
        min ← tablica[pocz]
        max ← tablica[pocz]
        zwróć (min, max)
    jeżeli kon = pocz + 1
        jeżeli tablica[pocz] <= tablica[kon]
            min ← tablica[pocz]
            max ← tablica[kon]
        w przeciwnym razie
            min ← tablica[kon]
            max ← tablica[pocz]
        zwróć (min, max)

    polowa ← (pocz + kon) // 2

    (minLewa, maxLewa) ← ZnajdzMinMax(tablica, pocz, polowa)
    (minPrawa, maxPrawa) ← ZnajdzMinMax(tablica, polowa + 1, kon)

    min ← min(minLewa, minPrawa)
    max ← max(maxLewa, maxPrawa)

    zwróć (min, max)

Słownik