obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

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 T_L i T_P (lewy i prawy). W podzbiorze T_P powinny znaleźć się elementy o wartościach nie większych od v. Z kolei w podzbiorze T_P powinny być elementy o wartościach nie mniejszych od v. Sam element v musi być pierwszym elementem podzbioru T_P. 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 T_L lub T_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 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:

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 T, zatem zmienne te przyjmują odpowiednio wartości:

i_p = 0
i_k = 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]
i_p										i_k

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

Jako pierwszy element partycji, v ← T[i_p]
Jako ostatni element partycji, v ← T[i_k]
Jako element środkowy partycji, v ← T[(i_p + i_k) / 2]
Jako element o losowym indeksie, v ← T[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

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.
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 T[ ]. Element ten dzieli partycję wejściową na dwie partycje:

{ T[i_p] ... T[j - 1] } - elementy mniejsze lub równe v - podzbiór T_L{ T[j] ... T[i_k] } - elementy większe lub równe v - podzbiór T_P

Zmienne pomocnicze:

v	-	wartość elementu zwrotnego
i,j	-	indeksy w tablicy T[ ], i,j ∈C

Lista kroków

Krok 1:	v ← T[i_p]	; zapamiętujemy wartość elementu zwrotnego
Krok 2:	i ← i_p	; indeksem i będziemy szukali elementów ≥ v
Krok 3:	j ← i_k + 1	; indeksem j będziemy szukali elementów ≤ v
Krok 4:	Jeśli i ≥ j, idź do kroku 11	; w pętli elementy większe umieszczamy w Z_P, a mniejsze w Z_L
Krok 5:	i ← i + 1	; przesuwamy się na następną pozycję w Z_L
Krok 6:	Jeśli T[i] < v, to idź do kroku 5	; szukamy elementu, który nie należy do Z_L
Krok 7:	j ← j - 1	; przesuwamy się na poprzednią pozycję w Z_P
Krok 8:	Jeśli v < T[j], to idź do kroku 7	; szukamy elementu, który nie należy do Z_P
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[i_p] ← 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, k ∈N

Wyjście:

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

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

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

Lista kroków:

Krok 1:	i_p ← 0	; startowa partycja obejmuje cały zbiór T
Krok 2:	i_k← n - 1
Krok 3:	p_v ← podziel(T[ ], i_p, i_k)	; dokonujemy podziału na dwie partycje T_L i T_P
Krok 4:	Jeśli p_v = n - k, to idź do kroku 10	; sprawdzamy, czy znaleźliśmy poszukiwany element
Krok 5:	Jeśli p_v > n - k to idź do kroku 8	; jeśli nie, to w zależności od pozycji elementu zwrotnego
Krok 6:	i_p ← p_v + 1	; elementu będziemy szukać w T_P
Krok 7:	Idź do kroku 3	; lub
Krok 8:	i_k ← p_v - 1	; elementu będziemy szukać w T_L
Krok 9:	Idź do kroku 3
Krok 10:	Pisz T[p_v]	; 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

przy nieparzystej liczbie elementów n > 1 mediana jest elementem środkowym T[ⁿ/₂] (indeksy elementów rozpoczynają się od 0).
Na przykład dla zbioru T = {1,3,5,8,9} medianą jest element 5 - poprzedzają go dwa elementy 1 i 3 oraz wyprzedzają dwa elementy 8 i 9.
przy parzystej liczbie elementów n > 1 mediana jest średnią arytmetyczną dwóch środkowych elementów T[ⁿ/₂-1] i T[ⁿ/₂].
Na przykład dla zbioru T = {1,3,5,8,9,9} mediana jest równa (5 + 8) / 2 = 6,5. Od tej wartości jest dokładnie tyle samo elementów mniejszych (1,3,5) co większych (8,9,9).
Istnieją również pojęcia dolnej mediany (ang. lower median) i górnej mediany (upper median), które w tym przypadku oznaczają odpowiednio element T[ⁿ/₂-1] i T[ⁿ/₂] w ciągu uporządkowanym o parzystej liczbie elementów.

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.

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe