Algorytmy wyszukujące - jednoczesne max i min

Zadanie jest następujące:

W n elementowym zbiorze danych znaleźć element maksymalny i minimalny.

Jeśli podejdziemy do tego zadania w sposób tradycyjny, to wyszukanie elementu maksymalnego będzie wymagało wykonania n - 1 porównań (porusz poprzedni rozdział). Podobnie jest dla elementu minimalnego. Zatem złożoność obliczeniowa problemu wyszukania elementu maksymalnego i minimalnego będzie równa:

T(n) = 2(n - 1) = 2n - 2

Czy można ten wynik poprawić? Okazuje się, że tak. Musimy zastosować zasadę Dziel i Zwyciężaj (ang. Divide & Conquer). Polega ona na podziale problemu na mniejsze problemy i wyznaczeniu rozwiązania z rozwiązań problemów mniejszych. W naszym przypadku zbiór rozdzielimy na dwa podzbiory - w jednym będą elementy mniejsze a w drugim elementy większe. W podzbiorze z elementami mniejszymi wyznaczymy element minimalny, a w podzbiorze z elementami większymi wyznaczymy element maksymalny.

Najpierw sprawdzimy, czy n jest liczbą parzystą. Jeśli nie, to na końcu zbioru dublujemy ostatni element. Parzysta liczba elementów jest nam potrzebna do zgrabnego podziału zbioru na dwie połówki. Zdublowanie ostatniego elementu zbioru nie wpłynie na wyznaczenie elementu minimalnego i maksymalnego.

Ze zbioru pobieramy kolejne dwa elementy i porównujemy ze sobą. Element mniejszy jest kandydatem na element minimalny. Element większy jest kandydatem na element maksymalny. Zatem po porównaniu dokonujemy dla mniejszego elementu testu na element minimalny, a dla większego dokonujemy testu na element maksymalny. Po przeglądnięciu wszystkich par elementów zbioru znajdujemy element minimalny i maksymalny.

Policzmy ilość niezbędnych porównań:

Ponieważ ze zbioru pobieramy po dwa elementy, to podziały na elementy mniejsze i większe wymagają ⁿ/₂ porównań. Po wykonaniu każdego takiego porównania musimy sprawdzić, czy wyznaczone elementy są odpowiednio elementem minimalnym i maksymalnym. Czyli otrzymujemy ⁿ/₂ porównań przy teście na element minimalny oraz ⁿ/₂ porównań przy teście na element maksymalny. Zatem złożoność obliczeniowa naszego algorytmu wyrazi się wzorem:

T(n) =
3 n < 2n - 2

2

Otrzymany wynik jest dużo korzystniejszy niż wynik poprzedni. Zysk powstaje stąd, iż elementu minimalnego i maksymalnego poszukujemy w podzbiorach o liczebności dwa razy mniejszej niż zbiór wyjściowy.

Klasa złożoności obliczeniowej nie ulega zmianie i wynosi O(n).

Dane wejściowe

n - liczba elementów w zbiorze; n N, n > 0

d[ ] - zbiór, w którym poszukujemy elementu maksymalnego. Indeksy elementów rozpoczynają się od 1. Jeśli liczba elementów jest nieparzysta, to w zbiorze powinno być miejsce na jeden dodatkowy element.

Dane wyjściowe

w_min - wartość wyznaczonego elementu minimalnego;

p_min - pozycja elementu minimalnego; p_min N, 1 p_min n

w_max - wartość wyznaczonego elementu maksymalnego;

p_max - pozycja elementu maksymalnego; p_max N, 1 p_max n

Zmienne pomocnicze

i - xxx i N, i {2,3,...,10}

krok 1: Jeśli n mod 2 0, to d[n + 1] d[n]

krok 2: w_min d[1]; w_max d[1]

krok 3: p_min 1; p_max 1

krok 4: i 1

krok 5: Dopóki i n: wykonuj kroki 6...12

krok 6:     Jeśli d[i] < d[i + 1], to idź do kroku 7. Inaczej idź do kroku 10

krok 7:     Jeśli d[i] < w_min, to w_min d[i];   p_min i

krok 8:     Jeśli d[i + 1] > w_max, to w_max d[i + 1];   p_max i + 1

krok 9:     Idź do kroku 12

krok 10:     Jeśli d[i + 1] < w_min, to w_min d[i + 1];   p_min i + 1

krok 11:     Jeśli d[i] > w_max, to w_max d[i];   p_max i

krok 12:     i i + 2 i wróć do kroku 5

krok 13: Jeśli p_min > n, to p_min p_min - 1

krok 14: Jeśli p_max > n, to p_max p_max - 1

krok 15: Zakończ algorytm

Pierwszy test w algorytmie sprawdza, czy zbiór d[ ] składa się z parzystej liczby elementów (parzysta liczba elementów jest niezbędna do równego podziału na dwie połówki). Jeśli nie, to wymuszamy parzystą liczbę elementów przez zdublowanie ostatniego elementu zbioru.

Następnie inicjujemy zmienne dla elementu minimalnego i maksymalnego. Tymczasowo wpisujemy do nich wartość pierwszego elementu zbioru oraz pozycję pierwszego elementu.

Rozpoczynamy pętlę przeszukującą zbiór. W pętli porównujemy ze sobą kolejne pary elementów zbioru - i-ty z (i+1)-szym. Porównanie to pozwala nam określić, który z tych elementów jest kandydatem na element minimalny a który na maksymalny. W zależności od wyniku porównania idziemy jedną z dwóch ścieżek.

Ścieżką TAK podążamy, gdy element i-ty jest mniejszy od elementu (i+1)-szego. W takim przypadku sprawdzamy, czy i-ty element jest nowym elementem minimalnym, a (i+1)-szy jest nowym elementem maksymalnym. Jeśli któryś z tych warunków jest spełniony, to odpowiednio modyfikujemy zmienne dla elementu minimalnego i maksymalnego.. W przypadku ścieżki NIE mamy sytuację odwrotną. Element i-ty jest testowany na element maksymalny, a element (i+1)-szy na element minimalny (zobacz na uwagi końcowe).

Po wykonaniu testów zwiększamy indeks i o 2, czyli przechodzimy do kolejnej pary elementów w zbiorze d[ ]. Pętla jest wykonywana dotąd, aż wszystkie pary zostaną przetworzone. Na wyjściu w zmiennych w_min, p_min mamy wartość i pozycję elementu minimalnego, a w w_max i p_max wartość i pozycję elementu maksymalnego.

Na koniec musimy jeszcze sprawdzić, czy wyznaczona pozycja elementu minimalnego p_min nie leży poza zbiorem. Może się tak zdarzyć, gdy najmniejszy element znajduje się na ostatniej pozycji w zbiorze, a zbiór posiada nieparzystą liczbę elementów. W takiej sytuacji dublowaliśmy ostatni element. Zatem porównanie d[i] < d[i + 1] da wynik negatywny, ponieważ oba elementy są równe. Algorytm zaliczy jako w_min element na pozycji i + 1, a to jest poza ostatnim elementem wejściowego zbioru. Wystarczy jedynie zmniejszyć o 1 wartość pozycji p_min i wszystko będzie w porządku. Kończymy algorytm.

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

Program szuka elementu minimalnego i maksymalnego w 19-to elementowym zbiorze liczb pseudolosowych o wartościach z zakresu od 0 do 99. Znalezione elementy są odpowiednio zaznaczane.

Efekt uruchomienia programu
Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego ------------------------------------------------------------ (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie 48 68 63 62 78 <83> 32 32 61 81 23 33 60 > 5< 7 35 18 61 78 wmin = 5 na pozycji 14 wmax = 83 na pozycji 6 KONIEC. Naciśnij dowolny klawisz...

Efekt uruchomienia programu

Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
------------------------------------------------------------
(C)2006 mgr Jerzy Wałaszek                   I LO w Tarnowie

 48  68  63  62  78 <83> 32  32  61  81  23  33  60 > 5<  7  35  18  61  78

wmin =  5 na pozycji 14
wmax = 83 na pozycji  6

KONIEC. Naciśnij dowolny klawisz...

// Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
//-------------------------------------------------------------
// (C)2006 mgr Jerzy Wałaszek                   I LO w Tarnowie
//-------------------------------------------------------------

program searchminmax;

{$APPTYPE CONSOLE}

const
  N = 19; // liczba elementów w zbiorze - specjalnie nieparzysta!
  M = 99; // maksymalna wartość elementów

// Deklaracja zmiennych

var
  d                     : array[1..N + 1] of cardinal;
  i,wmin,pmin,wmax,pmax : cardinal;

begin
  writeln('Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego');
  writeln('------------------------------------------------------------');
  writeln('(C)2006 mgr Jerzy Walaszek                   I LO w Tarnowie');
  writeln;

// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu minimalnego i maksymalnego

  randomize;
  for i := 1 to N do d[i] := random(M + 1);

// Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
// dublujemy ostatni element

  if N mod 2 <> 0 then d[N + 1] := d[N];

// Inicjujemy tymczasowe wartosci minimalne i maksymalne

  wmin := d[1];  pmin := 1; wmax := d[1];  pmax := 1;

// Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
// poszukujemy elementu minimalnego. W podzbiorze elementów większych
// poszukujemy elementu maksymalnego.

  i := 1;
  while i <= N do
  begin
    if d[i] < d[i + 1] then
    begin
      if d[i] < wmin then
      begin
        wmin := d[i]; pmin := i;
      end;
      if d[i + 1] > wmax then
      begin
        wmax := d[i + 1]; pmax := i + 1;
      end;
    end
    else
    begin
      if d[i + 1] < wmin then
      begin
        wmin := d[i + 1]; pmin := i + 1;
      end;
      if d[i] > wmax then
      begin
        wmax := d[i]; pmax := i;
      end;
    end;
    inc(i,2);
  end;

  if pmin = N + 1 then dec(pmin);

// Prezentujemy wyniki

  for i := 1 to N do
    if i = pmin then      write('>',d[i]:2,'<')
    else if i = pmax then write('<',d[i]:2,'>')
    else                  write(' ',d[i]:2,' ');
  writeln; writeln;
  writeln('wmin = ',wmin:2,' na pozycji nr ',pmin:2);
  writeln('wmax = ',wmax:2,' na pozycji nr ',pmax:2);
  writeln;

// Gotowe

  write('KONIEC. Nacisnij klawisz Enter...'); readln;
end.

// Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
//-------------------------------------------------------------
// (C)2006 mgr Jerzy Wałaszek                   I LO w Tarnowie
//-------------------------------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

const int N = 19; // liczba elementów w zbiorze - specjalnie nieparzysta!
const int M = 99; // maksymalna wartość elementów

int main(void)
{
  unsigned d[N + 2],i,wmin,pmin,wmax,pmax;

  cout << "Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego\n"
          "------------------------------------------------------------\n"
          "(C)2006 mgr Jerzy Walaszek                   I LO w Tarnowie\n\n";

// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu minimalnego i maksymalnego

  srand((unsigned)time(NULL));
  for(i = 1; i <= N; i++) d[i] = rand() % (M + 1);

// Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
// dublujemy ostatni element

  if(N % 2) d[N + 1] = d[N];

// Inicjujemy tymczasowe wartosci minimalne i maksymalne

  wmin = wmax = d[1];  pmin = pmax = 1;

// Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
// poszukujemy elementu minimalnego. W podzbiorze elementów większych
// poszukujemy elementu maksymalnego.

  for(i = 1; i <= N; i += 2)
    if(d[i] < d[i + 1])
    {
      if(d[i] < wmin)
      {
        wmin = d[i]; pmin = i;
      }
      if(d[i + 1] > wmax)
      {
        wmax = d[i + 1]; pmax = i + 1;
      }
    }
    else
    {
      if(d[i + 1] < wmin)
      {
        wmin = d[i + 1]; pmin = i + 1;
      }
      if(d[i] > wmax)
      {
        wmax = d[i]; pmax = i;
      }
    }
  if(pmin == N + 1) pmin--;

// Prezentujemy wyniki

  for(i = 1; i <= N; i++)
    if(i == pmin)      cout << ">" << setw(2) << d[i] << "<";
    else if(i == pmax) cout << "<" << setw(2) << d[i] << ">";
    else               cout << " " << setw(2) << d[i] << " ";
  cout << "\n\nwmin = " << setw(2) << wmin << " na pozycji nr " << setw(2) << pmin
       <<   "\nwmax = " << setw(2) << wmax << " na pozycji nr " << setw(2) << pmax
       << "\n\n";

// Gotowe

  system("pause"); return 0;
}

' Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
'-------------------------------------------------------------
' (C)2006 mgr Jerzy Wałaszek                   I LO w Tarnowie
'-------------------------------------------------------------

Module Module1

  Sub Main()
    Const N = 19 ' liczba elementów w zbiorze - specjalnie nieparzysta!
    Const M = 99 ' maksymalna wartość elementów

    ' Deklaracja zmiennych

    Dim d(N + 1), i, wmin, pmin, wmax, pmax As UInteger

    Console.WriteLine("Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego")
    Console.WriteLine("------------------------------------------------------------")
    Console.WriteLine("(C)2006 mgr Jerzy Wałaszek                   I LO w Tarnowie")
    Console.WriteLine()

    ' Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
    ' elementu minimalnego i maksymalnego

    Randomize()
    For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next

    ' Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
    ' dublujemy ostatni element

    If N \ 2 <> 0 Then d(N + 1) = d(N)

    ' Inicjujemy tymczasowe wartosci minimalne i maksymalne

    wmin = d(1) : pmin = 1 : wmax = d(1) : pmax = 1

    ' Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
    ' poszukujemy elementu minimalnego. W podzbiorze elementów większych
    ' poszukujemy elementu maksymalnego.

    For i = 1 To N Step 2
      If d(i) < d(i + 1) Then
        If d(i) < wmin Then
          wmin = d(i) : pmin = i
        End If
        If d(i + 1) > wmax Then
          wmax = d(i + 1) : pmax = i + 1
        End If
      Else
        If d(i + 1) < wmin Then
          wmin = d(i + 1) : pmin = i + 1
        End If
        If d(i) > wmax Then
          wmax = d(i) : pmax = i
        End If
      End If
    Next

    If pmin = N + 1 Then pmin -= 1

    ' Prezentujemy wyniki

    For i = 1 To N
      If i = pmin Then
        Console.Write(">{0,2}<", d(i))
      ElseIf i = pmax Then
        Console.Write("<{0,2}>", d(i))
      Else
        Console.Write(" {0,2} ", d(i))
      End If
    Next
    Console.WriteLine()
    Console.WriteLine()
    Console.WriteLine("wmin = {0,2} na pozycji {1,2}", wmin, pmin)
    Console.WriteLine("wmax = {0,2} na pozycji {1,2}", wmax, pmax)
    Console.WriteLine()

    ' Gotowe

    Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
    Console.ReadLine()

  End Sub

End Module

# -*- coding: cp1250 -*-
# Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
#-------------------------------------------------------------
# (C)2006 mgr Jerzy Wałaszek                   I LO w Tarnowie
#-------------------------------------------------------------

import random

N = 19 # liczba elementów w zbiorze - specjalnie nieparzysta!
M = 99 # maksymalna wartość elementów

d = []

print "Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego"
print "------------------------------------------------------------"
print "(C)2006 mgr Jerzy Walaszek                   I LO w Tarnowie"
print

# Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
# elementu minimalnego i maksymalnego

for i in range(N): d.append(random.randint(0, M))

# Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
# dublujemy ostatni element

if N % 2: d.append(d[N - 1])

# Inicjujemy tymczasowe wartości minimalne i maksymalne

wmin = wmax = d[0]; pmin = pmax = 0

# Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
# poszukujemy elementu minimalnego. W podzbiorze elementów większych
# poszukujemy elementu maksymalnego.

for i in range(0, N, 2):
  if d[i] < d[i + 1]:
    if d[i]     < wmin: wmin, pmin = d[i], i
    if d[i + 1] > wmax: wmax, pmax = d[i + 1], i + 1
  else:
    if d[i + 1] < wmin: wmin, pmin = d[i + 1], i + 1
    if d[i]     > wmax: wmax, pmax = d[i], i
if pmin == N: pmin -= 1

# Prezentujemy wyniki

for i in range(N):
  if   i == pmin: print ">%2d<" % d[i],
  elif i == pmax: print "<%2d>" % d[i],
  else:           print " %2d " % d[i],
print
print
print "wmin = %2d na pozycji %2d" % (wmin, pmin)
print "wmax = %2d na pozycji %2d" % (wmax, pmax)
print

# Gotowe

raw_input("KONIEC. Naciśnij klawisz Enter...")

<html>
  <head>
  </head>
  <body>
    <div align="center">
      <form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
                   BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
                   PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
                   PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
                   BACKGROUND-COLOR: #ffcc66" name="frmmaxmin">
        <h4 id="out_t" style="TEXT-ALIGN: center">
          Jednoczesne wyszukiwanie elementu<br>
          maksymalnego i minimalnego
        </h4>
        <p style="TEXT-ALIGN: center">
          (C)2006 mgr Jerzy Wałaszek<br>
          I LO w Tarnowie
        </p>
        <hr>
        <p style="TEXT-ALIGN: center">
          <input type="button" value="Szukaj" name="B1" onclick="main();">
        </p>
        <p style="TEXT-ALIGN: center" id="t_out">...</p>
      </form>

<script language=javascript>

// Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
//-------------------------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------------------------

function main()
{
  var N = 19; // liczba elementów w zbiorze - specjalnie nieparzysta!
  var M = 99; // maksymalna wartość elementów
  var d = new Array(N + 2);
  var i,wmin,pmin,wmax,pmax,t;

// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu minimalnego i maksymalnego

  for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * (M + 1));

// Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
// dublujemy ostatni element

  if(N % 2) d[N + 1] = d[N];

// Inicjujemy tymczasowe wartosci minimalne i maksymalne

  wmin = wmax = d[1]; pmin = pmax = 1;

// Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
// poszukujemy elementu minimalnego. W podzbiorze elementów większych
// poszukujemy elementu maksymalnego.

  for(i = 1; i <= N; i += 2)
    if(d[i] < d[i + 1])
    {
      if(d[i] < wmin)
      {
        wmin = d[i]; pmin = i;
      }
      if(d[i + 1] > wmax)
      {
        wmax = d[i + 1]; pmax = i + 1;
      }
    }
    else
    {
      if(d[i + 1] < wmin)
      {
        wmin = d[i + 1]; pmin = i + 1;
      }
      if(d[i] > wmax)
      {
        wmax = d[i]; pmax = i;
      }
    }
  if(pmin == N + 1) pmin--;

// Prezentujemy wyniki

  t = "";
  for(i = 1; i <= N; i++)
    if(i == pmin)      t += "<b><font color=blue>&gt;" + d[i] + "&lt;</font></b>";
    else if(i == pmax) t +=  "<b><font color=red>&lt;" + d[i] + "&gt;</font></b>";
    else               t += " " + d[i] + "&nbsp;";
    t += "<br><br>wmin = " + wmin + " na pozycji nr " + pmin +
             "<br>wmax = " + wmax + " na pozycji nr " + pmax

// Gotowe

  document.getElementById("t_out").innerHTML = t;
}

</script>

    </div>
  </body>
</html>

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Źródło: mgr Jerzy Wałaszek

technologia wyszukiwanie programowanie algorytmy algorytmika

n	-	liczba elementów w zbiorze; n N, n > 0
d[ ]	-	zbiór, w którym poszukujemy elementu maksymalnego. Indeksy elementów rozpoczynają się od 1. Jeśli liczba elementów jest nieparzysta, to w zbiorze powinno być miejsce na jeden dodatkowy element.

w_min	- wartość wyznaczonego elementu minimalnego;
p_min	- pozycja elementu minimalnego; p_min N, 1 p_min n
w_max	- wartość wyznaczonego elementu maksymalnego;
p_max	- pozycja elementu maksymalnego; p_max N, 1 p_max n

krok 1:	Jeśli n mod 2 0, to d[n + 1] d[n]
krok 2:	w_min d[1]; w_max d[1]
krok 3:	p_min 1; p_max 1
krok 4:	i 1
krok 5:	Dopóki i n: wykonuj kroki 6...12
krok 6:	Jeśli d[i] < d[i + 1], to idź do kroku 7. Inaczej idź do kroku 10
krok 7:	Jeśli d[i] < w_min, to w_min d[i]; p_min i
krok 8:	Jeśli d[i + 1] > w_max, to w_max d[i + 1]; p_max i + 1
krok 9:	Idź do kroku 12
krok 10:	Jeśli d[i + 1] < w_min, to w_min d[i + 1]; p_min i + 1
krok 11:	Jeśli d[i] > w_max, to w_max d[i]; p_max i
krok 12:	i i + 2 i wróć do kroku 5
krok 13:	Jeśli p_min > n, to p_min p_min - 1
krok 14:	Jeśli p_max > n, to p_max p_max - 1
krok 15:	Zakończ algorytm



		Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.