Algorytmy wyszukujące - k-ty największy element

Na początek rozwiążmy prostszy problem:

W n elementowym zbiorze (n > 1) znaleźć drugi największy element.

Jeśli zbiór jest uporządkowany, to zadanie staje się trywialnie proste - zwracamy przedostatni element. W przypadku zbioru nieuporządkowanego możemy zbiór posortować i zwrócić przedostatni element. Jednakże sortowanie jest kosztowne i zajmuje drogocenny czas. Istnieje o wiele prostsza metoda, która wymaga jednokrotnego przeglądnięcia zbioru, zatem ma klasę czasowej złożoności obliczeniowej O(n). Co więcej, nie zmienia ona struktury zbioru (kolejności elementów) oraz nie wymaga dodatkowej pamięci zależnej od ilości elementów w zbiorze.

Umówmy się, iż wynikiem poszukiwań będzie wartość elementu zbioru oraz jego położenie, czyli indeks. Dodatkowo nasz algorytm będzie zwracał wartość oraz położenie największego elementu w zbiorze.

Dane wejściowe

n	- ilość elementów w przeszukiwanym zbiorze.  n N
d[ ]	- zbiór, w którym poszukujemy drugiego największego elementu. Indeksy elementów rozpoczynają się od 1.

Dane wyjściowe

w1	- wartość największego elementu zbioru.
p1	- pozycja największego elementu zbioru. p1 N
w2	- wartość drugiego największego elementu zbioru.
p2	- pozycja drugiego największego elementu zbioru. p2 N

Zmienne pomocnicze

i	- zmienna licznikowa pętli. i N

krok 1:	w1 d[n];   p1 n;   w2 d[n - 1];   p2 n - 1
krok 2:	Jeśli w2 > w1, to  w1 w2;   p1 p2
krok 3:	Dla i = n - 2, n - 3,...,1: wykonuj kroki 4...6
krok 4:	Jeśli d[i] > w2, to idź do kroku 5. Inaczej wykonaj następny obieg pętli z kroku 3.
krok 5:	w2 d[i];   p2 i;
krok 6:	Jeśli w2 > w1, to  w1 w2;   p1 p2
krok 7:	Zakończ algorytm

Na początku algorytmu wybieramy ze zbioru dwa ostatnie elementy i umieszczamy je odpowiednio w zmiennych w₁ i w₂. Dlaczego rozpoczynamy od końca zbioru? Otóż jeśli w przyszłości posortujemy zbiór stabilnym algorytmem sortującym (czyli takim, który nie zmienia kolejności elementów równych), to wyznaczony przez nasz algorytm drugi największy element będzie przedostatnim elementem zbioru posortowanego. Rozpoczynając przeglądanie od początku zbioru nie mielibyśmy takiej gwarancji (na przykład w przypadku, gdy w zbiorze są dwa elementy równe drugiemu największemu elementowi zbioru).

W zmiennych p₁ i p₂ zapamiętujemy pozycję tych elementów.

Umawiamy się, iż w₁, p₁ identyfikuje największy element w zbiorze, a w₂ i p₂ identyfikuje drugi największy element. Po inicjalizacji zmiennych musimy sprawdzić, czy wprowadzone do nich dane spełniają ten warunek. Jeśli nie, to wymieniamy ze sobą odpowiednie zawartości zmiennych.

Rozpoczynamy pętlę przeglądającą kolejne elementy zbioru od n - 2 do pierwszego. Pozycje n i n - 1 pomijamy, ponieważ odpowiadające im elementy są już w w₁ i w₂.

W każdym obiegu pętli sprawdzamy, czy i-ty element zbioru jest większy od tymczasowego drugiego największego elementu, czyli w₂. Jeśli tak, to zapamiętujemy i-ty element w w₂ oraz jego pozycję w p₂. Teraz musimy sprawdzić, czy operacja ta nie spowodowała, iż w₂ stało się większe od w₁. Jeśli tak, to wymieniamy ze sobą zawartości zmiennych w₁ z w₂ oraz p₁ z p₂.

Po zakończeniu pętli w zmiennej w₁ mamy wartość największego elementu zbioru, w p₁ jego pozycję w zbiorze, w w₂ mamy wartość drugiego największego elementu zbioru i w p₂ jego pozycję. Algorytm kończymy.

		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 tworzy 100 elementowy zbiór liczb pseudolosowych z zakresu od 0 do 99 i wyszukuje w nim elementu największego oraz drugiego elementu największego.

Wyszukiwanie drugiego największego elementu
-------------------------------------------
(C)2006 mgr Jerzy Wałaszek  I LO w Tarnowie

 31  69   9  75  89  98  38  65  14  71   2  47  67  34  71  94  92  90  39   1
 55  66  36  66  23  99  53  89  51  52  10 |99|  7  52  29   6  16  56  48  79
 31  38  53  45  26   2  31  15  20  27  61  41  21  22  16  85  92  22  95  27
 53   2  86  87 <99> 12  44  80  42  41   2  90  86  13   1  73  19  93  51  83
 36  29  11  24  80  19  97  25  19  94  18  46  35  39  29  97  48  26  19  98

w1 = 99 na pozycji  65
w2 = 99 na pozycji  32

KONIEC. Naciśnij dowolny klawisz...

// Wyszukiwanie drugiego największego elementu
//---------------------------------------------
// (C)2006 mgr Jerzy Wałaszek  I LO w Tarnowie
//---------------------------------------------

program search2b;

{$APPTYPE CONSOLE}

// Procedura wymienia zawartość dwóch zmiennych
// przekazanych jako parametry
//---------------------------------------------
procedure Zamien(var a, b : integer);
var
  x : integer;
begin
  x := a; a := b; b := x;
end;

const
  N = 100;  // Liczba elementów w zbiorze
  M =  99;  // Maksymalna wartość elementu

var
  d             : array[1..N] of integer;
  i,p1,p2,w1,w2 : integer;

begin
  writeln('Wyszukiwanie drugiego najwiekszego elementu');
  writeln('-------------------------------------------');
  writeln('(C)2006 mgr Jerzy Walaszek  I LO w Tarnowie');
  writeln;

// Generujemy zbiór pseudolosowy

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

// Szukamy elementu

  w1 := d[N]; p1 := N; w2 := d[N - 1]; p2 := N - 1;
  if w2 > w1 then
  begin
    Zamien(w1, w2); Zamien(p1, p2);
  end;
  for i := N - 2 downto 1 do
    if d[i] > w2 then
    begin
      w2 := d[i]; p2 := i;
      if w2 > w1 then
      begin
        Zamien(w1, w2); Zamien(p1, p2);
      end;
    end;

// Prezentujemy wyniki

  for i := 1 to N do
    if i = p1 then
      write('<', d[i]:2, '>')
    else if i = p2 then
      write('|', d[i]:2, '|')
    else
      write(' ', d[i]:2, ' ');
  writeln;
  writeln('w1 =', w1:3, ' na pozycji ', p1:3);
  writeln('w2 =', w2:3, ' na pozycji ', p2:3);

// Gotowe

  writeln;
  writeln('Nacisnij klawisz Enter...');
  readln;
end.

// Wyszukiwanie drugiego największego elementu
//---------------------------------------------
// (C)2006 mgr Jerzy Wałaszek  I LO w Tarnowie
//---------------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Procedura wymienia zawartość dwóch zmiennych
// przekazanych jako parametry
//---------------------------------------------
void Zamien(int &a, int &b)
{
  int x;

  x = a; a = b; b = x;
}


int main(void)
{
  const int N = 100;  // Liczba elementów w zbiorze
  const int M =  99;  // Maksymalna wartość elementu

  int d[N],i,p1,p2,w1,w2;

  cout << "Wyszukiwanie drugiego najwiekszego elementu\n"
          "-------------------------------------------\n"
          "(C)2006 mgr Jerzy Walaszek  I LO w Tarnowie\n\n";

// Generujemy zbiór pseudolosowy

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

// Szukamy elementu

  w1 = d[N - 1]; p1 = N - 1; w2 = d[N - 2]; p2 = N - 2;
  if(w2 > w1)
  {
    Zamien(w1, w2); Zamien(p1, p2);
  }
  for(i = N - 3; i >= 0; i--)
    if(d[i] > w2)
    {
      w2 = d[i]; p2 = i;
      if(w2 > w1)
      {
        Zamien(w1, w2); Zamien(p1, p2);
      }
    }

// Prezentujemy wyniki

  for(i = 0; i < N; i++)
    if(i == p1)      cout << "<" << setw(2) << d[i] << ">";
    else if(i == p2) cout << "|" << setw(2) << d[i] << "|";
    else             cout << " " << setw(2) << d[i] << " ";
  cout << endl;
  cout << "w1 =" << setw(3) << w1 << " na pozycji " << setw(2) << p1 << endl;
  cout << "w2 =" << setw(3) << w2 << " na pozycji " << setw(2) << p2 << endl;

// Gotowe

  cout << endl;
  system("PAUSE"); return 0;
}

' Wyszukiwanie drugiego największego elementu
'---------------------------------------------
' (C)2006 mgr Jerzy Wałaszek  I LO w Tarnowie
'---------------------------------------------

Module Module1

  Sub Main()
    Const N = 100  ' Liczba elementów w zbiorze
    Const M = 99  ' Maksymalna wartość elementu

    Dim d(N), i, p1, p2, w1, w2, tmp As Integer

    Console.WriteLine("Wyszukiwanie drugiego największego elementu")
    Console.WriteLine("-------------------------------------------")
    Console.WriteLine("(C)2006 mgr Jerzy Wałaszek  I LO w Tarnowie")
    Console.WriteLine()

    ' Generujemy zbiór pseudolosowy

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

    ' Szukamy elementu

    w1 = d(N) : p1 = N : w2 = d(N - 1) : p2 = N - 1
    If w2 > w1 Then
      tmp = w1 : w1 = w2 : w2 = tmp
      tmp = p1 : p1 = p2 : p2 = tmp
    End If
    For i = N - 2 To 1 Step -1
      If d(i) > w2 Then
        w2 = d(i) : p2 = i
        If w2 > w1 Then
          tmp = w1 : w1 = w2 : w2 = tmp
          tmp = p1 : p1 = p2 : p2 = tmp
        End If
      End If
    Next

    ' Prezentujemy wyniki

    For i = 1 To N
      If i = p1 Then
        Console.Write("<{0,2}>", d(i))
      ElseIf i = p2 Then
        Console.Write("|{0,2}|", d(i))
      Else
        Console.Write(" {0,2} ", d(i))
      End If
    Next
    Console.WriteLine()
    Console.WriteLine("w1 = {0,2} na pozycji {1,3}", w1, p1)
    Console.WriteLine("w2 = {0,2} na pozycji {1,3}", w2, p2)

    ' Gotowe

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

  End Sub

End Module

# -*- coding: cp1250 -*-
# Wyszukiwanie drugiego największego elementu
#---------------------------------------------
# (C)2006 mgr Jerzy Wałaszek  I LO w Tarnowie
#---------------------------------------------

import random

N = 100  # Liczba elementów w zbiorze
M =  99  # Maksymalna wartość elementu

d = []

print "Wyszukiwanie drugiego najwiekszego elementu"
print "-------------------------------------------"
print "(C)2006 mgr Jerzy Walaszek  I LO w Tarnowie"
print

# Generujemy zbiór pseudolosowy

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

# Szukamy elementu

w1, p1 = d[N - 1], N - 1
w2, p2 = d[N - 2], N - 2
if w2 > w1:
  w1, w2 = w2, w1
  p1, p2 = p2, p1
for i in range(N - 3, -1, -1):
  if d[i] > w2:
    w2, p2 = d[i], i
    if w2 > w1:
      w1, w2 = w2, w1
      p1, p2 = p2, p1

# Prezentujemy wyniki

for i in range(N):
  if   i == p1: print "<%2d>" % d[i],
  elif i == p2: print "|%2d|" % d[i],
  else:         print " %2d " % d[i],
print
print
print "w1 = %2d na pozycji %2d" % (w1, p1)
print "w2 = %2d na pozycji %2d" % (w2, p2)

# Gotowe

print
raw_input("Nacisnij 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="frmSearch2B">
        <h4 id="out_t0" style="text-align: center">
          Wyszukiwanie drugiego największego elementu
        </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>

// Wyszukiwanie drugiego największego elementu
//---------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//---------------------------------------------

function main()
{
  var N = 100; // Liczba elementów w zbiorze
  var M =  99; // Maksymalna wartość elementu

  var d = new Array(N);
  var i,p1,p2,w1,w2,x;

// Generujemy zbiór pseudolosowy

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

// Szukamy elementu

  w1 = d[N - 1]; p1 = N - 1; w2 = d[N - 2]; p2 = N - 2;
  if(w2 > w1)
  {
    x = w1; w1 = w2; w2 = x;
    x = p1; p1 = p2; p2 = x;
  }
  for(i = N - 3; i >= 0; i--)
  if(d[i] > w2)
  {
    w2 = d[i]; p2 = i;
    if(w2 > w1)
    {
      x = w1; w1 = w2; w2 = x;
      x = p1; p1 = p2; p2 = x;
    }
  }

// Prezentujemy wyniki

  t = "";
  for(i = 0; i < N; i++)
  if(i == p1)      t += " <b><font color=red>&lt;" + d[i] + "&gt;</font></b>";
  else if(i == p2) t += " <b><font color=blue>|" + d[i] + "|</font></b>";
  else             t += " &nbsp;" + d[i] + "&nbsp;";
  t += "<br><br>";
  t += "<b><font color=red>w1 = " + w1 + " na pozycji " + p1 + "</font></b><br>";
  t += "<b><font color=blue>w2 = " + w2 + " na pozycji " + p2 + "</font></b>";

// 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