Sortuj tablicę 5 liczb całkowitych z maksymalnie 7 porównaniami

19

Jak mogę posortować listę 5 liczb całkowitych tak, że w najgorszym przypadku potrzeba 7 porównań? Nie obchodzi mnie, ile innych operacji zostanie wykonanych. Nie wiem nic szczególnego o liczbach całkowitych.

Wypróbowałem kilka różnych metod dzielenia i podbijania, które obniżają mnie do 8 porównań, takich jak stosowanie podejścia scalesort lub łączenie scalesort z wykorzystaniem wyszukiwania binarnego w celu znalezienia pozycji wstawiania, ale za każdym razem, gdy kończę z 8, porównuje najgorszy przypadek .

W tej chwili szukam tylko wskazówki, a nie rozwiązania.

Robert S. Barnes
źródło
Czy próbowałeś napisać drzewo „porównaj do”? Ma liści, każdy odpowiadający permutacji liczb całkowitych. Jeśli nie wiesz, co rozumiem przez drzewo „porównaj z”, czy znasz dowód, że potrzebujesz porównań? Ps, co sprawia, że ​​myślisz, że to możliwe? n log n5!=120nlogn
Pål GD
1
Cóż, w uzupełnieniu 8-bitowym dwa jest if(x > y)to to samo, if((x - y) & 0x80)co trudno porównać. Chyba powinniśmy zapomnieć, że obiekty są liczbami całkowitymi i zakładamy, że musimy użyć jakiejś magicznej compare(x, y)funkcji, aby porównać te obiekty ...
Karolis Juodelė
2
Czy „patrz rozdział 5.3 na temat optymalnego sortowania w tomie 3 sztuki programowania komputerowego , który dokładnie obejmuje to pytanie”, jest wskazówką lub rozwiązaniem? :-)
Steven Stadnicki
3
Granicą jest tak naprawdę, żei . Jest to możliwe (w zasadzie). 5 ! = 120 < 2 7 = 1282cn!5!=120<27=128
vonbrand,

Odpowiedzi:

23

Jest tylko jeden sposób na rozpoczęcie tego procesu (i dla prawie wszystkich twoich decyzji dotyczących porównania w późniejszych krokach jest tylko jedna poprawna). Oto jak to rozgryźć. Po pierwsze, pamiętaj, że możesz uzyskać możliwych odpowiedzi do porównań i różnych kombinacji, w których musisz rozróżnić.5 ! = 12027=1285!=120

Pierwsze porównanie jest łatwe: musisz porównać dwa klucze, a ponieważ nic o nich nie wiesz, wszystkie opcje są równie dobre. Więc powiedzmy, że porównanie i , a okaże się, że . Masz teraz możliwych odpowiedzi i pozostało możliwych permutacji (ponieważ wyeliminowaliśmy połowę z nich).b a b 2 6 = 64 60abab26=6460

Następnie możemy albo porównać i , lub możemy porównać do jednego z klawiszy używaliśmy w pierwszej porównania. Jeśli porównamy i , i dowiedzieć się, że , wtedy mamy pozostałe odpowiedzi i możliwych permutacji. Z drugiej strony, jeśli porównamy z , i odkryjemy, że , mamy możliwych permutacji, ponieważ wyeliminowaliśmy możliwych permutacji (te z ) . Mamy tylkod c c d c d 32 30 C C 40 1 / 3 C b 32cdccdcd3230caac401/3cab32 możliwe pozostałe odpowiedzi, więc nie mamy szczęścia.

Teraz wiemy, że musimy porównać pierwszy i drugi klucz oraz trzeci i czwarty klucz. Możemy założyć, że mamy i . Jeśli porównamy do któregokolwiek z tych czterech kluczy, tym samym argumentem, którego użyliśmy w poprzednim kroku, możemy wyeliminować tylko pozostałych permutacji i nie mamy szczęścia. Musimy więc porównać dwa klucze . Biorąc pod uwagę symetrię, mamy dwie możliwości: porównaj i lub porównaj i . Podobny argument zliczania pokazuje, że musimy porównać i . Możemy założyć, że bez utraty ogólności, żec d e 1 / 3 , b , c , d C do D C C b C dabcde1/3a,b,c,dacadacac , a teraz mamy oraz .abacd

Ponieważ poprosiłeś o podpowiedź, nie omówię reszty argumentu. Pozostały ci cztery porównania. Używaj ich mądrze.

Peter Shor
źródło
Jak doszło do tego, że porównanie do powoduje tylko 40 permutacji? cac
Robert S. Barnes
1
@Robert: Załóżmy, że masz i . Następnie istnieją dwie kombinacje zgodne z tymi ograniczeniami, oraz . Dla każdej z tych dwóch permutacji istnieją cztery miejsca, w których można dodać i pięć miejsc, w których można dodać . a c a , b , c a < b < c a < c < b d eabaca,b,ca<b<ca<c<bde
Peter Shor
8

Można to znaleźć w The Art of Computer Programming vol. III autorstwa D.Knuth, ale strategia jest następująca (zakładam, że masz tablicę ): Jeśli chcesz przeczytać podpowiedź tylko dwie pierwsze linijki mojej odpowiedzi{a,b,c,d,e}

  • Pary pierwszych grup liczb: .(a,b),(c,d)
  • Porównaj pary, aby je posortować, np .: .a<b,c<d
  • Porównaj najmniejsze elementy parami, mamy prowadzić np < c .a<c
  • Porównaj ostatni element , z większym elementem w ostatnim porównaniu ( c ) ec
    • Jeśli , łatwo jest zakończyć z pozostałymi 3 porównaniami. Skończone.e<c
    • Jeśli , powinieneś posortować { b , c , d , e } ze znajomością c < e , c < d . e>c{b,c,d,e}c<e,c<d
      • , jeśli d < e potem Compare(d,e)d<e
        • , jeśli b > dCompare(b,d)b>d
          • . Skończone.Compare(b,e)
        • jeśli b<d
          • . Skończone.Compare(b,c)
      • jeśli d>e
        • jeśli b > eCompare(b,e)b>e
          • . Skończone.Compare(b,d)
        • jeśli b<e
          • . Skończone.Compare(b,c)

Wszystkie wyżej wymienione sposoby powodują najwyżej trzy porównania po pierwszym porównaniu z c . (co najwyżej 7). ec

Jerzy
źródło
Czy jesteś pewien, że to prawda? Załóżmy, że otrzymujesz następujące wyniki: a <b, c <d, a <c, a następnie c <e, b <e, c <b oraz d <e. Porządki a <c <b <d <e i a <c <d <b <e są z nimi zgodne. Powodem jest to, że bi id nigdy nie są porównywane, w sposób dorozumiany lub jawny. Może gdzieś się mylę, jeśli tak, popraw mnie.
George