Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych Autor artykułu: mgr Jerzy Wałaszek |
©2014 mgr
Jerzy Wałaszek
|
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ę.
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 |
k-ta największa wartość elementu w tablicy T. Dodatkowo M[0]...M[k-1] tworzy ciąg wartości maksymalnych z tablicy T.
M | – | k + 1 elementowa tablica do przechowywania wartości maksymalnych z T |
i,j | – | indeksy w tablicach T i M, i,j C |
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:
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.
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 |
minT | – | minimalna wartość w T |
maxT | – | maksymalna wartość w T |
k-ta największa wartość elementu w tablicy T.
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 |
K01: | m ← maxT - minT + 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] - minT] | |
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 + minT |
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
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 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.
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
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.
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.
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, ip C |
ik | – | indeks końcowego elementu partycji, ik C |
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
v | – | wartość elementu zwrotnego |
i,j | – | indeksy w tablicy T, i,j C |
K01: | v ← T[ip] | ; zapamiętujemy wartość elementu zwrotnego |
K02: | i ← ip | ; indeksem i będziemy szukali elementów ≥ v |
K03: | j ← ik + 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 TP, a mniejsze w TL |
K05: | i ← i + 1 | ; przesuwamy się na następną pozycję w TL |
K06: | Jeśli T[i] < v, to idź do K05 | ; szukamy elementu, który nie należy do TL |
K07: | j ← j - 1 | ; przesuwamy się na poprzednią pozycję w TP |
K08: | Jeśli T[j] > v, to idź do K07 | ; szukamy elementu, który nie należy do TP |
K09: | Jeśli i < j, to T[i] ↔ T[j] | ; znalezione elementy zamieniamy miejscami |
K10: | T[ip] ← 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 |
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 |
Wartość k-tego największego elementu zbioru T.
ip | – | indeks początku partycji, ip C |
ik | – | indeks końca partycji, ik C |
pv | – | zawiera pozycję elementu zwrotnego |
Dziel_na_partycje(T,ip,ik) – funkcja dzieląca na dwie partycje wg elementu zwrotnego. Funkcja opisana powyżej.
K01: | ip ← 0 | ; startowa partycja obejmuje cały zbiór T |
K02: | ik ← n - 1 | |
K03: | pv ← Dziel_na_partycje(T,ip,ik) | ; dokonujemy podziału na dwie partycje TL i TP |
K04: | Jeśli pv = n - k, to zakończ z wynikiem T[pv] | ; sprawdzamy, czy znaleźliśmy poszukiwany element |
K05: | Jeśli n - k < pv, idź do K08 | ; jeśli nie, to w zależności od pozycji elementu zwrotnego |
K06: | ip ← pv + 1 | ; elementu będziemy szukać w TP |
K07: | Idź do K03 | ; lub |
K08: | ik ← pv - 1 | ; elementu będziemy szukać w TL |
K09: | Idź do K03 |
I Liceum Ogólnokształcące |
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