Wyszukiwanie k-tego największego elementu zbioru

Zadanie polega na wyszukaniu w tablicy T elementu v, od którego w tej tablicy jest dokładnie k - 1 elementów większych. Czyli element v jest k-tym największym elementem w tablicy T. 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 T wybieramy dowolny element. Oznaczmy go przez v i nazwijmy elementem zwrotnym (ang. pivot). Następnie dokonujemy podziału zbioru T na dwa podzbiory TL i TP (lewy i prawy). W podzbiorze TP powinny znaleźć się elementy o wartościach nie większych od v. Z kolei w podzbiorze TP powinny być elementy o wartościach nie mniejszych od v. Sam element v musi być pierwszym elementem podzbioru TP. Po takim podziale sprawdzamy, czy v jest (n - k)-tym elementem zbioru T. 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 TL lub TP, 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 T będziemy odwzorowywali w tablicy n-elementowej T[ ], 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 T, zatem zmienne te przyjmują odpowiednio wartości:

 

ip = 0
ik = n - 1, gdzie n jest liczbą elementów tablicy T[ ]

 

Odwzorowanie zbioru T w tablicy T[ ]
 T[0]   T[1]   T[2]   T[3]    ...     ...     ...     ...   T[n-3] T[n-2] T[n-1]
ip   ik

 

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

  1. Jako pierwszy element partycji, vT[ip]

  2. Jako ostatni element partycji, vT[ik]

  3. Jako element środkowy partycji, vT[(ip + ik) / 2]

  4. Jako element o losowym indeksie, vT[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
T[ ]  -  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, ipC
ik  - indeks końcowego elementu partycji, ikC
Wyjście:

j - pozycja elementu zwrotnego w T[ ]. Element ten dzieli partycję wejściową na dwie partycje:


    { T[ip] ... T[j - 1] } - elementy mniejsze lub równe v - podzbiór TL
     
{ T[j] ... T[ik] } - elementy większe lub równe v - podzbiór TP

Zmienne pomocnicze:
v  -  wartość elementu zwrotnego
i,j  - indeksy w tablicy T[ ], i,jC

 

Lista kroków
Krok 1: vT[ip] ; zapamiętujemy wartość elementu zwrotnego
Krok 2: iip ; indeksem i będziemy szukali elementów ≥ v
Krok 3: jik + 1 ; indeksem j będziemy szukali elementów ≤ v
Krok 4: Jeśli ij, idź do kroku 11 ; w pętli elementy większe umieszczamy w ZP, a mniejsze w ZL
Krok 5: ii + 1 ; przesuwamy się na następną pozycję w ZL
Krok 6: Jeśli T[i] < v, to idź do kroku 5 ; szukamy elementu, który nie należy do ZL
Krok 7: jj - 1 ; przesuwamy się na poprzednią pozycję w ZP
Krok 8: Jeśli v < T[j], to idź do kroku 7 ; szukamy elementu, który nie należy do ZP
Krok 9: Jeśli i < j, to wymień T[i] z T[j] ; znalezione elementy zamieniamy ze sobą
Krok 10: Idź do kroku 4 ; kontynuujemy pętlę
Krok 11: T[ip] ← T[j] ; zwalniamy pozycję elementu zwrotnego
Krok 12: T[j] ← v ; na zwolnionej pozycji umieszczamy element zwrotny
Krok 13: Zakończ ; kończymy, j zawiera pozycję elementu zwrotnego

 

Przykładowe dane dla programu

Pierwsza liczba określa liczbę elementów n. Następne n liczb całkowitych jest zawartością zbioru. Zbiór jest dzielony na dwie partycje względem pierwszego elementu. W partycji lewej znajdą się elementy mniejsze lub równe pierwszemu elementowi. W partycji prawej znajdą sie elementy wieksze lub równe pierwszemu elementowi.

15
467 221 187 872 378 621 119 187 982 621 193 532 468 333 518

 

// Podział zbioru na dwie partycje
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

// Funkcja dokonuje podziału na partycje
// względem pierwszego elementu. Zwraca jako wynik
// pozycję elementu pierwszego po podziale
//------------------------------------------------

int podziel(int * T, int ip, int ik)
{
    int v,x,i,j;

    v = T[ip]; i = ip; j = ik + 1;

    while(i < j)
    {
        while(T[++i] < v);
        while(v < T[--j]);
        if(i < j)
        {
            x = T[i]; T[i] = T[j]; T[j] = x;
        }
    }

    T[ip] = T[j]; T[j] = v;

    return j; 
}

int main()
{
    int * T,n,i,p;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n + 1];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // umieszczamy strażnika

    T[n] = 2147483647;

    // dzielimy na partycje

    p = podziel(T, 0, n - 1);

    // wyświetlamy wyniki

    cout << endl << endl;

    for(i = 0; i < n; i++)
    {
        if(i == p) cout << "| ";
        cout << T[i] << " ";
    }

    cout << endl << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 

Wyszukiwanie szybkie

Algorytm szybkiego wyszukiwania k-tego największego elementu

Wejście
n  - liczba elementów w zbiorze T
T[ ]  -  tablica (n+1)-elementowa odwzorowująca zbiór T, w którym poszukujemy k-tego największego elementu. Na pozycji T[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 T, k > 0, kN
Wyjście:

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

Zmienne pomocnicze:
ip  -  indeks początku partycji, ipC
ik  - indeks końca partycji, ikC
pv  - zawiera pozycję elementu zwrotnego

podziel(T[ ],ip,ik) - funkcja dzieląca na dwie partycje wg elementu zwrotnego na pozycji ip.

Lista kroków:
Krok 1: ip ← 0 ; startowa partycja obejmuje cały zbiór T
Krok 2: ik n - 1  
Krok 3: pv ← podziel(T[ ], ip, ik) ; dokonujemy podziału na dwie partycje TL i TP
Krok 4: Jeśli pv = n - k, to idź do kroku 10 ; sprawdzamy, czy znaleźliśmy poszukiwany element
Krok 5: Jeśli pv > n - k to idź do kroku 8 ; jeśli nie, to w zależności od pozycji elementu zwrotnego
Krok 6: ippv + 1 ; elementu będziemy szukać w TP
Krok 7: Idź do kroku 3 ; lub
Krok 8: ikpv - 1 ; elementu będziemy szukać w TL
Krok 9: Idź do kroku 3  
Krok 10: Pisz T[pv] ; wyprowadzamy znaleziony element
Krok 11: Zakończ  

 

Przykładowe dane dla programu

Pierwsza liczba określa k. Druga liczba określa liczbę elementów n. Następne n liczb całkowitych jest zawartością zbioru.

7
30
467 221 187 872 378 621 119 187 982 621 193 532 468 333 518
256 982 342 761 129 481 872 991 120 339 301 491 691 182 571

 

// Szybkie wyszukiwanie k-tego elementu
// (C)2010 I LO w Tarnowie
//-------------------------------------

#include <iostream>

using namespace std;

// Funkcja dokonuje podziału na partycje
// względem pierwszego elementu. Zwraca jako wynik
// pozycję elementu pierwszego po podziale
//------------------------------------------------

int podziel(int * T, int ip, int ik)
{
    int v,x,i,j;

    v = T[ip]; i = ip; j = ik + 1;

    while(i < j)
    {
        while(T[++i] < v);
        while(v < T[--j]);
        if(i < j)
        {
            x = T[i]; T[i] = T[j]; T[j] = x;
        }
    }

    T[ip] = T[j]; T[j] = v;

    return j; 
}

int main()
{
    int * T,n,k,i,ip,ik,pv;

    // odczytujemy k oraz n

    cin >> k >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n + 1];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // umieszczamy strażnika

    T[n] = 2147483647;

    // szukamy k-tego elementu

    ip = 0; ik = n - 1;

    while(true)
    {
        pv = podziel(T, ip, ik);

        if(pv == n - k) break;

        if(pv > n - k) ik = pv - 1;
        else           ip = pv + 1;
    }

    // wyświetlamy wyniki

    cout << "\n\nk = " << k << endl
         << "v = " << T[pv] << endl << endl;

    for(i = 0; i < n; i++)
    {
        if(i == pv) cout << "*";
        cout << T[i] << " ";
    }

    cout << endl << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 

Wyszukiwanie mediany zbioru

Medianą zbioru T nazwiemy wartość v, od której w tym zbiorze jest tyle samo elementów większych lub równych co mniejszych lub równych. Mediana posiada wiele ważnych zastosowań praktycznych w statystyce, grafice, obróbce dźwięku i wielu innych dziedzinach.

Jeśli zbiór T jest posortowany rosnąco, to

Medianę możemy w prosty sposób znaleźć wykorzystując nasz algorytm szybkiego wyszukiwania k-tego największego elementu. Twoim zadaniem jest napisanie odpowiedniego programu.

 



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.