Szybkie wyszukiwanie k-tego największego elementu


Tematy pokrewne   Podrozdziały
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych
  Podział zbioru na dwie partycje
Wyszukiwanie szybkie

 

Problem

W zbiorze Z 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, vZ[ip]
  2. Jako ostatni element partycji, vZ[ik]
  3. Jako element środkowy partycji, vZ[(ip + ik) shr 1]
  4. Jako element o losowym indeksie, vZ[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

Elementy 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: vZ[ip] ; zapamiętujemy wartość elementu zwrotnego
K02: iip ; indeksem i będziemy szukali elementów ≥ v
K03: jik + 1 ; indeksem j będziemy szukali elementów ≤ v
K04: Dopóki i < j, wykonuj K05...K09 ; w pętli elementy większe umieszczamy w ZP, a mniejsze w ZL
K05:     ii + 1 ; przesuwamy się na następną pozycję w ZL
K06:     Jeśli Z[i] < v, to idź do K05 ; szukamy elementu, który nie należy do ZL
K07:     jj - 1 ; przesuwamy się na poprzednią pozycję w ZP
K08:     Jeśli Z[j] > v, to idź do K07 ; szukamy elementu, który nie należy do ZP
K09:     Jeśli i < j, to Z[i] Z[j] ; znalezione elementy zamieniamy miejscami
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

 

Program

Ważne:

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.

 

Lazarus
// Podział zbioru na dwie partycje
// Data:   17.05.2008
// (C)2012 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.
Code::Blocks
// Podział zbioru na dwie partycje
// Data:   17.05.2008
// (C)2012 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;
}
Free Basic
' Podział zbioru na dwie partycje
' Data:   17.05.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek


...

 

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.

Elementy 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, to zakończ z wynikiem Z[pv] ; sprawdzamy, czy znaleźliśmy poszukiwany element
K05: Jeśli n - k < pv, idź do K08 ; jeśli nie, to w zależności od pozycji elementu zwrotnego
K06: ippv + 1 ; elementu będziemy szukać w ZP
K07: Idź do K03 ; lub
K08: ikpv - 1 ; elementu będziemy szukać w ZL
K09: Idź do K03  

 

Program

Ważne:

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.

 

Lazarus
// Szybkie wyszukiwanie
// Data:   18.05.2008
// (C)2012 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 najwiekszy 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.
Code::Blocks
// Szybkie wyszukiwanie
// Data:   18.05.2008
// (C)2012 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 najwiekszy 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;
}
Free Basic
' Szybkie wyszukiwanie
' Data:   18.05.2008
' (C)2012 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 najwiekszy 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 najwiekszy 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)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.