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

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.

algorithms sorting

— 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?

5! = 120

$5! = 120$

n \log n

$n \log n$

— Pål GD

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ė

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

Granicą jest tak naprawdę, żei . Jest to możliwe (w zasadzie).

2^{c} \geq n!

$2^c \ge n!$

5! = 120 < 2^{7} = 128

$5! = 120 < 2^7 = 128$

— vonbrand,

powiązane: Sortowanie tablicy z minimalną liczbą porównań

— Janus Troelsen

Odpowiedzi:

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ć. $2^7 =128$ $5! = 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). $a$ $b$ $a \leq b$ $2^6 = 64$ $60$

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 tylko $c$ $d$ $c$ $c$ $d$ $c \leq d$ $32$ $30$ $c$ $a$ $a \leq c$ $40$ $1/3$ $c \leq a \leq b$ $32$ 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, że $a\leq b$ $c \leq d$ $e$ $1/3$ $a,b,c,d$ $a$ $c$ $a$ $d$ $a$ $c$ $a \leq c$ , a teraz mamy oraz . $a \leq b$ $a \leq c \leq d$

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?

a

$a$

c

$c$

— Robert S. Barnes

@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 \leq b

$a \leq b$

a \leq c

$a \leq c$

a, b, c

$a,b,c$

a < b < c

$a < b < c$

a < c < b

$a < c < b$

d

$d$

e

$e$

— Peter Shor

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 . $a<c$
Porównaj ostatni element , z większym elementem w ostatnim porównaniu ( c )
- 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 .
  - , jeśli d < e potem
    - , jeśli b > d
      - . Skończone. $Compare(b,e)$
    - jeśli
      - . Skończone. $Compare(b,c)$
  - jeśli
    - jeśli b > e
      - . Skończone. $Compare(b,d)$
    - jeśli
      - . Skończone. $Compare(b,c)$

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

— 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