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

9d122c961f27217f08c2df3b195e46e1.gif

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.

8656636357e4cd47e3395dbfe8f40121.gif

Dane wejściowe

n - ilość elementów w przeszukiwanym zbiorze.  n 14247a86f7b50ba102885ddf4d312016.gif 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 14247a86f7b50ba102885ddf4d312016.gif N
w2 - wartość drugiego największego elementu zbioru.
p2 - pozycja drugiego największego elementu zbioru. p2 14247a86f7b50ba102885ddf4d312016.gif N

Zmienne pomocnicze

i - zmienna licznikowa pętli. i 14247a86f7b50ba102885ddf4d312016.gif N
66c00e55e9fd1bc35c758f32fc1e0c05.gif
krok 1: w1 32c1bbc9383ce87905e38735db718052.gif d[n];   p1 32c1bbc9383ce87905e38735db718052.gif n;   w2 32c1bbc9383ce87905e38735db718052.gif d[n - 1];   p2 32c1bbc9383ce87905e38735db718052.gif n - 1
krok 2: Jeśli w2 > w1, to  w1 2757fc6436e9df3212f3d01548fd446b.gif w2;   p1 2757fc6436e9df3212f3d01548fd446b.gif 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 32c1bbc9383ce87905e38735db718052.gif d[i];   p2 32c1bbc9383ce87905e38735db718052.gif i;
krok 6:     Jeśli w2 > w1, to  w1 2757fc6436e9df3212f3d01548fd446b.gif w2;   p1 2757fc6436e9df3212f3d01548fd446b.gif p2
krok 7: Zakończ algorytm
951c1d7a8c6858da40d19af1580fbc85.gif

Na początku algorytmu wybieramy ze zbioru dwa ostatnie elementy i umieszczamy je odpowiednio w zmiennych w1 i w2. 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 p1 i p2 zapamiętujemy pozycję tych elementów.

Umawiamy się, iż w1, p1 identyfikuje największy element w zbiorze, a w2 i p2 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 w1 i w2.

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

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

08da2b4d51820a2f7f416596856bf87c.gif
abf0f653213654c6859885e509bf3770.gif    
   
   

56d0518356aadf396daeeb5ef5392ee4.gif

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.

Efekt uruchomienia programu
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...

79e0551bbc33e9eeecf7800661368dc0.gif
// 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.
19f1033872d4d544d95a42dd9916d5ae.gif
// 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;
}
04d7a3a9fa2a05b2cbee99251621f074.gif
' 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
fad41e58a053066834d7680fecd49158.gif
# -*- 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...")
97fb73ed98ca6440e842db028e4bff38.gif
<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