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

Zmienne 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, wykonuj kroki K05...K09	w pętli elementy większe umieszczamy w Z_P, a mniejsze w Z_L
K05:	i ← i + 1	przesuwamy się na następną pozycję w Z_L
K06:	Jeśli Z [ i ] < v, to idź do kroku K05	szukamy elementu, który nie należy do Z_L
K07:	j ← j - 1	przesuwamy się na poprzednią pozycję w Z_P
K08:	Jeśli Z [ j ] > v, to idź do kroku K07	szukamy elementu, który nie należy do Z_P
K09:	Jeśli i < j, to Z [ i ] ↔ Z [ j ]	znalezione elementy zamieniamy miejscami
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 <time.h>

using namespace std;

const int N = 20;

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

  srand ( ( unsigned )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 )
    {
      x = Z [ i ]; Z [ i ] = Z [ j ]; Z [ j ] = x;
    }
  }
  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 "----";
Next
For i = 0 To N - 1
  If i = j Then Print Using "|###";Z ( i ); Else Print Using "####";Z ( i );
Next
For i = 0 To N - 1
  If i = j Then Print "|---";: Else Print "----";
Next
Print 
Print
End

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

Na początek: podrozdziału 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.

Zmienne 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_P
K04:	Jeśli p_v = n - k, to zakończ z wynikiem Z [ p_v ]	sprawdzamy, czy znaleźliśmy poszukiwany element
K05:	Jeśli n - k < p_v, idź do kroku K08	jeśli nie, to w zależności od pozycji elementu zwrotnego
K06:	i_p ← p_v + 1	elementu będziemy szukać w Z_P
K07:	Idź do kroku K03	lub
K08:	i_k ← p_v - 1	elementu będziemy szukać w Z_L
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 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 <time.h>

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, x;

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

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

  srand ( ( unsigned )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
Print

' 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
Loop

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

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

Wynik:

673 357 95 402 445 481 444 474 738 913 231   5 421 967 618 238 428 145 905 760

k = 11, k-ty max element = 444

145   5 95 231 238 402 357 421 428 444 445 474 481 618 673 967 913 738 905 760
                                     ---

Na początek: podrozdziału 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:

Zmienne pomocnicze:

Lista kroków funkcji Dziel_na_partycje ( Z, i p, i k ):

Przykładowe programy

Wyszukiwanie szybkie

Algorytm szybkiego wyszukiwania k-tego największego elementu

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

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