Minimalna liczba porównań potrzebnych do posortowania (uporządkowania) 5 elementów

Znajdź najmniejszą liczbę porównań potrzebną do posortowania (uporządkowania) pięciu elementów i opracuj algorytm, który sortuje te elementy przy użyciu tej liczby porównań.

Rozwiązanie : Jest ich 5! = 120 możliwych wyników. Dlatego drzewo binarne do procedury sortowania będzie miało co najmniej 7 poziomów. Rzeczywiście, ≥ 120 oznacza≥ 7. Ale 7 porównań to za mało. Najmniejsza liczba porównań potrzebnych do posortowania (uporządkowania) pięciu elementów wynosi 8.$2^h$$h$

Oto moje aktualne pytanie: znalazłem algorytm, który robi to w porównaniu 8, ale jak mogę udowodnić, że nie da się tego zrobić w 7 porównaniach?

Rozwiązanie jest złe. Demuth [1; przez 2, ust. 5.3.1] pokazuje, że pięć wartości można posortować przy użyciu tylko siedmiu porównań, tj. Że dolna granica „teorii informacji” jest w tym przypadku ścisła.

Odpowiedź jest metodą dostosowaną do , a nie ogólnym algorytmem. To też nie jest zbyt miłe. Oto zarys:$n=5$

1. Posortuj dwie pierwsze pary.

2. Zamów pary we właściwym większym elemencie.

   Nazwij wynik ; znamy ia < b < $[a,b,c,d,e]$$a<b<d$ .$c<d$

3. Wstaw do [ a , b , d ] .$e$$[a,b,d]$

4. Wstaw do wyniku kroku 3.$c$

Pierwszy krok wyraźnie obejmuje dwa porównania, drugi tylko jeden. Ostatnie dwa kroki wymagają dwóch porównań; w obu przypadkach wstawiamy do trzyelementowej listy (w kroku 4. zauważmy, że z wiemy, że c jest mniejszy niż ostatni element z dostępnej listy) i najpierw porównujemy z środkowym elementem. To daje w sumie siedem porównań.$c<d$$c$

Ponieważ nie widzę, jak napisać „ładny” pseudokod tego, zobacz tutaj dla przetestowanej (i miejmy nadzieję, że czytelnej) implementacji.

1. Doktorat praca dyplomowa (Uniwersytet Stanforda) HB Demuth (1956)

   Zobacz także elektroniczne sortowanie danych według HB Demuth (1985)

2. Sortowanie i wyszukiwanie według Donalda E. Knutha; The Art of Computer Programming Vol. 3 (wydanie 2, 1998)

Teoretyczna dolna granica sortowania opartego na porównaniu to $\log(n!)$ . Oznacza to, że aby posortować $n$ elementów za pomocą porównań $<$ lub $>$ , potrzeba co najmniej 2 logarytmu podstawowego $n!$, stąd $\log(5!) \approx 6.91$ operacji.

Od $5!= 120$ i $2^7= 128$ , za pomocą binarnego drzewa decyzyjnego można posortować 5 pozycji w 7 porównaniach. Drzewo dokładnie określa, które ze 120 permutacji masz, a następnie dokonuje zamiany potrzebnej do jego posortowania.

To nie jest ładny ani krótki kod i prawdopodobnie powinieneś użyć metod generowania kodu do stworzenia drzewa decyzyjnego i zamiany zamiast kodowania go ręcznie, ale działa; i sprawdzalnie działa na każdą możliwą permutację 5 przedmiotów, co dowodzi, że możesz posortować 5 przedmiotów w nie więcej niż 7 porównaniach.

Myślałem Quicksort. wybierasz jako element obrotowy element, który akurat jest środkowym elementem. porównaj oś obrotu z pozostałymi 4 elementami, co posortuje dwa stosy. każdy z tych stosów można posortować w 1 porównaniu. chyba że popełniłem straszny błąd, 5 pozycji zostało w pełni posortowanych w zaledwie 6 porównaniach i myślę, że jest to absolutnie najmniejsza liczba porównań potrzebnych do wykonania pracy. w pierwotnym pytaniu znaleziono najmniejszą liczbę porównań do sortowania 5 elementów.

Jeśli możesz przetestować algorytm, przetestuj go na wszystkich kombinacjach liczb. Jeśli masz dużo liczb, sprawdź wiele losowych kombinacji. Nie precyzyjne, ale szybsze niż wszystkie kombinacje.

Minimalne
a <b <c = 2
a <b <c <d = 3
a <b <c <d <e = 4

Maksymalnie
3 ^ 3
4 ^ 4
5 ^ 5

Wstaw do środka, użyj 3-6 dla 4 cyfr.
Scalanie użyj 4-5 dla 4 liczb.
Minimalne porównanie przez wiki to 5 dla 4 liczb :) Dla 5 to 7. Używasz 8, wciąż tyle.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
Jeśli znasz wszystko przed porównaniami, możesz przejść do porównań. Moja średnia dla 4 liczb wynosi 3,96 / 1024 dla wszystkich kombinacji.