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:
Ciekawy artykuł.
Byłbym wdzięczny gdybyś wytłumaczył dlaczego właśnie taki ciąg jest optymalny.
Okej. Napiszę o tym w następnej notce gdzieś w weekend.
Prześlij komentarz