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. Można zastosować następujący algorytm:

Przygotowujemy pustą tablicę M, w której będziemy składowali k największych elementów. Przeglądamy tablicę T i kolejne elementy próbujemy wstawić do M. Element z tablicy T trafia do M wtedy, gdy tablica M nie jest jeszcze zapełniona lub gdy element z T jest większy od pierwszego elementu M. Elementy wstawiamy, tak aby tablica M była uporządkowana nierosnąco. Gdy zakończymy przeglądanie tablicy T w pierwszym elemencie M będzie k-ty największy element z T.

Wyjaśnienia wymaga sposób działania na tablicy T. Będzie ona (k + 1) elementowa. Do wstawiania elementów wykorzystamy ideę wartownika. Tablicę M wypełnimy od M[0] do M[k-1] najmniejszą możliwą liczbą całkowitą – zagwarantuje to wstawianie najmniejszych elementu z T, 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

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:

M[0] – 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
x	–	przechowuje element z T

Lista kroków:

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

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.

12
510
-46 -267 632 -91 82 879 376 -264 -189 10 -582 447 -664 54 72
453 -401 -398 10 -97 177 256 105 429 -63 995 -437 638 10 16
-16 320 40 141 -523 -284 138 405 17 -318 257 543 -651 -378 -278
9 27 -805 962 10 39 387 382 -212 32 -64 128 10 150 20
-4 12 32 530 -35 125 450 41 316 -301 -15 246 -849 -844 -165
27 -959 14 21 8 876 539 948 -662 5 13 32 254 577 88
-452 715 10 81 -725 359 361 381 -263 793 -144 -412 137 -119 -76
496 -189 467 149 -377 714 -273 443 490 -81 976 255 180 71 703
-620 161 970 -849 68 964 935 -188 602 -63 659 111 182 245 712
31 9 -82 63 178 -832 -743 -916 -341 871 65 -646 -70 830 612
-63 877 495 14 -290 2 698 166 -227 -400 -476 941 786 129 715
99 820 502 -28 481 943 815 -70 415 413 -484 1 329 250 782
915 -466 401 641 -802 543 10 -766 934 10 -786 10 951 768 886
231 762 74 -269 -508 10 134 -328 371 937 531 -756 470 -464 -488
-926 25 502 261 -339 115 67 -962 10 68 -882 863 -996 -791 924
742 -13 370 448 183 10 -147 41 -546 768 318 120 -522 466 628
756 98 58 358 -592 421 638 -978 980 988 444 -85 118 831 48
-858 -754 281 344 210 703 -84 -885 844 685 148 389 927 84 956
103 -310 -782 175 614 523 496 -897 10 399 924 -86 539 328 995
685 -336 548 961 15 175 982 -120 300 100 583 228 -588 672 950
-68 232 659 587 -909 967 218 -608 -838 779 343 -873 980 478 572
90 -944 395 754 10 994 26 -689 399 342 3 4 5 982 730
985 780 160 -816 933 628 433 -414 845 -646 322 450 716 849 619
-669 -855 278 173 687 471 304 460 377 -424 10 733 -20 130 721
83 654 47 145 224 771 927 10 579 38 361 773 661 -662 155
35 -9 159 283 -49 971 963 -318 913 431 811 266 -374 861 284
-232 672 564 -888 932 484 973 226 143 344 962 11 444 532 646
-16 3 29 14 83 -874 871 401 -381 473 -538 908 58 760 20
96 120 160 40 -584 -176 598 110 358 443 822 403 310 -46 199
-643 -614 574 521 845 -136 43 -8 3 143 703 7 -242 50 615
34 487 526 290 818 219 968 71 -894 510 180 -447 708 -226 -296
-782 314 932 211 169 67 824 10 90 508 138 350 -824 799 882
-713 -212 335 -223 990 -735 502 743 -363 434 -484 10 -782 166 512
565 -654 934 364 397 168 43 555 65 603 524 183 303 10 399

Szybkie wyszukiwanie k-tego największego elementu

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.

Tworzenie partycji

Do utworzenia partycji musimy z tablicy wybrać jeden z elementów, który nazwiemy piwotem. W lewej partycji znajdą się wszystkie elementy niewiększe od piwotu, a w prawej partycji umieścimy wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem mogą one występować w obu partycjach. Również porządek elementów w każdej z partycji nie jest ustalony.

Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Dla naszych potrzeb wybierzemy element środkowy:

piwot ← T[(lewy + prawy) div 2]

piwot	– element podziałowy
T[ ]	– dzielona tablica
lewy	– indeks pierwszego elementu
prawy	– indeks ostatniego elementu

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku tablicy – i oraz j. Wskaźnik i przebiega przez zbiór poszukując wartości mniejszych od piwotu. Po znalezieniu takiej wartości jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaźnik j jest przesuwany na następną pozycję. Wskaźnik j zapamiętuje pozycję, na którą trafi następny element oraz na końcu wskazuje miejsce, gdzie znajdzie się piwot. W trakcie podziału piwot jest bezpiecznie przechowywany na ostatniej pozycji w zbiorze.

Przykład:

Dla przykładu podzielimy na partycje zbiór:

{ 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 }

Lp.	Operacja	Opis
1.	7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3	Wyznaczamy na piwot element środkowy.
2.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5	Piwot wymieniamy z ostatnim elementem zbioru
3.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Na początku zbioru ustawiamy dwa wskaźniki. Wskaźnik i będzie przeglądał zbiór do przedostatniej pozycji. Wskaźnik j zapamiętuje miejsce wstawiania elementów mniejszych od piwotu
4.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wskaźnikiem i szukamy elementu mniejszego od piwotu
5.	2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Znaleziony element wymieniamy z elementem na pozycji j-tej. Po wymianie wskaźnik przesuwamy o 1 pozycję.
6.	2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
7.	2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
8.	2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
9.	2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
10.	2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
11.	2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
12.	2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
13.	2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
14.	2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
15.	2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
16.	2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 i j	Szukamy
17.	2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
18.	2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 i j	Szukamy
19.	2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6 5 i j	Wymieniamy i przesuwamy j.
20.	2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 ^ i Lewa partycja j Prawa partycja	Brak dalszych elementów do wymiany. Piwot wymieniamy z elementem na pozycji j-tej. Podział na partycje zakończony.

Po zakończeniu podziału na partycje wskaźnik j wyznacza pozycję piwotu. Lewa partycja zawiera elementy mniejsze od piwotu i rozciąga się od początku zbioru do pozycji j - 1. Prawa partycja zawiera elementy większe lub równe piwotowi i rozciąga się od pozycji j + 1 do końca zbioru. Operacja podziału na partycje ma liniową klasę złożoności obliczeniowej – O(n).

Specyfikacja problemu

podziel(T, lewy, prawy)

Dane wejściowe

T[ ]	– Tablica zawierająca elementy do posortowania.
lewy	– indeks pierwszego elementu w tablicy, lewy C
prawy	– indeks ostatniego elementu w tablicy, prawy C

Dane wyjściowe

T[ ]	– Tablica podzielona na dwie partycje
j	– miejsce podziału

Zmienne pomocnicze

piwot	–	element podziałowy
i, j	–	indeksy, i, j C

Lista kroków

K01:

i ← [	lewy + prawy	]
	2

; wyznaczamy środek partycji

K02:

piwot ← T[i]

; zapamiętujemy piwot

K03:

T[i] ← T[prawy]

; na miejscu piwota umieszczamy prawy element partycji

K04:

j ← lewy

; indeks podziałowy umieszczamy na początku partycji

K05:

Dla i = lewy, lewy+1, ..., prawy-1: wykonuj:
    Jeśli T[i] < piwot to:
        T[i] ↔ T[j]
        j ← j + 1

; przeglądamy kolejne elementy partycji od pierwszego do przedostatniego

; elementy mniejsze od piwota wymieniamy z pozycją j-tą, po czym pozycję
; j-tą zwiększamy o 1

K06:

T[prawy] ← T[j]

; robimy miejsce na piwot

K07:

T[j] ← piwot

; wstawiamy piwot do tablicy

K08:

Zakończ zwracając j

Wyszukiwanie szybkie

Algorytm szybkiego wyszukiwania k-tego największego elementu

Wejście

n	-	liczba elementów w zbiorze T
T[ ]	-	tablica n-elementowa odwzorowująca zbiór T, w którym poszukujemy k-tego największego elementu.
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	-	zawiera pozycję elementu zwrotnego

podziel(T ,i_p,i_k) - funkcja dzieląca na dwie partycje.

Lista kroków:

K01:	i_p ← 0	; startowa partycja obejmuje cały zbiór T
K02:	i_k← n - 1
K03:	p ← podziel(T[ ], i_p, i_k)	; dokonujemy podziału na dwie partycje T_L i T_P
K04:	Jeśli p = n - k, to idź do K07	; sprawdzamy, czy znaleźliśmy poszukiwany element
K05:	Jeśli p > n - k to i_k ← p - 1 inaczej i_p ← p + 1	; jeśli nie, to w zależności od pozycji elementu zwrotnego ; szukamy w odpowiedniej partycji
K06:	Idź do K03
K07:	Pisz T[p]	; wyprowadzamy znaleziony element
K08:	Zakończ

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.