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

using namespace std;

const int N = 40;

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

  srand(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;
      }
    swap(Z[i], Z[minp]);
  }

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

Python (dodatek)

# Wyszukiwanie k-tego największego elementu
# Data:  28.02.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------------------

import random

N = 40

# Inicjujemy tablicę Z[]
z = [random.randrange(1000) for i in range(N)]
# Losujemy k
k = random.randrange(1, 11)
# Wyświetlamy zawartość Z[]
for i in range(N):
    print("%4d" % z[i], end="")
print()
print()
# Sortujemy Z[]
z.sort()
# Wyświetlamy zawartość Z[]
for i in range(N):
    print("%4d" % z[i], end="")
print()
print()
# Wyświetlamy k oraz Z[N-k]
print(k, ":", z[N-k])
print()

Wynik:

  62 335 638 986 466 735 299 438  38 994 344 338 346  13 385 781 150 235 795 530
 578 953 738 104 351 406 917 155 312  54 917 743 365 161 758 437 557 342 596 737

  13  38  54  62 104 150 155 161 235 299 312 335 338 342 344 346 351 365 385 406
 437 438 466 530 557 578 596 638 735 737 738 743 758 781 795 917 917 953 986 994

2 : 986

JavaScript

<html>
  <head>
    <title>
      k-ty największy
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align:
               center;
               background-color:
               #E7E7DA">
          <b>Wyszukiwanie
          k-tego<br>
          największego
          elementu</b><br/>
          &nbsp;&nbsp;
          (C)2026 mgr
          Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

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

function main()
{
  var N = 40;
  var Z = Array(N);
  var c,i,j,k,x,minZ,minp,t;

  // Inicjujemy tablicę Z[]
  for(i = 0; i < N; i++)
    Z[i] = Math.floor(
           Math.random() *
           1000);

  // Losujemy k (1...10)
  k = Math.floor(
      Math.random() * 10) + 1;

  // Wyświetlamy zawartość Z[]

  t = "<pre>";
  c = 0;
  for(i = 0; i < N; i++)
  {
    if(Z[i] < 100) t += " ";
    if(Z[i] <  10) t += " ";
    t += " " + Z[i];
    c++;
    if(c == 10)
    {
      c = 0;
      t += " <br/>";
    }
  }
  t += "<br/>";

  // 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++)
  {
    if(Z[i] < 100) t += " ";
    if(Z[i] <  10) t += " ";
    if(i == N-k)
      t += " <span style=" +
           "'color:Red'><b>" +
           Z[i] + "</b></span>";
    else t += " "+Z[i];
    c++;
    if(c == 10)
    {
      c = 0;
      t += " <br/>";
    }
  }
  t += "</pre>"
  t += k + " : <span style=" +
       "'color:Red'><b>" +
       Z[N - k] +
       "</b></span>";
  // Wyświetlamy k oraz Z[N-k]
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do 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.

Elementy 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: ; inicjujemy tablicę M
     wykonuj krok K02
K02:   M[i] ← najmniejsza liczba całkowita
K03: M[k] ← największa liczba całkowita
K04: Dla i = 0, 1, …, n-1: ; przeglądamy kolejne elementy Z
     wykonuj kroki K05…K10
K05:   x ← Z[i] ; zapamiętujemy i-ty element Z
K06:   j ← -1
K07:   Dopóki x > M[j+1]: ; szukamy miejsca dla x w M
       wykonuj kroki K08…K09
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, ; wstawiamy element x do M
       to M[j] ← x
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 <ctime>

using namespace std;

const int N = 40;

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

  srand(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

Python (dodatek)

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

import random

N = 40
# Inicjujemy tablicę M[]
m = [-1] * 11
# Inicjujemy tablicę Z[]
z = [random.randrange(1000) for i in range(N)]
# Losujemy k
k = random.randrange(5,11)
# Ustawiamy tablicę M[]
m[k] = 1000
# Szukamy k-tego największego elementu
for i in range(N):
    x, j = z[i], -1
    while x > m[j+1]:
        j += 1
        m[j] = m[j+1]
    if j >= 0:
        m[j] = x
# Wypisujemy zawartość tablicy Z[]
for i in range(N):
    print("%4d" % z[i], end="")
print()
print()
# Wypisujemy zawartość tablicy M[]
print("k =", k, ":", end="")
for i in range(k):
    print("%4d" % m[i], end="")
print()
print()

Wynik:

 430 456 314 671 510 519 605 885 831 551 765 827 406 399 313  74 666 426 645  35
 857 146 313 458 972 577 241 159 219 447 174 193 335  55 848 260 457  16 784 983

k = 6 : 831 848 857 885 972 983

do podrozdziału do 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:

Wyjście:

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

Elementy 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: ; zliczamy wartości elementów Z
     wykonuj krok K06
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 <ctime>

using namespace std;

const int N = 400;

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

  srand(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

Python (dodatek)

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

import random

N = 400

# Generujemy zbiór Z[]
z = [random.randrange(-99, 100) for i in range(N)]
# Szukamy jednocześnie min i max
minz, maxz = 100, -100
for i in range(0, N, 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
cnt = [0]*m
#  Zliczamy wartości zbioru Z[]
for i in range(N):
    cnt[z[i]-minz] += 1
# Losujemy k
k = random.randrange(1, 101)
# Szukamy k-tego największego elementu
j, kt = m-1, k
while kt > 0:
    kt -= cnt[j]
    j -= 1
# Wypisujemy tablicę Z[]
for i in range(N):
    print("%4d" % z[i], end="")
print()
print()
# Wypisujemy k oraz
# k-ty największy element
print("k =", k, ": max k-ty =", j+1+minz)
print()

Wynik:

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

k = 92: max k-ty = 62

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

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:

Elementy 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:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy