mfranczak.pl

Jednoczesne znajdowanie największego i najmniejszego elementu w zbiorze

Wyróżniamy dwie metody jednoczesnego znajdowania największego i najmniejszego elementu w zbiorze:

1. Algorytm naiwny
   polega na zastosowaniu algorytmu szukania minimum dla n elementów, usunięciu elementu najmniejszego ze zbioru a następnie zastosowania algorytmu szukania maksimum dla zbioru składającego się z n-1 elementów (czyli pomniejszonego o element najmniejszy)
   W algorytmie naiwnym wykonujemy n-1+n-2=2n-3 porównań
2. Algorytm optymalny – metoda dziel i zwyciężaj
   
   Przy parzystej liczbie elementów wykonujemy najpierw n/2 porównań aby podzielić zbiór na dwie części i w każdej części wykonujemy n/2-1 porównań czyli razem:
   n/2 + n/2 -1 + n/2 -1 = 3n/2 -2
   Przy nieparzystej liczbie elementów ostatni element pozostaje zapamiętany w zmiennej pomocniczej a na samym końcu porównujemy do z największym i najmniejszym znalezionym elementem. W szczególnym przypadku to właśnie ten ostatni element może być minimalny bądź maksymalny.