====== std.sort — Sortierung ======

→ [[lyx_-_programmiersprache:units|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 [[lyx_-_programmiersprache:units:stats|std.stats]] (''ArraySort'', ''ArrayMedian'') ist damit wieder verlässlich.
</WRAP>

===== Import =====

<code lyx>
import std.sort;
</code>

----

===== 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 =====

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

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 =====

<code lyx>
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;
}
</code>

Ausgabe:

<code>
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
</code>

----

===== 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.

<code lyx>
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;
}
</code>

----

===== 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 [[lyx_-_programmiersprache:units:list|std.list]].
  * **Nicht stabil.**
  * **Keine Bereichsprüfung.** ''SortInt64'' vertraut auf ''len''; ein zu großer Wert sortiert über den Puffer hinaus.

----

===== Verwandte Units =====

  * [[lyx_-_programmiersprache:units:stats|std.stats]] — ''ArraySort'', ''ArrayMedian'' und die übrigen Kennzahlen
  * [[lyx_-_programmiersprache:units:list|std.list]] — ''ListInt64Sort''/''ListInt64SortDesc'' für dynamische Listen
  * [[lyx_-_programmiersprache:units:math|std.math]] — ''Min64'', ''Max64'', ''Clamp64''