Jak przeprowadzić scalanie 8 elementów z 16 porównaniami?

Zadałem pytanie dotyczące sortowania kilka dni temu. Dowiedziałem się, jak udowodnić, że najmniejsza liczba porównań, sortując 8 elementów, wynosi 16 i zrozumiałam dlaczego. Ale mój algorytm sortowania scalającego liczy 17 porównań, w moim przypadku jest to prawda. Aby połączyć dwie posortowane tablice o długości xiy, musimy porównać (x + y) -1, więc w sortowaniu scalonym otrzymujemy 17 porównań. Ale musi być możliwe z 16 porównaniami, więc .. jak? gdzie mogę zapisać to 1 porównanie).Jak przeprowadzić scalanie 8 elementów z 16 porównaniami?

Oto zdjęcie:

enter image description here

http://oeis.org/A001768

Dzięki!

Źródło

2011-12-31 nakajuice

A to już [poprzednie pytanie] (http://stackoverflow.com/q/8673860/60761) –

Podajesz, że już wiesz "jak udowodnić, że ... jest 16". Twój dowód powinien być w stanie odpowiedzieć na to pytanie. –

to znaczy, spodziewam się, że teoretycznie jest to możliwe – nakajuice

OP zawiera wyraźny dowód, że scalić sortowania z 8 elementów nie jest możliwe z mniej niż 17 porównań. Nadal istnieje możliwość sortowania 8 elementów w 16 porównaniach z innym algorytmem. Algorytm opisany jest w "The art of computer programming" D.Knutha, tom 3, rozdział 5.3.1. Nazywa się scalić wstawianie.

Najniższa liczba porównań nie czyni tego algorytmu najszybszym. Na przykład: Batcher odd–even mergesort z 19 porównaniami łatwo osiąga lepsze wyniki niż scalanie wstawiania, ponieważ wykonuje większość porównań równolegle.

Źródło

2011-12-31 14:18:51

bardzo najlepsza odpowiedź .. jest cały akapit na mój problem z "najlepszym najgorszym przypadkiem" dla liczby porównań. – nakajuice

Możesz otrzymać tylko najmniejsze rozwiązanie, gdy masz nieparzystą liczbę numerów do posortowania.

Źródło

2011-12-31 12:20:37 ChristopherS

Jak to zrobić? To nie jest dla mnie oczywiste. – Dialecticus

Ponieważ na najniższym poziomie zapisujesz porównanie. Twoja baza będzie wyglądała jak 2 - 2 - 2 - 1 z 7 elementami. W związku z tym nie trzeba porównywać ostatnich par (ponieważ nie jest to para). – ChristopherS

Można udowodnić, że 16 porównań nie wystarczy, próbując wszystkich możliwych algorytmów. Potrzebny byłby do tego "algorytm generujący algorytm".

Źródło

2011-12-31 12:34:09 Dialecticus

Jak przeprowadzić scalanie 8 elementów z 16 porównaniami?

Odpowiedz

Powiązane problemy