Klasa II - Wyszukiwanie k-tego największego elementu w zbiorze

Proste rozwiązanie tego problemu jest następujące:

Przygotowujemy pusty zbiór M, w którym będziemy składowali k największych elementów. Przeglądamy zbiór T i kolejne elementy próbujemy wstawić do M. Element zbioru T trafia do M wtedy, gdy zbiór M nie jest jeszcze zapełniony lub gdy element zbioru T jest większy od pierwszego elementu zbioru M. Elementy wstawiamy, tak aby zbiór M był uporządkowany nierosnąco. Gdy zakończymy przeglądanie zbioru T w pierwszym elemencie zbioru M będzie k-ty największy element zbioru T.

Wyjaśnienia wymaga sposób działania na zbiorze M. Odwzorujemy go w tablicy (k + 1) elementowej. Do wstawiania elementów wykorzystamy ideę wartowników, którą opisaliśmy w rozdziale o wyszukiwaniu liniowym z wartownikiem. Tablicę M wypełnimy od M[0] do M[k-1] najmniejszą liczbą całkowitą – zagwarantuje to wstawianie najmniejszych elementu zbioru Z, jeśli w M jest jeszcze miejsce. Na ostatniej pozycji M[k] umieścimy największą liczbę całkowitą – zagwarantuje nam ona, iż wstawiane elementy nie wyjdą poza k-1 pozycję.

Algorytm wyszukiwania k-tego największego elementu – wersja nr 1

Wejście

n	–	liczba elementów w tablicy T, n > 0, n N
T	–	n-elementowa tablica, w której poszukujemy k-tej największej wartości
k	–	określa numer największej wartości, której szukamy w T, k > 0, k ≤ n, k N

Wyjście:

k-ta największa wartość elementu w tablicy T. Dodatkowo M[0]...M[k-1] tworzy ciąg wartości maksymalnych z tablicy T.

Elementy pomocnicze:

M	–	k + 1 elementowa tablica do przechowywania wartości maksymalnych z T
i,j	–	indeksy w tablicach T i M, i,j C

Lista kroków:

K01:	Dla i = 0,1,...,k - 1, wykonuj K02	; inicjujemy tablicę M
K02:	M[i] ← najmniejsza liczba całkowita
K03:	M[k] ← największa liczba całkowita
K04:	Dla i = 0,1,...,n-1 wykonuj K05...K10	; przeglądamy kolejne elementy T
K05:	x ← T[i]	; zapamiętujemy i-ty element T
K06:	j ← -1
K07:	Dopóki x > M[j+1] wykonuj K08...K09	; szukamy miejsca dla x w M
K08:	j ← j + 1	; przesuwamy się na następną pozycję w M
K09:	M[j] ← M[j+1]	; przesuwamy elementy, aby zrobić miejsce dla x
K10:	Jeśli j ≥ 0, to M[j] ← x	; wstawiamy element x do M
K11:	Zakończ z wynikiem M[0]	; w M[0] jest k-ty największy element

Jeśli zbiór T jest bardzo duży lecz wartości jego elementów tworzą względnie mały przedział liczb całkowitych, to do wyznaczenia k-tego największego elementu można wykorzystać następujące rozwiązanie:

Tworzymy tablicę L posiadającą tyle elementów, ile liczb całkowitych zawiera przedział <min_T,max_T> (wartość minimalna i maksymalna elementów zbioru T). Elementy L zerujemy – będą one pełniły rolę liczników elementów zbioru T. Teraz przeglądamy zbiór T od pierwszego do ostatniego elementu i odpowiednio zliczamy napotkane elementy T w licznikach L. Na koniec przeglądamy liczniki L od ostatniego (odpowiada max_T) do pierwszego (odpowiada min_T). Ponieważ licznik L[i] zawiera informację o tym, ile razy wartość i występuje w T, to przy każdym kolejnym liczniku odejmujemy jego stan od k. Jeśli k wyzeruje się lub przyjmie wartość ujemną, to poszukiwana wartość jest równa indeksowi licznika, który spowodował tę sytuację.

Klasa złożoności obliczeniowej tak zdefiniowanego algorytmu wynosi O(n + m), gdzie n oznacza liczbę elementów w zbiorze T, a m liczbę ich możliwych wartości. Dodatkowo algorytm wymaga O(m) komórek pamięci na przechowanie liczników. Musimy również znać zakres wartości elementów zbioru T – można tutaj wykorzystać algorytm jednoczesnego wyszukiwania min i max.

Algorytm wyszukiwania k-tego największego elementu – wersja nr 2

Wejście

n	–	liczba elementów w tablicy T, n > 0, n N
T	–	n-elementowa tablica, w której poszukujemy k-tej największej wartości
k	–	określa numer największej wartości, której szukamy w T, k > 0, k ≤ n, k N
min_T	–	minimalna wartość w T
max_T	–	maksymalna wartość w T

Wyjście:

k-ta największa wartość elementu w tablicy T.

Elementy pomocnicze:

L	–	tablica liczników. Elementy są liczbami całkowitymi.
i	–	indeksy w tablicach T i L, i C
m	–	liczba wartości elementów T, m N

Lista kroków:

K01:	m ← max_T - min_T + 1	; przygotowujemy tablicę liczników
K02:	Twórz L o m elementach
K03:	Dla i = 0,1,...,m-1 wykonuj K04
K04:	L[i] ← 0	; zerujemy liczniki wartości
K05:	Dla i = 0,1,...,n-1 wykonuj K06	; zliczamy wartości elementów T
K06:	Zwiększ o 1 L[T[i] - min_T]
K07:	i ← m - 1	; szukamy k-tego największego elementu
K08:	Dopóki k > 0 wykonuj K09...K10
K09:	k ← k - L[i]	; od k odejmujemy liczbę elementów o wartości i
K10:	i ← i - 1	; przechodzimy do niższej wartości
K11:	Zakończ z wynikiem i + 1 + min_T

Przykładowe dane do ćwiczeń

Pierwsza liczba to n – ilość elementów w tablicy T. Druga liczba to k – numer największej wartości. Następne n liczb to zawartość tablicy T.

40 10
779 147 424 546 363 390 95 226 179 440 576 347 15 271 860 362 870 290 476 453
594 382 782 189 369 965 622 44 579 350 968 622 775 924 250 982 7 667 733 149
484 665 40 452 26 296 300 379 206 173 215 696 61 34 120 255 460 332 961 740
123 349 604 435 859 299 189 813 471 593 335 899 976 791 190 209 529 954 437 750

Szybkie wyszukiwanie k-tego największego elementu

Jeśli nie musimy zachowywać oryginalnej kolejności elementów w zbiorze T, 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'ego 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) shr 1]
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

Funkcja Dziel_na_partycje(T,i_p,i_k)

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

Elementy pomocnicze:

v	–	wartość elementu zwrotnego
i,j	–	indeksy w tablicy T, i,j C

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

K01:	v ← T[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 K05...K09	; w pętli elementy większe umieszczamy w T_P, a mniejsze w T_L
K05:	i ← i + 1	; przesuwamy się na następną pozycję w T_L
K06:	Jeśli T[i] < v, to idź do K05	; szukamy elementu, który nie należy do T_L
K07:	j ← j - 1	; przesuwamy się na poprzednią pozycję w T_P
K08:	Jeśli T[j] > v, to idź do K07	; szukamy elementu, który nie należy do T_P
K09:	Jeśli i < j, to T[i] ↔ T[j]	; znalezione elementy zamieniamy miejscami
K10:	T[i_p] ← T[j]	; zwalniamy pozycję elementu zwrotnego
K11:	T[j] ← v	; na zwolnionej pozycji umieszczamy element zwrotny
K12:	Zakończ z wynikiem j	; kończymy zwracając pozycję elementu zwrotnego

Algorytm szybkiego wyszukiwania k-tego największego elementu - wersja nr 3

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.

Elementy 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(T,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 T
K02:	i_k← n - 1
K03:	p_v ← Dziel_na_partycje(T,i_p,i_k)	; dokonujemy podziału na dwie partycje T_L i T_P
K04:	Jeśli p_v = n - k, to zakończ z wynikiem T[p_v]	; sprawdzamy, czy znaleźliśmy poszukiwany element
K05:	Jeśli n - k < p_v, idź do K08	; jeśli nie, to w zależności od pozycji elementu zwrotnego
K06:	i_p ← p_v + 1	; elementu będziemy szukać w T_P
K07:	Idź do K03	; lub
K08:	i_k ← p_v - 1	; elementu będziemy szukać w T_L
K09:	Idź do K03

Informatyka dla klas II - Wyszukiwanie k-tego największego elementu w zbiorze

Algorytm wyszukiwania k-tego największego elementu – wersja nr 1

Wejście

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm wyszukiwania k-tego największego elementu – wersja nr 2

Wejście

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe dane do ćwiczeń

Szybkie wyszukiwanie k-tego największego elementu

Podział zbioru na dwie partycje

Algorytm partycjonowania zbioru wg pierwszego elementu

Funkcja Dziel_na_partycje(T,ip,ik)

Wejście

Wyjście:

Elementy pomocnicze:

Lista kroków funkcji Dziel_na_partycje(T,ip,ik):

Algorytm szybkiego wyszukiwania k-tego największego elementu - wersja nr 3

Wejście

Wyjście:

Elementy pomocnicze:

Lista kroków:

Funkcja Dziel_na_partycje(T,i_p,i_k)

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