2 listopada 2008

Algorytm Forda-Johnsona cz II.

Algorytm Forda Johnsona służy do posortowania n-elementowej tablicy. Algorytm jest bardzo ciekawy z teoretycznego punktu widzenia, bo wykonuje bardzo małą liczbę porównań, bliską optymalnej. Algorytm działa optymalnie dla n < 16 oraz dla n = 20, 21, 22, a najmniejszy n dla którego znamy algorytm wymagający mniejszej liczby porównań to n = 47.

Na początku podzielmy tablicę n-elementową na pary i porównujemy je w tych parach. Jeśli liczba elementów jest nieparzysta to jeden element zostaje nieporównany.Elementy, które okazały się mniejsze w parach, sortujemy rekurencyjnie. Dla ułatwienia naszych dalszych rozważań ponumerujmy elementy. Największy numer dostaje element, który nie został jeszcze porównany (jeśli tablica ma nieparzyście wiele elementów). Resztę elementów numerujemy tak jak na rysunku.Teraz każdy element znajdujący się w ciągu "na dole" będziemy chcieli umieścić w ciągu "na górze". Szukając miejsca tego elementu, będziemy korzystać z wyszukiwania binarnego.
Kolejność w której będziemy wrzucać elementy z dołu do elementów na górze ma kolosalne znaczenie. Optymalną kolejnością wrzucania elementów jest następująca: 1, 3, 2, 5, 4, 11, 10, 9, 8, 7, 6, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 43, 42 ... . Element 1 wpisałem dla porządku, element ten jest już na swoim miejscu i nie trzeba nic z nim robić. Ciąg niemniej może wydawać się trochę skomplikowany. Już tłumaczę jak powstał. Można zauważyć, że po wszystkich liczbach zaznaczonych pogrubieniem, liczby maleją, aż skończą się nam liczby. Następnie pojawia się znowu pogrubiona liczba i liczby znowu zmniejszają się o jeden. Aby umieć wygenerować taki ciąg wystarczy zatem wiedzieć na jakiej podstawie wybieramy pogrubione liczby. Zauważmy, że sumy kolejnych dwóch liczb pogrubionych są równe kolejnym potęgom dwójki: 1 + 3 = 4; 3 + 5 = 8; 5 + 11 = 16; 11 + 21 = 32 itd.

Algorytm jest nieco skomplikowany. Jeśli są z nim jakieś problemy, albo trzeba coś jeszcze wytłumaczyć - to proszę o kontakt.

2 komentarze:

Mitrandir77 pisze...

Ciekawy artykuł.
Byłbym wdzięczny gdybyś wytłumaczył dlaczego właśnie taki ciąg jest optymalny.

npb pisze...

Okej. Napiszę o tym w następnej notce gdzieś w weekend.