Algorytmy i Struktury Danych - Szybkie wyszukiwanie k-tego największego elementu

SPIS TREŚCI

Tematy pomocnicze

Wbudowane generatory liczb pseudolosowych

Podrozdziały

Podział zbioru na dwie partycje
Wyszukiwanie szybkie

Problem

W zbiorze Z należy wyszukać element, od którego w tym zbiorze jest dokładnie k - 1 elementów większych.

Jeśli nie musimy zachowywać oryginalnej kolejności elementów w zbiorze Z , to istnieje szybki algorytm znajdowania k-tego największego elementu, który posiada oczekiwaną klasę złożoności obliczeniowej równą O(n log n) (liniowo logarytmiczna). Algorytm ten nosi nazwę Szybkiego Wyszukiwania (ang. Quick Select) i został opracowany przez profesora Tony Hoare'a, twórcę jednego z najszybszych algorytmów sortujących – Sortowania Szybkiego (ang. Quick Sort).

Działanie algorytmu Szybkiego Wyszukiwania oparte jest na zasadzie Dziel i Zwyciężaj (ang. Divide and Conquer). Polega ona na rekurencyjnym podziale pierwotnego problemu na problemy prostsze tego samego typu. Podział wykonywany jest dotąd, aż rozwiązanie stanie się oczywiste. Następnie z rozwiązań podproblemów tworzymy rozwiązania na wyższych poziomach aż dojdziemy do rozwiązania problemu pierwotnego

W przypadku Szybkiego Wyszukiwania postępujemy w sposób następujący:

W zbiorze Z wybieramy dowolny element. Oznaczmy go przez v i nazwijmy elementem zwrotnym (ang. pivot). Następnie dokonujemy podziału zbioru Z na dwa podzbiory Z_L i Z_P (lewy i prawy). W podzbiorze Z_P powinny znaleźć się elementy o wartościach nie większych od v. Z kolei w podzbiorze Z_P powinny być elementy o wartościach nie mniejszych od v. Sam element v musi być pierwszym elementem podzbioru Z_P. Po takim podziale sprawdzamy, czy v jest (n-k)-tym elementem zbioru Z. Jeśli tak, to v jest k-tym największym elementem w tym zbiorze. Jeśli nie, to za nowy zbiór do podziału przyjmujemy ten z podzbiorów Z_L lub Z_P, w którym występuje pozycja (n-k)-ta i całą procedurę powtarzamy aż do znalezienia k-tego największego elementu.

Podstawowym problemem w algorytmie Szybkiego Wyszukiwania jest podział zbioru na dwa podzbiory, partycje, o wymaganych własnościach. Ponieważ zbiór Z będziemy odwzorowywali w tablicy n-elementowej Z, to zdefiniujmy dwie zmienne, które będą przechowywały indeksy pierwszego i końcowego elementu podzbioru:

i_p – przechowuje indeks pierwszego elementu podzbioru – początek
i_k – przechowuje indeks ostatniego elementu podzbioru – koniec

Początkowo podzbiór obejmuje cały zbiór Z, zatem zmienne te przyjmują odpowiednio wartości:

i_p = 0
i_k = n-1, 
gdzie n jest liczbą elementów tablicy Z

Odwzorowanie zbioru Z w tablicy Z
Z[0]	Z[1]	Z[2]	Z [3]	…	…	…	…	Z[n-3]	Z[n-2]	Z[n-1]
i_p										i_k

Element zwrotny można wybierać na różne sposoby.

Jako pierwszy element partycji, v ← Z[i_p].
Jako ostatni element partycji, v ← Z[i_k].
Jako element środkowy partycji, v ← Z[(i_p + i_k) shr 1].
Jako element o losowym indeksie,
v ← Z[i_p+losowe(i_k-i_p+1)].

Poniżej podajemy algorytm partycjonowania zbioru wg pierwszego elementu partycji głównej. Jeśli zechcemy partycjonować wg innego elementu zwrotnego, to po prostu wymieniamy wybrany element zwrotny z pierwszym elementem partycji i dalej wykorzystujemy podany poniżej algorytm.

Algorytm partycjonowania zbioru wg pierwszego elementu

Wejście:

Z : tablica, której podzbiór partycjonujemy. Za ostatnim elementem partycji należy umieścić wartownika o wartości większej od każdego elementu partycji.
i_p : indeks pierwszego elementu partycji, i_p ∈ C.
i_k : indeks końcowego elementu partycji, i_k ∈ C.

Wyjście:

j : pozycja elementu zwrotnego w Z. Element ten dzieli partycję wejściową na dwie partycje:
{Z[i_p]…Z[j-1]} : elementy mniejsze lub równe v – podzbiór Z_L
{Z[j]…Z[i_k]} : elementy większe lub równe v – podzbiór Z_P

Elementy pomocnicze:

v : wartość elementu zwrotnego.
i, j : indeksy w tablicy Z. i, j ∈ C.

Lista kroków funkcji Dziel_na_partycje(Z, i_p, i_k):

K01: v ← Z[i_p] ; zapamiętujemy wartość elementu zwrotnego
K02: i ← i_p; indeksem i będziemy szukali elementów ≥ v
K03: j ← i_k+1 ; indeksem j będziemy szukali elementów ≤ v
K04: Dopóki i < j: ; w pętli elementy większe umieszczamy w Z_P, 
     wykonuj kroki K05…K09 ; a mniejsze w Z_LK05:   i ← i+1 ; przesuwamy się na następną pozycję w Z_LK06:   Jeśli Z[i] < v, ; szukamy elementu, który nie należy do Z_L
       to idź do kroku K05
K07:   j ← j-1 ; przesuwamy się na poprzednią pozycję w Z_PK08:   Jeśli Z[j] > v, ; szukamy elementu, który nie należy do Z_P
       to idź do kroku K07
K09:   Jeśli i < j, ; znalezione elementy zamieniamy miejscami
       to Z[i] ↔ Z[j]
K10: Z[i_p] ← Z[j] ; zwalniamy pozycję elementu zwrotnego
K11: Z[j] ← v ; na zwolnionej pozycji umieszczamy element zwrotny
K12: Zakończ z wynikiem j ; kończymy zwracając pozycję elementu zwrotnego

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ę 20 elementową Z liczbami pseudolosowymi z zakresu od 0 do 999. Następnie dokonuje partycjonowania tablicy wg pierwszego elementu. Wyświetla zawartość tablicy Z z zaznaczeniem punktu podziałowego.

Pascal

// Podział zbioru na dwie partycje
// Data:   17.05.2008
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------

program prg;

const N = 20;

var
  Z : array [0..N] of integer;
  i, j, v, x : integer;

begin
  randomize;

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

  // Na końcu Z[] umieszczamy wartownika
  Z[N] := 1000;

  // Wyświetlamy Z[] przed podziałem
  for i := 0 to N-1 do
    write(Z[i]:4);
  writeln;

  // Dzielimy Z[] na dwie partycje
  v := Z[0]; i := 0; j := N;
  while i < j do
  begin
    repeat inc(i); until Z[i] >= v;
    repeat dec(j); until Z[j] <= v;
    if i < j then
    begin
      x := Z[i];
      Z[i] := Z[j];
      Z[j] := x;
    end;
  end;
  Z[0] := Z[j];
  Z[j] := v;

  // Wyświetlamy Z[] po podziale
  for i := 0 to N-1 do
    if i = j then
      write('|---')
    else
      write('----');

  for i := 0 to N-1 do
    if i = j then
      write('|', Z[i]:3)
    else
      write(Z[i]:4);

  for i := 0 to N-1 do
    if i = j then
      write('|---')
    else
      write('----');

  writeln;
  writeln;
end.

C++

// Podział zbioru na dwie partycje
// Data:   17.05.2008
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 20;

int main()
{
  int Z[N+1], i, j, v;

  srand(time(NULL));

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

  // Na końcu Z[] umieszczamy wartownika
  Z[N] = 1000;

  // Wyświetlamy Z[] przed podziałem
  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl;

  // Dzielimy Z[] na dwie partycje
  v = Z[0]; i = 0; j = N;
  while(i < j)
  {
    while(Z[++i] < v);
    while(Z[--j] > v);
    if(i < j) swap(Z[i], Z[j]);
  }
  Z[0] = Z[j]; Z[j] = v;

  // Wyświetlamy Z[] po podziale
  for(i = 0; i < N; i++)
    cout << (i == j ? "|---": "----");

  for(i = 0; i < N; i++)
    if(i == j)
      cout << "|" << setw(3) << Z[i];
    else
      cout << setw(4) << Z[i];

  for(i = 0; i < N; i++)
    cout << (i == j ? "|---" : "----");
  cout << endl << endl;

  return 0;
}

Basic

' Podział zbioru na dwie partycje
' Data:   17.05.2008
' (C)2020 mgr Jerzy Wałaszek
'--------------------------------

Const N = 20

Dim As Integer Z(N), i, j, v

Randomize

' Przygotowujemy tablicę Z[]
For i = 0 To N-1
  Z(i) = Cint(Rnd*999)
Next

' Na końcu Z[] umieszczamy wartownika
Z(N) = 1000

' Wyświetlamy Z[] przed podziałem
For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print

' Dzielimy Z[] na dwie partycje
v = Z(0): i = 0: j = N
While i < j
  Do: i += 1: Loop Until Z(i) >= v
  Do: j -= 1: Loop Until Z(j) <= v
  If i < j Then Swap Z(i), Z(j)
Wend
Z(0) = Z(j): Z(j) = v

' Wyświetlamy Z[] po podziale
For i = 0 To N-1
  If i = j Then
    Print "|---";
  Else
    Print "----";
  End If
Next
For i = 0 To N-1
  If i = j Then
    Print Using "|###";Z(i);
  Else
    Print Using "####";Z(i);
  End If
Next
For i = 0 To N-1
  If i = j Then
    Print "|---";
  Else
    Print "----";
  End If
Next
Print
Print
End

Python (dodatek)

# Podział zbioru na dwie partycje
# Data:  29.02.2024
# (C)2024 mgr Jerzy Wałaszek
#--------------------------------

import random

N = 20 # Ilość liczb

# Przygotowujemy tablicę Z[]
z = [random.randrange(1000) for i in range(N)]
# Na końcu Z[] umieszczamy wartownika
z.append(1000)
# Wyświetlamy Z[] przed podziałem
for i in range(N):
    print("%4d" % z[i], end="")
print()
print()
# Dzielimy Z[] na dwie partycje
v, i, j = z[0], 0, N
while i < j:
    while True:
        i += 1
        if z[i] >= v: break
    while True:
        j -= 1
        if z[j] <= v: break
    if i < j: z[i], z[j] = z[j], z[i]
z[0], z[j] = z[j], v
# Wyświetlamy Z[] po podziale
for i in range(N):
    if i == j:
        print("|---", end="")
    else:
        print("----", end="")
for i in range(N):
    if i == j:
        print("|%3d" % z[i], end="")
    else:
        print("%4d" % z[i], end="")
for i in range(N):
    if i == j:
        print("|---", end="")
    else:
        print("----", end="")
print()
print()

Wynik:

 382 983   4 321 701 483 706 214 816 904 310 366 408 372 896 583 808 308 774 212

--------------------------------|-----------------------------------------------
 310 212   4 321 308 372 366 214|382 904 816 706 408 483 896 583 808 701 774 983
--------------------------------|-----------------------------------------------

do podrozdziału do strony

Algorytm szybkiego wyszukiwania k-tego największego elementu

Wejście:

n : liczba elementów w zbiorze Z.
Z : tablica (n+1)-elementowa odwzorowująca zbiór Z, w którym poszukujemy k-tego największego elementu. Na pozycji Z[n] należy umieścić wartownika o wartości większej od każdego elementu zbioru.
k : określa numer porządkowy największego elementu do znalezienia w Z, k > 0, k ∈ N.

Wyjście:

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

Elementy pomocnicze:

i_p : indeks początku partycji, i_p ∈ C.
i_k : indeks końca partycji, i_k ∈ C.
p_v : zawiera pozycję elementu zwrotnego.

Dziel_na_partycje(Z, i_p, i_k) : funkcja dzieląca na dwie partycje wg elementu zwrotnego. Funkcja opisana powyżej.

Lista kroków:

K01: i_p ← 0 ; startowa partycja obejmuje cały zbiór Z
K02: i_k← n-1
K03: p_v ← Dziel_na_partycje(Z, i_p, i_k) ; dokonujemy podziału
                                     ; na dwie partycje Z_L i Z_PK04: Jeśli p_v = n-k, ; sprawdzamy, czy znaleźliśmy
     to zakończ z wynikiem Z[p_v] ; poszukiwany element
K05: Jeśli n-k < p_v, ; jeśli nie, to w zależności
     idź do kroku K08 ; od pozycji elementu zwrotnego
K06: i_p ← p_v+1 ; elementu będziemy szukać w Z_PK07: Idź do kroku K03 ; lub
K08: i_k ← p_v-1 ; elementu będziemy szukać w Z_LK09: Idź do kroku K03

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ę 20 elementową Z liczbami pseudolosowymi z zakresu od 0 do 999, losuje liczbę k z zakresu od 1 do 20, wyszukuje k-ty największy element i na koniec wyświetla k, wyszukany element oraz zawartość tablicy Z zaznaczoną pozycją elementu.

Pascal

// Szybkie wyszukiwanie
// Data:   18.05.2008
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------

program prg;

const N = 20;

// Funkcja dzieli zbiór Z na dwie partycje:
// ZL-elementy mniejsze od elementu zwrotnego
// ZP-elementy większe od elementu zwrotnego
// Zwraca pozycję elementu zwrotnego
//-------------------------------------------
function Dziel_na_partycje(var Z : array of integer;
                               ip, ik : integer)
                               : integer;
var i, v, x : integer;
begin
  v := Z[ip]; i := ip; inc(ik);
  while i < ik do
  begin
    repeat inc(i);  until Z[i]  >= v;
    repeat dec(ik); until Z[ik] <= v;
    if i < ik then
    begin
      x := Z[i]; Z[i] := Z[ik]; Z[ik] := x;
    end;
  end;
  Z[ip] := Z[ik]; Z[ik] := v;
  Dziel_na_partycje := ik;
end;

var
  Z : array [0..N] of integer;
  i, ip, ik, k, pv : integer;

begin
  randomize;

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

  // Na końcu Z[] umieszczamy wartownika
  Z[N] := 1000;

  // Wyświetlamy Z[] przed podziałem
  for i := 0 to N-1 do
    write(Z[i]:4);
  writeln;

  // Losujemy k
  k := random(20)+1;

  // Szukamy k-tego największego elementu
  ip := 0; ik := N-1;
  while true do
  begin
    pv := Dziel_na_partycje(Z, ip, ik);
    if pv = N-k then
      break
    else
      if N-k < pv then
        ik := pv-1
      else
        ip := pv+1;
  end;

  // Wyświetlamy k i Z[N-k]
  writeln(' k = ', k, 
          ', k-ty max element = ', Z[N-k]);
  writeln;

  // Wyświetlamy Z[] po podziale
  for i := 0 to N-1 do
    write(Z[i]:4);
  for i := 0 to pv-1 do
    write('    ');
  writeln(' ---');
  writeln;
end.

C++

// Szybkie wyszukiwanie
// Data:   18.05.2008
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 20;

// Funkcja dzieli zbiór Z na dwie partycje:
// ZL-elementy mniejsze od elementu zwrotnego
// ZP-elementy większe od elementu zwrotnego
// Zwraca pozycję elementu zwrotnego
//-------------------------------------------
int Dziel_na_partycje(int *Z, 
                      int ip, 
                      int ik)
{
  int i, v;

  v = Z[ip]; i = ip; ik++;
  while(i < ik)
  {
    while(Z[++i]  < v);
    while(Z[--ik] > v);
    if(i < ik) swap(Z[i], Z[ik]);
  }
  Z[ip] = Z[ik]; Z[ik] = v;
  return ik;
}

int main()
{
  int Z[N+1], i, ip, ik, k, pv;

  srand(time(NULL));

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

  // Na końcu Z[] umieszczamy wartownika
  Z[N] = 1000;

  // Wyświetlamy Z[] przed podziałem
  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl;

  // Losujemy k
  k = 1+(rand() % 20);

  // Szukamy k-tego największego elementu
  ip = 0; ik = N-1;
  while(true)
  {
    pv = Dziel_na_partycje(Z, ip, ik);
    if(pv == N-k)
      break;
    else
      if(N-k < pv)
        ik = pv-1;
      else
        ip = pv+1;
  }

  // Wyświetlamy k i Z[N-k]
  cout << "k = " << k
       << ", k-ty max element = " << Z[N-k]
       << endl << endl;

  // Wyświetlamy Z[] po podziale
  for(i = 0; i < N;  i++) cout << setw(4) << Z[i];
  for(i = 0; i < pv; i++) cout << "    ";
  cout << " ---\n\n";
  return 0;
}

Basic

' Szybkie wyszukiwanie
' Data:   18.05.2008
' (C)2020 mgr Jerzy Wałaszek
'--------------------------------

Const N = 20

' Funkcja dzieli zbiór Z na dwie partycje:
' ZL-elementy mniejsze od elementu zwrotnego
' ZP-elementy większe od elementu zwrotnego
' Zwraca pozycję elementu zwrotnego
'-------------------------------------------
Function Dziel_na_partycje(Z() As Integer, _
                            Byval ip As Integer, _
                            Byval ik As Integer) _
                            As Integer
 
  Dim As Integer i, v

  v = Z(ip): i = ip: ik += 1
  While i < ik
    Do: i  += 1: Loop Until Z(i)  >= v
    Do: ik -= 1: Loop Until Z(ik) <= v
    If i < ik Then Swap Z(i), Z(ik)
  Wend
  Z(ip) = Z(ik): Z(ik) = v
  Dziel_na_partycje = ik
End Function

Dim As Integer Z(N), i, ip, ik, k, pv

Randomize

' Przygotowujemy tablicę Z()

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

' Na końcu Z() umieszczamy wartownika

Z(N) = 1000

' Wyświetlamy Z() przed podziałem

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

' Losujemy k

k = Cint(Rnd * 19)+1

' Szukamy k-tego największego elementu

ip = 0: ik = N-1
Do
  pv = Dziel_na_partycje(Z(), ip, ik)
  If pv = N-k  Then Exit Do
  If N-k < pv Then
    ik = pv-1
  Else
    ip = pv+1
  End If
Loop

' Wyświetlamy k i Z(N-k)

Print
Print " k =";k;", k-ty max element =";Z(N-k)
Print

' Wyświetlamy Z() po podziale

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

Python (dodatek)

# Szybkie wyszukiwanie
# Data:   18.05.2008
# (C)2020 mgr Jerzy Wałaszek
#--------------------------------

import random

N = 20


# Funkcja dzieli podany zbiór Z na dwie partycje:
# ZL-elementy mniejsze od elementu zwrotnego
# ZP-elementy większe od elementu zwrotnego
# Zwraca pozycję elementu zwrotnego
#------------------------------------------------
def dziel_na_partycje(z, ip, ik):
    v = z[ip]
    i = ip
    ik += 1
    while i < ik:
        while  True:
            i  += 1
            if z[i] >= v: break
        while True:
            ik -= 1
            if z[ik] <= v: break
        if i < ik:
            z[i], z[ik] = z[ik], z[i]
    z[ip], z[ik] = z[ik], v
    return ik


# Przygotowujemy tablicę Z[]
z = [random.randrange(1000) for i in range(N)]
# Na końcu Z[] umieszczamy wartownika
z.append(1000)
# Wyświetlamy Z[] przed podziałem
for i in range(N):
    print("%4d" % z[i], end="")
print()
# Losujemy k
k = random.randrange(1, 21)
# Szukamy k-tego największego elementu
ip, ik = 0, N-1
while True:
    pv = dziel_na_partycje(z, ip, ik)
    if pv == N-k: break
    if N-k < pv:
        ik = pv-1
    else:
        ip = pv+1
# Wyświetlamy k i Z[N-k]
print()
print(" k =", k, ", k-ty max element =", z[N-k])
print()
# Wyświetlamy Z[] po podziale
for i in range(N):
    print("%4d" % z[i], end="")
for i in range(pv):
    print("    ", end="")
print(" ---")
print()

Wynik:

 332 996 106 811 623 676 710 856 424 828  61 541 862 736  38 851 453 687 378 114

 k = 10, k-ty max element = 851

 106 996 332 676 623 811 424 856 710 828 851 541 862 736  38 687 453 378  61 114
                                         ---

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.

Szybkie wyszukiwanie k-tego największego elementu

Problem

Podział zbioru na dwie partycje

Algorytm partycjonowania zbioru wg pierwszego elementu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków funkcji Dziel_na_partycje(Z, ip, ik):

Przykładowe programy

Wyszukiwanie szybkie

Algorytm szybkiego wyszukiwania k-tego największego elementu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Lista kroków funkcji Dziel_na_partycje(Z, i_p, i_k):