marthy
(Marthy)
22 Sierpień 2005 20:45
#1
Czy ktoś zna jakieś namiary na opis tego algorytmu?
system
(system)
22 Sierpień 2005 20:46
#2
A o co chodzi w tym algorytmie, bo może będę mógł pomóc.
marthy
(Marthy)
22 Sierpień 2005 20:48
#3
No właśnie nie wiem o co chodzi,a muszę sie dowiedzieć (Możliwe, że ma coś wspólnego z Quicksortem , tudzież z algorytmem Hoare’a…)
Monczkin
(Monczkin)
22 Sierpień 2005 20:50
#4
marthy
(Marthy)
22 Sierpień 2005 20:53
#5
Niestety… nie ma Może ten algorytm ma jakąś inną nazwę, sama nie wiem…
Monczkin
(Monczkin)
22 Sierpień 2005 20:56
#6
Algorytm Hoare’a Gdy potrzebujemy wiedzieć jaka jest wartość k-tego elementu nieposortowanego ciągu (np.: kto zdobył k-te miejsce, bądź jaka jest mediana czyli element n/2 w kolejności), można wówczas oczywiście posorotwać cały ciąg i sprawdzić k-ty element. Jest to jednak operacja zbyt kosztowna. Wystarczy bowiem zastosować algortym Hoare’a. W algorytmie Hoare’a stosujemy podobną metodę jak w quicksorcie. Ciąg wejściowy dzielimy na 2 podciągi: elementów mniejszych i większych bądź równych pewnemu elementowi. Podział taki wykonujemy następująco: dla danego ciągu wybieramy tzw. element dzielący - niech w naszym przypadku będzie to element pierwszy z brzegu. Teraz poruszamy się od lewej strony ciągu poszukując elementu większego bądź równego elementowi dzielącemu, gdy go znajdziemy od prawej strony ciągu poruszamy się szukając elementu mniejszego od elementu dzielącego, gdy go znajdziemy zamieniamy te wyrazy ciągu miejscami. Następnie kontunuujemy przeszukiwanie dalej tak długo aż spotakamy się podczas poszukiwań od lewej i prawej strony. Miejsce spotkania dzieli nam ciąg na elementy mniejsze na lewo od miejsca spotkania i pozotałe elementy większe bądź równe elementowi dzielącemu. Przykład: Dany jest ciąg 3, 2, 5, 4, 8, 1, 6 Jak powiedzieliśmy elementem dzielącym będzie element pierwszy z brzegu czyli 3. Poruszamy się od lewej szukając elementu większego lub równego 3. Jest nim oczywiście 3. Teraz poruszamy się od prawej szukając elementu mniejszego od 3, jest nim 1. Znalezione elementy zamieniamy miejscami i otrzumjemy ciąg: 1, 2, 5, 4, 8, 3, 6 Znów poruszamy się dalej od lewej szukając elementu większego bądź równego 3. Jest nim 5. Teraz poruszamy się dalej od prawej szukając elementu mniejszego od 3. Nie odnajdujemy go jednak przed znalezioną piątką. W tym własnie miejscu następuje miejsce spotkania, które dzieli ciąg na elementy mniejsze od 3 (1, 2) na lewo od 5 i pozostałe (5, 4, 8, 3, 6) większe równe 3. Algorytm Hoare’a polega na tym, że wejsciowy ciąg dzielimy tak jak pokazano to powyżej. Następnie w zależności od liczebności wynikowych podciągów wywołujemy rekurencyjnie funkcję dla odpowiedniego podciągu. Jeżeli w ciągu c szukamy elementu k-tego to po podzieleniu wyżej podaną procedurą, szukamy albo elementu k-tego w ciągu elementów mniejszych od elementu dzielącego jeśli liczebność tego ciągu jest większa bądź równa k, bądź szukamy elementu k-liczebność ciągu liczb mniejszych od elementu dzielącego w ciągu elementów większych bądź równych elementowi dzielącemu. Rekursję powtarzamy tak długo aż w wyniku otrzymamy ciąg o 1 elemencie. Przykład: Ciąg: (7,2,4,3,6,8,1,5,9) Szukamy trzeciego elementu w ciągu Niech elementem dzielącym będzie 7 - pierwsza liczba z brzegu, wówczas ciąg elementów mniejszych od 7 to (5,2,4,3,6,1) natomiast ciag elementów większych bądź równych: (8,7,9). Ponieważ liczność ciagu elemntów mniejszych od 7 jest większa równa 3, tam będziemy dalej szukać naszej liczby. A więc wywołujemy rekurencyjnie funkcję dla ciągu elementów mniejszych od 7 szukając tam elementu trzeciego. Elementem dzielącym jest tutaj 5, wówczas ciąg elementów mniejszych od 5 to (1,2,3), a większych bądź równych (4,6,5). Ponieważ liczność ciągu elementów mniejszych od 5 jest większa równa 3, zatem w tym ciągu będziemy szukać naszej liczby. Elementem dzielącym jest tutaj 1. Tym razem procedura przedstawiona na samym początku podzieli nasz ciąg na ciąg elementów mniejszym bądź równych 1 (1) oraz ciąg elementów większych (2,3). Ponieważ w tym wypadku ciąg elementów mniejszych bądź równych nie ma liczności większej bądź równej 3, zatem nasze poszukiwania będziemy kontunuować w ciagu elementów większych. Lecz nie będziemy tam szukać elementu trzeciego lecz elementu 3-liczność zbioru elementów mniejszych bądź równych. W naszym wypadku jest to 3-1, zatem szukamy elementu 2 w zbiorze elementów większych do elementu dzielącego. Elementem dzielącym jest tutaj 2. Procedura podzieli nam ten ciąg na ciąg (2) oraz (3). Ponieważ liczność ciągu elementów mniejszych bądź równych jest mniejsza niż 2 zatem naszego elementu szukać będziemy w zbiorze elementów większych. Szukamy w nim zatem elementu 2-liczność zbioru elementów mniejszych bądź równych. Czyli elementu 2-1. Ponieważ otrzymaliśmy ciąg o jednym elemencie, w którym szukamy elementu pierwszego wiemy, ze naszym poszukiwanym elementem jest 3.
http://www.algorytm.cad.pl/
marthy
(Marthy)
22 Sierpień 2005 20:59
#7
Tak, to znalazlam, ale w dalszym ciągu nic nigdzie nie widzę na temat “magicznych piątek”.
_gosc
(_gosc_)
28 Marzec 2006 01:29
#8
Kluczem do wydajnosci quicksorta i wyszukiwania n-tego elementu jest wybór elementu wzgledem ktorego dzielimy zbior - gdyby w quicksorcie za kazdym razem dzielic n na n-1 i 1 dzialalby w n^2
Najlepiej wybrac element dzielacy dokladnie na pol, czyli mediane - i do tego mniej wiecej sluza magiczne piatki - algorytm wyznacza *pseudomediane*, ktora jest dobra w tym sensie, ze zapewnia zawsze liniowy czasz dzialania algorytmu.
Dzialanie - podziel input na grupki 5 elementowe i z kazdej takiej grupki wylicz mediane (prawdziwa), nastepnie z otrzymane mediany potraktuj w taki sam sposob (i tak w kolko), az otrzymasz tylko 1 mediane.
przyklad nie dla 5, ale 3
213 156 78 65 34 48000000 78 68
(213 156 78 ) ( 65 34 48000000 ) (78 68 )
156 65 73
73
i podzial:
34 65 68 78 78 156 213 48000000
Jak dobrze zaimplementujesz powinno zuzyc rzedu log n dodatkowej pamieci : D
Opoznienie calkiem spore, ale jestescie pierwszym trafieniem w googlu i nie macie wyjasnienia ; )
Drugie trafienie to notatki na http://www.ii.uni.wroc.pl/~lorys/AiSD05/AiSD05.htm
btw: nie moglibyscie dac mozliwosci pisania postow z goscia?
btw2: pozdr dla wszystkich innych, ktorzy tez nie byli na wykladzie :mrgreen: (i zrobili :o na widok “magicznych” piatek)