Also das erste Zeichen eines Strings oder ein leicht veränderter Exponent einer Fließkommazahl würde ich jetzt nicht Hash nennen wollen. Ging ja los mit einem Counting-Sort, der alle Werte kennen soll. Für einen Bucket- oder Radixsort mag dieser Hash zwar sehr gut sein, aber zum Zählen aller Werte wohl doch nicht. Eine Tabelle mit 40Bit Index wäre selbst am PC ein bisschen arg viel.
Beiträge von Hoogo im Thema „Sortieren in V2 BASIC“
-
-
Hashes bringen imho aber die innere Ordnung durcheinander. Es bringt nichts, Zahlen nach ihrer Quersumme zu sortieren.
-
Nein, das meiste wurde von Ärzten entwickelt. Haufen-Sort von Gastrologen, Blasen- und Reinsteck-Sort von Urologen.

-
Den kannte ich unter dem Namen "straight insert", und der hier gezeigte Insert-Sort war mir neu.
-
Anders gesagt: Die binäre Suche bringt nur dann etwas, wenn die Element z.B. in einer doppelt verketteten Liste organisiert sind, wo das Einfügen O(1) also quasi konstant, ohne großes Herumgeschiebe, machbar ist.
Und wie kombinierst Du die doppelt verkettete Liste mit binärer Suche?
Eine Variante von Heap-Sort (der "Bottom-Up-Heap-Sort") läßt das neue Element von unten her aufsteigen und spart dadurch im Mittel die Hälfte der Vertauschungen gegenüber dem Versickern im Standard-Heap-Sort ein.
Kann ich mir so erstmal nichts drunter vorstellen. Heapsort kenne ich so:
-Erst mal den Blickwinkel auf das Array ändern: Jedes Element hat 2 statt 1 Folge-Elemente. Wo das normale Array als Folge-Element für X an Position X+1 was hat, finden sich die Folge-Elemente im Baum bei 2*X und 2*X+1.
-Dann in einem Vorlauf erste Ordnung reinbringen: Jedes Element muss größer sein als seine beiden Folge-Elemente. Hat quasi nebenbei zur Folge, dass das größte Element ganz am Anfang landet. Ist diese Ordnung erstmal drin, kann man sich den Rest der Zeit darauf verlassen.
-Das eigentliche Sortieren tauscht erstes und letztes Element in der Array-Sicht. Der letzte Platz scheidet danach aus und wird nie mehr betrachtet. So landet das größte Element am Ende, allerdings ist jetzt die Vorsortierung im Heap kaputt, der muss repariert werden, was aber nicht viel Aufwand braucht.
-Zum Reparieren kenne ich 2 Varianten:
-Normal: Gößtes Folge-Element bestimmen (1 Vergleich), mit der Wurzel vergleichen (1 Vergleich), eventuell tauschen, im Heap vorrücken und dann weiter reparieren.
-Gößtes Folge-Element bestimmen (1 Vergleich), mit der Wurzel tauschen, im Heap vorrücken, bis man am Ende angelangt ist. Das spart einen Vergleich, kann aber falsch sein. Anschließend vom zuletzt getauschten Platz rückwärts reparieren. Klingt umständlicher, spart aber letztlich doch Overhead.