Jednoczesne wyszukiwanie minimum i maksimum (optymalne)
Jednoczesne wyszukiwanie minimum i maksimum jest dość często wykorzystywanym algorytmem w informatyce. Jeśli chcesz więcej się dowiedzieć o przykładowym wykorzystaniu algorytmu, przeczytaj artykuł Jednoczesne wyszukiwanie minimum i maksimum.
Sugeruję również przeczytanie wspomnianego artykułu, bowiem ten artykuł przedstawia inną wersją algorytmu jednoczesnego wyszukiwania minimum i maksimum. Szczerze mówiąc w tym artykule jest przedstawiony algorytm optymalny (czyli najlepszy, najszybszy), a we wspomnianym artykule jest opisany nieco gorszy, ale zarazem prostszy algorytm.
Sprecyzujmy warunki algorytmu:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz dwa operatory:
mniejszy niż oraz większy niż.
Wynik: Indeks (numer) pierwszego najmniejszego elementu spośród n podanych elementów (czyli liczba 1 ... n)
oraz indeks (numer) pierwszego największego elementu spośród n podanych elementów (czyli liczba 1 ... n)
Algorytm w postaci listy kroków (wersja optymalna)
- Zmiennej pomocniczej min przypisujemy 1
- Zmiennej pomocniczej max przypisujemy 1
-
Dla zmiennej i od 2 do n-1 z krokiem co 2 wykonujemy:
- Zmiennej pomocniczej max_lok przypisujemy indeks większej liczby z pary x[2*i], x[2*i+1] (czyli przypiszemy 2i lub i+1)
- Zmiennej pomocniczej min_lok przypisujemy indeks mniejszej liczby z pary x[i], x[i+1] (czyli przypiszemy i lub i+1)
- jeśli element x[max_lok] jest większy (w sensie użytego operatora) od elementu x[max], to zmiennej max przypisujemy wartość max_lok
- jeśli element x[min_lok] jest mniejszy (w sensie użytego operatora) od elementu x[min], to zmiennej min przypisujemy wartość min_lok
-
Jeśli n jest liczbą nieparzystą, to kończymy algorytm. Jeśli n jest liczbą parzystą wykonujemy następujące kroki:
- jeśli element x[n] jest większy (w sensie użytego operatora) od elementu x[max], to zmiennej max przypisujemy wartość n i kończymy algorytm
- jeśli element x[n] jest mniejszy (w sensie użytego operatora) od elementu x[min], to zmiennej min przypisujemy wartość n i kończymy algorytm
- Kończymy algorytm.
