Strona główna » Algorytmy » Wyszukiwanie » Iteracyjne wyznaczanie MIN i MAX
 

Iteracyjne wyznaczanie MIN i MAX

https://mattomatti.com/fp01
· Liniowe · Iteracyjne ·

O technice wyszukiwania

Na początek porównujemy pierwszy element z drugim. Mniejszy przyjmujemy jako minimum, a drugi jako maksimum. Następnie analizujemy kolejne dwa elementy. Porównujemy je. Mniejszy porównujemy z aktualnym minimum, a większy z maksimum id odpowiednio przypisujemy wartości. Pozostaje kwestia wyjaśnienia co jeśli lista ma nieparzystą liczbę elementów. W takim przypadku ostatni element na liście porównujemy z minimum oraz maksimum.

Przykład

Weźmy przykładowo listę L:={4, 6, 5, 7, 2, 1, 3}. Algorytm zaczynamy od porównania dwóch pierwszych elementów: 6 > 4, więc przyjmujemy, że minimum to 4, a maksimum to 6. Następnie kroki porównywania przedstawia tabelka: (kursywą zostało zapisane porównanie udowadniające przypisanie nowej wartości)

Porównane el.WynikMinimumMaksimum
5, 75 < 747 (7 > 6)
2, 12 > 11 (1 < 4)7

Pozostał jeden element na liście. Zgodnie z algorytmem porównujemy go z minimum oraz maksimum: 3 > 1 i 3 < 7 czyli nie zmieniamy maksimum oraz minimum. W ten sposób wiemy, że minimum to 1, a maksimum to 7.

Zastanówmy się teraz nad złożonością algorytmu. Dla każdej pary wykonujemy dokładnie 3 porównania. Daje to jedno porównanie mniej niż w przypadku poszukiwania liniowego. Złożoność algorytmu wynosi Θ(n). Należy jednak zauważyć, że jest to szybszy algorytm od tradycyjnego wyszukiwania liniowego, gdzie wykonujemy 2(n - 1) porównań.

Implementacja

Funkcja, która będzie wyszukiwać równocześnie MIN i MAX przyjmuje cztery argumenty: lista - lista liczb, n - ilość elementów na liście oraz wskaźniki gdzie znajdują się wartości min i max.

  1. void findMinMax(double* lista, int n, double &min, double &max){
  2.   if(lista[0] <= lista[1]){
  3.     min = lista[0];
  4.     max = lista[1];
  5.   } else {
  6.     min = lista[1];
  7.     max = lista[0];
  8.   }

(1.) Nasza funkcja przyjmuje cztery argumenty: lista - lista liczb rzeczywistych, n - określa ile elementów ma lista. Ostatnie dwa to min i max. To odpowiednio element minimalny i maksymalny. (2.) Nasz pierwszy krok polega wyznaczeniu początkowej wartości minimum i maksimum. Porównujemy dwa pierwsze elementy i odpowiednio przypisujemy wartości min oraz max. Jeśli pierwszy większy od drugiego to (3. - 4.), a w przeciwnym wypadku (6. - 7.).

  1.   int i = 2;
  2.   int dl = n - 1 - (n % 2);

(9.) Iteracje rozpoczniemy od trzeciego elementu. (10.) Musimy też prawidłowo wyznaczyć do którego elementu będziemy wykonywać iteracje. W przypadku parzystej liczby elementów to n - 1. W przypadku nieparzystej ilości nie rozpatrujemy ostatniego elementu czyli dl = n - 2.

  1.   while(i < dl){
  2.     if(lista[i] <= lista[i + 1]){
  3.       if(lista[i] < min) min = lista[i];
  4.       if(lista[i + 1] > max) max = lista[i + 1];
  5.     } else {
  6.       if(lista[i + 1] < min) min = lista[i + 1];
  7.       if(lista[i] > max) max = lista[i];
  8.     }
  9.     i += 2;
  10.   }

(11.) W pętli porównujemy kolejne pełne pary elementów. Zmienne min i max zmieniamy zgodnie z algorytmem. (19.) Na koniec każdej iteracji zwiększamy i o 2, ponieważ przechodzimy do kolejnej pary elementów.

  1.   if(n % 2){
  2.     if(lista[n - 1] < min) min = lista[n - 1];
  3.     if(lista[n - 1] > max) max = lista[n - 1];
  4.   }
  5. }

(21.) Ostatni przypadek wykonujemy kiedy lista ma długość nieparzystą. (22., 23.) Porównujemy wtedy ostatni element z aktualnym minimum oraz maksimum.

Uproszczenie implementacja

Załóżmy, że początkowo naszym elementem minimalnym i maksymalny jest pierwszy element z listy. Następnie jeśli długość naszej listy jest nieparzysta to zaczynamy rozpatrywać kolejne pary od drugiego elementu. W przypadku parzystej długości zaczynamy od pierwszego elementu. Pomimo ustabilizowania ilości porównań złożoność algorytmu nie zmienia się i pozostaje liniowa.

  1. void findMinMax(double* lista, int n, double &min, double &max){
  2.   min = max = lista[0];
  3.   int i = n % 2;
  4.   while(i < n){
  5.     if(lista[i] <= lista[i + 1]){
  6.       if(lista[i] < min) min = lista[i];
  7.       if(lista[i + 1] > max) max = lista[i + 1];
  8.     } else {
  9.       if(lista[i + 1] < min) min = lista[i + 1];
  10.       if(lista[i] > max) max = lista[i];
  11.     }
  12.     i += 2;
  13.   }
  14. }

(1.) Nagłówek funkcji pozostaje niezmieniony. (2.) Przyjmujemy, że minimum i maksimum to pierwszy element na liście. (4. - 13.) Pętla while jest identyczna jak w przypadku poprzedniej implementacji.

Testowanie funkcji

Obydwie wersje funkcji można przetestować poniższą funkcja main(). Po uruchomieniu wczyta od użytkownika długość listy n i wczyta n liczb. Następnie na konsolę zostanie wypisana wartość MIN oraz MAX.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   double* L = new double[n];
  5.   for(int i = 0; i < n; i++)
  6.     cin >> L[i];
  7.   double min, max;
  8.   findMinMax(L, n, min, max);
  9.   cout << "min: " << min << endl;
  10.   cout << "max: " << max << endl;
  11.   delete[] L;
  12.   system("pause");
  13.   return 0;
  14. }

Nową wersje funkcji testujemy funkcją main() z poprzedniej implementacji.

Zadania

Zadanie 1

Przepisz algorytm, aby program wczytywał listę znaków. Elementem minimalnym ma być element, który występuje najbliżej a w alfabecie. Elementem maksymalnym będzie znak, który leży najdalej w alfabecie.

Przykładowo dla listy [z, h, b, x, k] program zwróci:

  1. min: b
  2. max: z