std.sort — Sortierung

→ Zurück zur Unit-Übersicht

QuickSort für int64-Felder mit Median-of-Three-Pivotwahl und Insertion-Sort für kurze Teilfolgen. Sortiert an Ort und Stelle, ohne zusätzlichen Speicher. Die Unit hat genau eine öffentliche Funktion.

Autor: Andreas Röne
Copyright: 2024–2025 Andreas Röne
Quelle: std/sort.lyx

<WRAP info> Der frühere Sortierfehler (#1458) ist behoben. Partition arbeitet jetzt nach dem Lomuto-Schema mit eindeutigem Trennindex. Nachgeprüft mit lyxc 1.0.21A: 500 Zufallsfelder, jeweils Reihenfolge und Elementsumme geprüft — 0 Fehler. Auch std.stats (ArraySort, ArrayMedian) ist damit wieder verlässlich. </WRAP>

Import

import std.sort;

Funktionen

Signatur	Beschreibung
`SortInt64(arr: int64, len: int64): void`	Sortiert `len` `int64`-Werte ab Adresse `arr` aufsteigend, in-place

arr ist ein roher Speicherblock mit 8 Byte Schrittweite; len zählt Elemente, nicht Bytes. len ⇐ 1 kehrt sofort zurück, len == 0 ist zulässig.

Die übrigen Funktionen der Datei (Partition, MedianOfThree, InsertionSort, QuickSortInternal, SortSwap, SortGet) sind unit-privat.

Aufbau

SortInt64(arr, len)
   └─ QuickSortInternal(arr, low, high)
        ├─ Teilfolge < 10 Elemente → InsertionSort
        └─ sonst: Partition (Median-of-Three) → zwei Rekursionsäste

Der Schwellwert von 10 Elementen ist fest verdrahtet: für kurze Teilfolgen ist Insertion-Sort schneller als die Rekursion. Median-of-Three wählt den Pivot aus erstem, mittlerem und letztem Element und vermeidet damit den Worst-Case bei bereits sortierten Eingaben.

Laufzeit: im Mittel O(n log n), im schlechtesten Fall O(n²). Die Sortierung ist nicht stabil — gleiche Werte können ihre Reihenfolge tauschen. Bei reinen Zahlen spielt das keine Rolle; wer Indizes mitführt, muss es beachten.

Beispiel

import std.sort;
import std.alloc;
import std.math;

fn zeige(arr: int64, n: int64): void {
    var i: int64 := 0;
    while (i < n) { Print(IntToStr(peek64(arr + i*8)), " "); i := i + 1; }
    PrintLn("");
}
fn istSortiert(arr: int64, n: int64): int64 {
    var i: int64 := 1;
    while (i < n) { if (peek64(arr + (i-1)*8) > peek64(arr + i*8)) { return 0; } i := i + 1; }
    return 1;
}
fn summe(arr: int64, n: int64): int64 {
    var i: int64 := 0; var s: int64 := 0;
    while (i < n) { s := s + peek64(arr + i*8); i := i + 1; }
    return s;
}

fn main(): int64 {
    var w: int64 := alloc(10 * 8);
    poke64(w,    33); poke64(w+8,  18); poke64(w+16, 43); poke64(w+24,  7);
    poke64(w+32, 45); poke64(w+40,  8); poke64(w+48, 28); poke64(w+56, 15);
    poke64(w+64,  1); poke64(w+72, 35);
    Print("Eingabe:  "); zeige(w, 10);
    SortInt64(w, 10);
    Print("Ergebnis: "); zeige(w, 10);

    // Belastungstest: Reihenfolge und Elementsumme ueber viele Zufallsarrays
    RandomSeed(11);
    var fehler: int64 := 0;
    var runde: int64 := 0;
    while (runde < 500) {
        var a: int64 := alloc(50 * 8);
        var i: int64 := 0;
        while (i < 50) { poke64(a + i*8, Abs64(Random()) % 1000); i := i + 1; }
        var vorher: int64 := summe(a, 50);
        SortInt64(a, 50);
        if (istSortiert(a, 50) == 0 || summe(a, 50) != vorher) { fehler := fehler + 1; }
        free(a, 50*8);
        runde := runde + 1;
    }
    PrintLn("fehlerhaft sortiert: ", IntToStr(fehler), " von 500 Zufallsarrays (n=50)");

    // Sonderfaelle
    var e: int64 := alloc(8);
    poke64(e, 42);
    SortInt64(e, 1); PrintLn("n=1 unveraendert: ", IntToStr(peek64(e)));
    SortInt64(e, 0); PrintLn("n=0 ueberlebt");
    return 0;
}

Ausgabe:

Eingabe:  33 18 43 7 45 8 28 15 1 35
Ergebnis: 1 7 8 15 18 28 33 35 43 45
fehlerhaft sortiert: 0 von 500 Zufallsarrays (n=50)
n=1 unveraendert: 42
n=0 ueberlebt

Eine Sortierung richtig prüfen

Der Belastungstest im Beispiel ist keine Zierde — genau diese Form hätte den früheren Fehler #1458 sofort gezeigt, während die üblichen Testfälle ihn durchgelassen haben. Zwei Dinge gehören zusammen:

Reihenfolge allein übersieht verlorene oder verdoppelte Werte.
Elementsumme allein übersieht Vertauschungen.

Und zwar über Zufallsfelder. Bereits sortierte, umgekehrte oder gleichförmige Eingaben liefen bei #1458 alle korrekt durch; nur echte Zufallsdaten fielen durch — 448 von 500.

fn istSortiert(arr: int64, n: int64): int64 {
    var i: int64 := 1;
    while (i < n) {
        if (peek64(arr + (i-1)*8) > peek64(arr + i*8)) { return 0; }
        i := i + 1;
    }
    return 1;
}

Grenzen

Nur int64. Für andere Typen oder eigene Vergleichsregeln gibt es keine Variante mit Vergleichsfunktion.
Nur aufsteigend. Absteigend erhält man durch Umdrehen des sortierten Feldes oder über ListInt64SortDesc aus std.list.
Nicht stabil.
Keine Bereichsprüfung. SortInt64 vertraut auf len; ein zu großer Wert sortiert über den Puffer hinaus.