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
    https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcT3KuAP3IMYkBlwC8bZMYe2NjK1zvnRSwUsX-l4SIwro8xyh-nuFA
    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.