Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Szybkie wyszukiwanie k-tego największego elementu

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

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 ZL i ZP (lewy i prawy). W podzbiorze ZP powinny znaleźć się elementy o wartościach nie większych od v. Z kolei w podzbiorze ZP powinny być elementy o wartościach nie mniejszych od v. Sam element v musi być pierwszym elementem podzbioru ZP. 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 ZL lub ZP, w którym występuje pozycja (n-k)-ta i całą procedurę powtarzamy aż do znalezienia k-tego największego elementu.

Podział zbioru na dwie partycje

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:

ip – przechowuje indeks pierwszego elementu podzbioru – początek
ik – przechowuje indeks ostatniego elementu podzbioru – koniec

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

ip = 0
ik = 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]
ip   ik

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

  1. Jako pierwszy element partycji, v ← Z[ip].
  2. Jako ostatni element partycji, v ← Z[ik].
  3. Jako element środkowy partycji, v ← Z[(ip + ik) shr 1].
  4. Jako element o losowym indeksie,
    v ← Z[ip+losowe(ik-ip+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.
ip : indeks pierwszego elementu partycji, ip ∈ C.
ik : indeks końcowego elementu partycji, ik ∈ C.

Wyjście:

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

Zmienne pomocnicze:

v : wartość elementu zwrotnego.
i, j : indeksy w tablicy Z. i, j ∈ C.
Lista kroków funkcji Dziel_na_partycje(Z, ip, ik):
K01: v ← Z[ip]             ; zapamiętujemy wartość elementu zwrotnego
K02: i ← ip                 ; indeksem i będziemy szukali elementów ≥ v
K03: j ← ik + 1            ; indeksem j będziemy szukali elementów ≤ v
K04: Dopóki i < j:         ; w pętli elementy większe umieszczamy w ZP,
     wykonuj kroki K05…K09 ; a mniejsze w ZL
K05:   i ← i + 1           ; przesuwamy się na następną pozycję w ZL
K06:   Jeśli Z[i] < v,     ; szukamy elementu, który nie należy do ZL
       to idź do kroku K05
K07:   j ← j - 1           ; przesuwamy się na poprzednią pozycję w ZP
K08:   Jeśli Z[j] > v,     ; szukamy elementu, który nie należy do ZP
       to idź do kroku K07
K09:   Jeśli i < j,        ; znalezione elementy zamieniamy miejscami
       to Z[i] ↔ Z[j]
K10: Z[ip] ← 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
Z = [] # Tablica

# Przygotowujemy tablicę Z[]

for i in range(N):
    Z.append(random.randrange(1000))

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

Podział zbioru Z na dwie partycje wg pierwszego elementu
(C)2020 mgr Jerzy Wałaszek

…


Na początek:  podrozdziału   strony 

Wyszukiwanie szybkie

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.

Zmienne pomocnicze:

ip : indeks początku partycji, ip ∈ C.
ik : indeks końca partycji, ik ∈ C.
pv : zawiera pozycję elementu zwrotnego.
Dziel_na_partycje(Z, ip, ik) : funkcja dzieląca na dwie partycje wg elementu zwrotnego. Funkcja opisana powyżej.

Lista kroków:

K01: ip ← 0 ; startowa partycja obejmuje cały zbiór Z
K02: ik ← n - 1
K03: pv ← Dziel_na_partycje(Z,ip,ik) ; dokonujemy podziału
                                     ; na dwie partycje ZL i ZP
K04: Jeśli pv = n - k,               ; sprawdzamy, czy znaleźliśmy
     to zakończ z wynikiem Z[pv]     ; poszukiwany element
K05: Jeśli n - k < pv,               ; jeśli nie, to w zależności
     idź do kroku K08                ; od pozycji elementu zwrotnego
K06: ip ← pv + 1                     ; elementu będziemy szukać w ZP
K07: Idź do kroku K03                ; lub
K08: ik ← pv - 1                     ; elementu będziemy szukać w ZL
K09: 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 podany 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;
  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 podany 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 podany 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 = []
for i in range(N):
    Z.append(random.randrange(1000))

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

Szybkie wyszukiwanie k-tego największego elementu
(C)2020 mgr Jerzy Wałaszek

…


Na początek:  podrozdziału   strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.