Wie sortiert man 5 Elemente mit sieben Vergleichen?

Question

könnte mir jemand zeigen, wie man fünf Elemente mit sieben Vergleichen sortieren kann.

Am besten an der Zahlenfolge 5 4 3 2 1, weil ohne Bezeichnungen fand ich die Interneterklärungen nicht so verständlich.

MfG Fragesteller

Comments

Ist das eine Wettbewerbsaufgabe?

---

Siehe Donald Knuth The Art of Computer Programming volume 3:

https://archive.org/details/B-001-001-250/page/n199

Seite 183-184.

---

Ausgangszustand : unsortiert
Die Sortierreihenfolge muß bekannt sein
( wo will ich mit dem Sortieren hin ? )
Welcher Endzustand soll erreicht werden ?

---

Hier ist einer der schnellsten Sortieralgorithmen für kleine Listen.

https://en.wikipedia.org/wiki/Merge-insertion_sort

Er braucht für 5 Elemente nur 7 Vergleiche.

Answer 1

Der Merge-Insertion-Sort Algorithmus funktioniert für kleine Listen sehr effizient. Er ist vergleichbasiert.

Eine andere Möglichkeit ist, einen Algorithmus zu wählen, der garkeine Vergleiche zum Sortieren ausführt: Countingsort wäre hier gut.

Beste Grüße

Felix