Algorytm Forda-Johnsona cz III.

Zgodnie z obietnicą w tej części postaram się wyjaśnić dlaczego akurat taki ciąg został wybrany w części drugiej.

Wszystkie rozważenia przeprowadzę na następującym przykładzie:Rozważymy trzy proste ciągi i policzymy ile w najgorszym przypadku będziemy potrzebowali porównań, aby posortować te liczby. Przypomnę jeszcze, że aby do ciągu n elementowego wstawić liczbę potrzebujemy [lg n] + 1 porównań (gdzie [x] - oznacza podłogę z liczby x).

Spróbujmy wstawiać elementy od lewej do prawej:

Wstawiamy 8 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 7 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 6 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 5 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 4 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 3 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 2 --- Wykonujemy 4 porównania ([lg 8] + 1)
W sumie - 28 porównań.

Zauważmy, że w tej metodzie wstawiając każdy element, wykonaliśmy tyle samo porównań (skorzystamy z tego faktu). Teraz spróbujmy wstawiać elementy od prawej do lewej:

Wstawiamy 2 --- Wykonujemy 2 porównania ([lg 2] + 1)
Wstawiamy 3 --- Wykonujemy 3 porównania ([lg 4] + 1)
Wstawiamy 4 --- Wykonujemy 3 porównania ([lg 6] + 1)
Wstawiamy 5 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 6 --- Wykonujemy 4 porównania ([lg 10] + 1)
Wstawiamy 7 --- Wykonujemy 4 porównania ([lg 12] + 1)
Wstawiamy 8 --- Wykonujemy 4 porównania ([lg 14] + 1)
W sumie - 24 porównania.

Czyli w drugim przypadku wykonaliśmy o 4 porównania mniej. I nasza metoda z poprzedniej notki:

Wstawiamy 3 --- Wykonujemy 2 porównania ([lg 3] + 1)
Wstawiamy 2 --- Wykonujemy 2 porównania ([lg 3] + 1)
Wstawiamy 5 --- Wykonujemy 3 porównania ([lg 7] + 1)
Wstawiamy 4 --- Wykonujemy 3 porównania ([lg 7] + 1)
Wstawiamy 8 --- Wykonujemy 4 porównania ([lg 12] + 1)
Wstawiamy 7 --- Wykonujemy 4 porównania ([lg 12] + 1)
Wstawiamy 6 --- Wykonujemy 4 porównania ([lg 12] + 1)
W sumie - 22 porównania.

Zauważmy dwie rzeczy. W momentach w którym nasz ciąg maleje - (np. we wstawieniu 8, 7, 6) wykonujemy tyle samo porównań (zauważyliśmy już to w ciągu pierwszym). Nie przypadkiem jest również to, że wewnątrz logarytmów są liczby bliskie potęgom liczby 2 (gdybyśmy wstawiali liczby do 11 to w miejscu [lg 12] pojawił by się [lg 15]).

Ciąg trzeci został więc wybrany następująco (zachłannie):
- wybierzmy wierzchołek najbardziej na lewo, który jesteśmy w stanie wstawić w dwóch ruchach.
- wstawmy go do ciągu "głównego" wraz z wszystkimi elementami na prawo od niego
- wybierzmy wierzchołek najbardziej na lewo, który jesteśmy w stanie wstawić w trzech ruchach.
- wstawmy go do ciągu "głównego" wraz z wszystkimi elementami na prawo od niego
- wybierzmy wierzchołek najbardziej na lewo, który jesteśmy w stanie wstawić w czterech ruchach.
- wstawmy go do ciągu "głównego" wraz z wszystkimi elementami na prawo od niego
...

Mam nadzieję, że nieco się wyjaśniło odnośnie tego ciągu. Jeśli nie to proszę o kontakt :)