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

©2020 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 ( 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.

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:

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.

  1. Jako pierwszy element partycji, v  ← Z [ i p  ].
  2. Jako ostatni element partycji, v  ← Z [ i k  ].
  3. Jako element środkowy partycji, v  ← Z [ ( i p  + i k  ) shr 1 ].
  4. 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 pC.
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, jC.
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
--------------------------------|-----------------------------------------------
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, kN

Wyjście:

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

Zmienne pomocnicze:

i p  –  indeks początku partycji, i pC.
i k  – indeks końca partycji, i kC.
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
                                     ---
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
©2020 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.