Algorytmy i Struktury Danych - Wyszukiwanie k-tego największego elementu

Problem wyszukiwania k-tego największego elementu (ang. the k-th largest/greatest element search) można rozwiązać na wiele różnych sposobów. Na przykład tak:

Zbiór Z sortujemy rosnąco. Wtedy elementy ułożą się w kolejności od najmniejszego do największego. Wystarczy zatem zwrócić wartość k-tego od końca elementu.

Ponieważ znajdowanie k-tego największego elementu w zbiorze posortowanym posiada stałą klasę złożoności obliczeniowej O ( 1 ), to faktyczna klasa złożoności całego rozwiązania zależy od zastosowanego algorytmu sortującego zbiór Z. Sortowanie zbioru zmienia wzajemne położenie elementów. Zatem można je stosować tylko wtedy, gdy nie musimy zachowywać oryginalnej struktury zbioru. Jeśli zbiór jest niewielki, to sortowanie może być wykonane na jego duplikacie.

Algorytm wyszukiwania k-tego największego elementu – wersja nr 1

Wejście:

n	–	liczba elementów w tablicy Z, n > 0, n ∈ N.
Z	–	tablica do wyszukania k-tego największego elementu. Indeksy od 0 do n - 1.
k	–	określa k-ty największy element tablicy Z, k > 0, k ≤ n, k ∈ N.

Wyjście:

Wartość k-tego największego elementu w Z.

Lista kroków:

K01:	Posortuj rosnąco tablicę Z	ustalamy kolejność elementów
K02:	Zakończ z wynikiem Z [ n - k ]	zwracamy k-ty największy element

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 40 elementową Z liczbami pseudolosowymi z zakresu od 0 do 999. Następnie losuje k z zakresu od 1 do 10. Wypisuje zawartość tablicy nieposortowanej, sortuje tablicę Z algorytmem sortowania przez wybór (może być inny, ale ten typ sortowania opisaliśmy w tym artykule ), wypisuje zawartość tablicy posortowanej, k oraz k-ty największy element w tablicy.

Pascal

// Wyszukiwanie k-tego największego elementu
// Data:   9.05.2008
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------

program prg;

const N = 40;

var Z : array [ 0..N-1 ] of integer;
    i, j, k, x, minZ, minp : integer;

begin
  randomize;

  // Inicjujemy tablicę Z [ ] 

  for i := 0 to N - 1 do Z [ i ] := random ( 1000 );

  // Losujemy k

  k := random ( 10 ) + 1;


  // Wyświetlamy zawartość Z [ ] 

  for i := 0 to N - 1 do write ( Z [ i ] :4 );
  writeln;
  writeln;

  // Sortujemy Z [ ] 

  for i := 0 to N - 2 do
  begin
    minZ := Z [ i ];
    minp := i;
    for j := i + 1 to N - 1 do
      if Z [ j ] < minZ then
      begin
        minZ := Z [ j ]; minp := j;
      end;
    x := Z [ i ]; Z [ i ] := Z [ minp ]; Z [ minp ] := x;
  end;

  // Wyświetlamy zawartość Z [ ] 

  for i := 0 to N - 1 do write ( Z [ i ] :4 );
  writeln;
  writeln;

  // Wyświetlamy k oraz Z [ N-k ] 

  writeln ( k, ' : ', Z [ N - k ] );
  writeln;
end.

C++

// Wyszukiwanie k-tego największego elementu
// Data:   9.05.2008
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 40;

int main( )
{
  int Z [ N ], i, j, k, x, minZ, minp;

  srand ( ( unsigned )time ( NULL ) );

  // Inicjujemy tablicę Z [ ] 

  for( i = 0; i < N; i++ ) Z [ i ] = rand( ) % 1000;

  // Losujemy k

  k = ( rand( ) % 10 ) + 1;

  // Wyświetlamy zawartość Z [ ] 

  for( i = 0; i < N; i++ ) cout << setw ( 4 ) << Z [ i ];
  cout << endl << endl;

  // Sortujemy Z [ ] 

  for( i = 0; i < N - 1; i++ )
  {
    minZ = Z [ i ];
    minp = i;
    for( j = i + 1; j < N; j++ )
      if( Z [ j ] < minZ )
      {
        minZ = Z [ j ]; minp = j;
      }
    x = Z [ i ]; Z [ i ] = Z [ minp ]; Z [ minp ] = x;
  }

  // Wyświetlamy zawartość Z [ ] 

  for( i = 0; i < N; i++ ) cout << setw ( 4 ) << Z [ i ];
  cout << endl << endl;

  // Wyświetlamy k oraz Z [ N-k ] 

  cout << k << ": " << Z [ N - k ] << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie k-tego największego elementu
' Data:   9.05.2008
' (C)2020 mgr Jerzy Wałaszek
'------------------------------------------

Const N = 40

Dim As Integer Z ( N-1 ), i, j, k, minZ, minp

Randomize

' Inicjujemy tablicę Z [ ] 

For i = 0 To N - 1: Z ( i ) = Cint ( Rnd * 999 ): Next

' Losujemy k

k = Cint ( Rnd * 9 ) + 1


' Wyświetlamy zawartość Z [ ] 

For i = 0 To N - 1: Print Using "####";Z ( i );: Next
Print
Print

' Sortujemy Z [ ] 

For i = 0 To N - 2
  minZ = Z ( i )
  minp = i
  For j = i + 1 To N - 1
    If Z ( j ) < minZ Then
      minZ = Z ( j ): minp = j
    End If
  Next
  Swap Z ( i ), Z ( minp )
Next

' Wyświetlamy zawartość Z [ ] 

For i = 0 To N - 1: Print Using "####";Z ( i );: Next
Print
Print

' Wyświetlamy k oraz Z [ N-k ] 

Print k;": ";Z ( N - k )
Print
End

Wynik:

249 47 995 892 293 567 801 212 308 539 805 516 568 204 316 8 81 347 372 345
758 699 45 855 533 206 274 703 645 95 162 473 406 330 271 177 618 526 247 414

8 45 47 81 95 162 177 204 206 212 247 249 271 274 293 308 316 330 345 347
372 406 414 473 516 526 533 539 567 568 618 645 699 703 758 801 805 855 892 995

7 : 703

Na początek: podrozdziału strony

Sortowanie zbioru jest kosztowne czasowo i zmienia położenie elementów w zbiorze, które czasami musimy zachować. W takim przypadku można zastosować inny algorytm wyszukiwania k-tego największego elementu:

Przygotowujemy pusty zbiór M, w którym będziemy składowali k największych elementów. Przeglądamy zbiór Z i kolejne elementy próbujemy wstawić do M. Element zbioru Z trafia do M wtedy, gdy zbiór M nie jest jeszcze zapełniony lub gdy element zbioru Z jest większy od pierwszego elementu zbioru M. Elementy wstawiamy, tak aby zbiór M był uporządkowany nierosnąco. Gdy zakończymy przeglądanie zbioru Z w pierwszym elemencie zbioru M będzie k-ty największy element zbioru Z.

Wyjaśnienia wymaga sposób działania na zbiorze M. Odwzorujemy go w tablicy ( k + 1 ) elementowej. Do wstawiania elementów wykorzystamy ideę wartowników, którą opisaliśmy w rozdziale o wyszukiwaniu liniowym z wartownikiem. Tablicę M wypełnimy od M [ 0 ] do M [ k - 1 ] najmniejszą liczbą całkowitą – zagwarantuje to wstawianie najmniejszych elementu zbioru Z, jeśli w M jest jeszcze miejsce. Na ostatniej pozycji M [ k ] umieścimy największą liczbę całkowitą – zagwarantuje nam ona, iż wstawiane elementy nie wyjdą poza k - 1 pozycję.

Algorytm wyszukiwania k-tego największego elementu – wersja nr 2

Wejście:

n	–	liczba elementów w tablicy Z, n > 0, n ∈ N.
Z	–	n-elementowa tablica, w której poszukujemy k-tej największej wartości.
k	–	określa numer największej wartości, której szukamy w Z, k > 0, k ≤ n, k ∈ N.

Wyjście:

k-ta największa wartość elementu w tablicy Z. Dodatkowo M [ 0 ]...M [ k - 1 ] tworzy ciąg wartości maksymalnych z tablicy Z.

Zmienne pomocnicze:

M	–	k + 1 elementowa tablica do przechowywania wartości maksymalnych z Z.
i, j	–	indeksy w tablicach Z i M, i, j ∈ C.

Lista kroków:

K01:	Dla i = 0, 1, ..., k - 1: wykonuj krok K02	inicjujemy tablicę M
K02:	M [ i ] ← najmniejsza liczba całkowita
K03:	M [ k ] ← największa liczba całkowita
K04:	Dla i = 0, 1, ..., n-1: wykonuj kroki K05...K10	przeglądamy kolejne elementy Z
K05:	x ← Z [ i ]	zapamiętujemy i-ty element Z
K06:	j ← -1
K07:	Dopóki x > M [ j + 1 ], wykonuj kroki K08...K09	szukamy miejsca dla x w M
K08:	j ← j + 1	przesuwamy się na następną pozycję w M
K09:	M [ j ] ← M [ j + 1 ]	przesuwamy elementy, aby zrobić miejsce dla x
K10:	Jeśli j ≥ 0, to M [ j ] ← x	wstawiamy element x do M
K11:	Zakończ z wynikiem M [ 0 ]	w M [ 0 ] jest k-ty największy element

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 40 elementową Z liczbami pseudolosowymi z zakresu od 0 do 999. Następnie losuje k z zakresu od 5 do 10. Wypisuje zawartość tablicy Z, następnie wyszukuje k-ty największy element opisanym powyżej algorytmem i wypisuje k oraz całą zawartość tablicy M od elementu M [ 0 ] do M [ k - 1 ].

Pascal

// Wyszukiwanie k-tego największego elementu
// Data:   14.05.2008
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------

program prg;

const N = 40;

var Z : array [ 0..N-1 ] of integer;
    M : array [ 0..10 ] of integer;
    i, j, k, x : integer;

begin
  randomize;

  // Inicjujemy tablicę Z [ ] 

  for i := 0 to N - 1 do Z [ i ] := random ( 1000 );

  // Losujemy k

  k := random ( 6 ) + 5;

  // Ustawiamy tablicę M

  for i := 0 to k - 1 do M [ i ] := -1;
  M [ k ] := 1000;

  // Szukamy k-tego największego elementu

  for i := 0 to N - 1 do
  begin
    x := Z [ i ];
    j := -1;
    while x > M [ j+1 ] do
    begin
      inc ( j ); M [ j ] := M [ j+1 ];
    end;
    if j >= 0 then M [ j ] := x;
  end;

  // Wypisujemy zawartość tablicy Z [ ] 

  for i := 0 to N - 1 do write ( Z [ i ] :4 );
  writeln;

  // Wypisujemy zawartość tablicy M

  write ( 'k = ', k, ' : ' );
  for i := 0 to k - 1 do write ( M [ i ] :4 );
  writeln;
  writeln;
end.

C++

// Wyszukiwanie k-tego największego elementu
// Data:   14.05.2008
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 40;

int main( )
{
  int Z [ N ], M [ 11 ], i, j, k, x;

  srand ( ( unsigned )time ( NULL ) );

  // Inicjujemy tablicę Z [ ] 

  for( i = 0; i < N; i++ ) Z [ i ] = rand( ) %  1000;

  // Losujemy k

  k = 5 + ( rand( ) %  6 );

  // Ustawiamy tablicę M

  for( i = 0; i < k; i++ ) M [ i ] = -1;
  M [ k ] = 1000;

  // Szukamy k-tego największego elementu

  for( i = 0; i < N; i++ )
  {
    x = Z [ i ];
    for( j = -1; x > M [ j + 1 ]; )
    {
      j++; M [ j ] = M [ j + 1 ];
    }
    if( j >= 0 ) M [ j ] = x;
  }

  // Wypisujemy zawartość tablicy Z [ ] 

  for( i = 0; i < N; i++ ) cout << setw ( 4 ) << Z [ i ];
  cout << endl;

  // Wypisujemy zawartość tablicy M

  cout << "k = " << k << ": ";
  for( i = 0; i < k; i++ ) cout << setw ( 4 ) << M [ i ];
  cout << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie k-tego największego elementu
' Data:   14.05.2008
' (C)2020 mgr Jerzy Wałaszek
'------------------------------------------

Const N = 40

Dim As Integer Z ( N-1 ), M ( 10 ), i, j, k, x

Randomize

' Inicjujemy tablicę Z [ ] 

For i = 0 To N - 1: Z ( i ) = Cint ( Rnd * 999 ): Next

' Losujemy k

k = Cint ( Rnd * 5 ) + 5

' Ustawiamy tablicę M

For i = 0 To k - 1: M ( i ) = -1: Next
M ( k ) = 1000

' Szukamy k-tego największego elementu

For i = 0 To N - 1
  x = Z ( i )
  j = -1
  While x > M ( j + 1 )
    j += 1: M ( j ) = M ( j + 1 )
  Wend
  If j >= 0 Then M ( j ) = x
Next

' Wypisujemy zawartość tablicy Z [ ] 

For i = 0 To N - 1: Print Using "####";Z ( i );: Next
Print

' Wypisujemy zawartość tablicy M

Print "k = ";k;": ";
For i = 0 To k - 1: Print Using "####";M ( i );: Next
Print
Print
End

Wynik:

779 147 424 546 363 390 95 226 179 440 576 347 15 271 860 362 870 290 476 453
594 382 782 189 369 965 622 44 579 350 968 622 775 924 250 982 7 667 733 149

k = 10 : 733 775 779 782 860 870 924 965 968 982

484 665 40 452 26 296 300 379 206 173 215 696 61 34 120 255 460 332 961 740
123 349 604 435 859 299 189 813 471 593 335 899 976 791 190 209 529 954 437 750

k = 7 : 791 813 859 899 954 961 976

Na początek: podrozdziału strony

Jeśli zbiór Z jest bardzo duży lecz wartości jego elementów tworzą względnie mały przedział liczb całkowitych, to do wyznaczenia k-tego największego elementu można wykorzystać następujące rozwiązanie:

Tworzymy tablicę L posiadającą tyle elementów, ile liczb całkowitych zawiera przedział [ min_Z, max_Z ] (wartość minimalna i maksymalna elementów zbioru Z ). Elementy L zerujemy – będą one pełniły rolę liczników elementów zbioru Z. Teraz przeglądamy zbiór Z od pierwszego do ostatniego elementu i odpowiednio zliczamy napotkane elementy Z w licznikach L. Na koniec przeglądamy liczniki L od ostatniego (odpowiada max_Z ) do pierwszego (odpowiada min_Z ). Ponieważ licznik L [ i ] zawiera informację o tym, ile razy wartość i występuje w Z, to przy każdym kolejnym liczniku odejmujemy jego stan od k. Jeśli k wyzeruje się lub przyjmie wartość ujemną, to poszukiwana wartość jest równa indeksowi licznika, który spowodował tę sytuację.

Klasa złożoności obliczeniowej tak zdefiniowanego algorytmu wynosi O ( n + m ), gdzie n oznacza liczbę elementów w zbiorze Z, a m liczbę ich możliwych wartości. Dodatkowo algorytm wymaga O ( m ) komórek pamięci na przechowanie liczników. Musimy również znać zakres wartości elementów zbioru Z – można tutaj wykorzystać algorytm jednoczesnego wyszukiwania min i max.

Algorytm wyszukiwania k-tego największego elementu – wersja nr 3

Wejście:

n	–	liczba elementów w tablicy Z, n > 0, n ∈ N.
Z	–	n-elementowa tablica, w której poszukujemy k-tej największej wartości.
k	–	określa numer największej wartości, której szukamy w Z, k > 0, k ≤ n, k ∈ N.
min_Z	–	minimalna wartość w Z.
max_Z	–	maksymalna wartość w Z.

Wyjście:

k-ta największa wartość elementu w tablicy Z.

Zmienne pomocnicze:

L	–	tablica liczników. Elementy są liczbami całkowitymi.
i	–	indeksy w tablicach Z i L, i ∈ C.
m	–	liczba wartości elementów Z, m ∈ N.

Lista kroków:

K01:	m ← max_Z - min_Z + 1	przygotowujemy tablicę liczników
K02:	Twórz tablicę L o m elementach
K03:	Dla i = 0, 1, ..., m - 1: wykonuj krok K04
K04:	L [ i ] ← 0	zerujemy liczniki wartości
K05:	Dla i = 0, 1, ..., n - 1: wykonuj krok K06	zliczamy wartości elementów Z
K06:	Zwiększ o 1 element L [ Z [ i ] - min_Z ]
K07:	i ← m - 1	szukamy k-tego największego elementu
K08:	Dopóki k > 0, wykonuj kroki K09...K10
K09:	k ← k - L [ i ]	od k odejmujemy liczbę elementów o wartości i
K10:	i ← i - 1	przechodzimy do niższej wartości
K11:	Zakończ z wynikiem i + 1 + min_Z

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 400 elementową Z liczbami pseudolosowymi z zakresu od -99 do 99. Następnie losuje k z zakresu od 1 do 100. Wypisuje zawartość tablicy Z, znajduje min i max, wyszukuje k-ty największy element opisanym powyżej algorytmem i wypisuje k oraz znaleziony element.

Pascal

// Wyszukiwanie k-tego największego elementu
// Data:   16.05.2008
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------

program prg;

const N = 400;

type Tint = array of integer;

var
  Z : array [ 0..N-1 ] of integer;
  L : Tint;
  i, j, k, kt, m, minZ, maxZ : integer;

begin
  randomize;

  // Generujemy zbiór Z [ ] 

  for i := 0 to N - 1 do Z [ i ] := -99 + random ( 199 );

  // Szukamy jednocześnie min i max

  minZ := 100; maxZ := -100;
  i := 0;
  while i < N do
  begin
    if Z [ i ] > Z [ i+1 ] then
    begin
      if Z [ i ]   > maxZ then maxZ := Z [ i ];
      if Z [ i+1 ] < minZ then minZ := Z [ i+1 ];
    end
    else
    begin
      if Z [ i ]   < minZ then minZ := Z [ i ];
      if Z [ i+1 ] > maxZ then maxZ := Z [ i+1 ];
    end;
    inc ( i, 2 );
  end;

  // Przygotowujemy liczniki

  m := maxZ - minZ + 1;
  setlength ( L, m );
  for i := 0 to m - 1 do L [ i ] := 0;

  //  Zliczamy wartości zbioru Z [ ] 

  for i := 0 to N - 1 do inc ( L [ Z [ i ] - minZ ] );

  // Losujemy k

  k := 1 + random ( 100 );

  // Szukamy k-tego największego elementu

  j := m - 1; kt := k;
  while kt > 0 do
  begin
    dec ( kt, L [ j ] ); dec ( j );
  end;

  // Wypisujemy tablicę Z [ ] 

  for i := 0 to N - 1 do write ( Z [ i ] :4 );
  writeln;

  // Wypisujemy k oraz k-ty największy element

  writeln ( 'k = ', k, ' : max k-ty = ', j + 1 + minZ );
  writeln;

end.

C++

// Wyszukiwanie k-tego największego elementu
// Data:   16.05.2008
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 400;

int main( )
{
  int Z [ N ], * L, i, j, k, kt, m, minZ, maxZ;

  srand ( ( unsigned )time ( NULL ) );

  // Generujemy zbiór Z [ ] 

  for( i = 0; i < N; i++ ) Z [ i ] = -99 + ( rand( ) % 199 );

  // Szukamy jednocześnie min i max

  minZ = 100; maxZ = -100;
  for( i = 0; i < N; i += 2 )
    if( Z [ i ] > Z [ i+1 ] )
    {
      if( Z [ i ]   > maxZ ) maxZ = Z [ i ];
      if( Z [ i+1 ] < minZ ) minZ = Z [ i + 1 ];
    }
    else
    {
      if( Z [ i ]   < minZ ) minZ = Z [ i ];
      if( Z [ i+1 ] > maxZ ) maxZ = Z [ i + 1 ];
    }

  // Przygotowujemy liczniki

  m = maxZ - minZ + 1;
  L = new int [ m ];
  for( i = 0; i < m; i++ ) L [ i ] = 0;

  // Zliczamy wartości zbioru Z [ ] 

  for( i = 0; i < N; i++ ) L [ Z [ i ] - minZ ] ++;

  // Losujemy k

  k = 1 + ( rand( ) % 100 );

  // Szukamy k-tego największego elementu

  for( j = m - 1, kt = k; kt > 0; j-- ) kt -= L [ j ];

  // Wypisujemy tablicę Z [ ] 

  for( i = 0; i < N; i++ ) cout << setw ( 4 ) << Z [ i ];
  cout << endl;

  // Wypisujemy k oraz k-ty największy element

  cout << "k = " << k 
       << ": max k-ty = " << ( j + 1 + minZ )
       << endl << endl;
  delete [ ] L;
  return 0;
}

Basic

' Wyszukiwanie k-tego największego elementu
' Data:   16.05.2008
' (C)2020 mgr Jerzy Wałaszek
'------------------------------------------

Const N = 400

Dim As Integer Z ( N - 1 ), i, j, k, kt, m, minZ, maxZ

Randomize

' Generujemy zbiór Z [ ] 

For i = 0 To N - 1: Z ( i ) = -99 + Cint ( Rnd * 198 ): Next

' Szukamy jednocześnie min i max

minZ = 100: maxZ = -100
i = 0
While i < N
  If Z ( i ) > Z ( i+1 ) Then
    If Z ( i )   > maxZ Then maxZ = Z ( i )
    If Z ( i+1 ) < minZ Then minZ = Z ( i + 1 )
  Else
    If Z ( i )   < minZ Then minZ = Z ( i )
    If Z ( i+1 ) > maxZ Then maxZ = Z ( i + 1 )
  End If
  i += 2
Wend

' Przygotowujemy liczniki

m = maxZ - minZ + 1

Dim As Integer L ( m - 1 )

For i = 0 To m - 1: L ( i ) = 0: Next

'  Zliczamy wartości zbioru Z [ ] 

For i = 0 To N - 1: L ( Z ( i ) - minZ ) += 1: Next

' Losujemy k

k = 1 + Cint ( Rnd * 99 )

' Szukamy k-tego największego elementu

j = m - 1: kt = k
While kt > 0
  kt -= L ( j ): j -= 1
Wend

' Wypisujemy tablicę Z [ ] 

For i = 0 To N - 1: Print Using "####";Z ( i );: Next
Print

' Wypisujemy k oraz k-ty największy element

Print "k =";k;": max k-ty =";j + 1 + minZ
Print
End

Wynik:

75 76 12 -93 -34 -80 -88 12 36 -80 92 84 -93 -46 -2 -51 44 -29 52 -77
83 11 -97 93 12 -42 -2 66 71 38 -33 80 -40 25 44 -15 -33 39 -95 -72
-51 87 -74 88 -8 -85 -98 10 42 36 -82   6 -12 73 -46 40 94   5 84 37
-48 35 61 84 -16 -30 47 -91 -38 -65 53 26 -13 -72 -73 77 -4 -96 -14 54
74 -96 -14 -29 -54 93 58 -8 -65 -26 30 27 -53 -2 67 -8 10   0 -88 -96
18 -48 49 -72 54 -39 -41 44 -99 37 83 32 -57 -60 41 -97 55 23 -13   0
-52 68 -5 20 80 26 -62 -40 53 -56   2 57 -88 -22 -61 50 -73   6 69 62
-88 47 -52 -97 -13 57 -88 -72 90 92 -17 95   2 -64 -52 -59 -21 -52 -5 74
51 -63 -9 -82 -22 -45 65 -4 -94 52 82 77 -86 86 -16 63 -4 47 24 -9
59 48 -94 10 -79   3 -92 -39   7 -72 85 -46   1 -2 -39 -81 -44 -77 -38 -99
-15 88 -34 70 -79 86 31 -11 -29 -57 62 46 -54 -94 -6 -91 -24 83   8 -67
39 48 -77   3 -27 -14 -72 -86   0 -39 -50 -53 -85 87 88 20 46 -27 -69 55
-84 -24 -9 22 -52 92 53 33 -92 -28   0 87 -52 74 76 -26 68 67 -98 -71
49 58 90 30 -84 -42 -41 28 41 -60 89 -4 -89 -55 -59   6 -95 -59 55 42
59   1 54 -55 41   4 -30 40 57 96 -42 -71   9 83 -74 -45 49 59 23 12
-3 48 -50 -73 -36 -54 -9 -6 25   2 42 -12 52 13 60 -40 -31 -63 87 -8
64 -13 -38 -82 -9 45 75 -88 54 -45 39 -14 95 30 11   6 86 -10 36 15
39 93   9 -86 -44 -70 14 -30 -51 70 47   3 -41 -27   9 -89 -48 35 14 13
56   2 17 16 -20 -15 62 29 25 54 86 36 30 29 -95 10 23 41 36 -46
-73 39 32 68 -66 -84 69 80   7 -45 -68 25 29 99 49 52 -91 -38 -88 -58

k = 32 : max k-ty = 83

Na początek: podrozdziału strony

Wyszukiwanie k-tego największego elementu

Problem

Rozwiązanie nr 1

Algorytm wyszukiwania k-tego największego elementu – wersja nr 1

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm wyszukiwania k-tego największego elementu – wersja nr 2

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 3

Algorytm wyszukiwania k-tego największego elementu – wersja nr 3

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy