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:     xT[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:         jj + 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 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.

 

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
Piwot wymieniamy z ostatnim elementem zbioru
3.
 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 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   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   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     i 
   j 
Szukamy
7.
 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6     i 
     j 
Wymieniamy i przesuwamy j.
8.
 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6         i 
     j 
Szukamy
9.
 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6         i 
       j 
Wymieniamy i przesuwamy j.
10.
 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6           i 
       j 
Szukamy
11.
 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6           i 
         j 
Wymieniamy i przesuwamy j.
12.
 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6             i 
         j 
Szukamy
13.
 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6             i 
           j 
Wymieniamy i przesuwamy j.
14.
 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6                 i 
           j 
Szukamy
15.
 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6                 i 
             j 
Wymieniamy i przesuwamy j.
16.
 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6                     i 
             j 
Szukamy
17.
 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6                     i 
               j 
Wymieniamy i przesuwamy j.
18.
 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6                         i 
               j 
Szukamy
19.
 2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6                         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: jlewy ; 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]
        jj + 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:
ip  -  indeks początku partycji, ip C
ik  - indeks końca partycji, ik C
p  - zawiera pozycję elementu zwrotnego

podziel(T ,ip ,ik) - funkcja dzieląca na dwie partycje.

Lista kroków:
K01: ip ← 0 ; startowa partycja obejmuje cały zbiór T
K02: ik n - 1  
K03: p ← podziel(T[ ], ip, ik) ; dokonujemy podziału na dwie partycje TL i TP
K04: Jeśli p = n - k, to idź do K07 ; sprawdzamy, czy znaleźliśmy poszukiwany element
K05: Jeśli p > n - k to ikp - 1
inaczej              ipp + 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

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.