Dieser absurd einfache Sortieralgorithmus funktioniert – und niemand glaubt es

I Can't Believe It Can Sort

Zwei verschachtelte Schleifen, die jedes Element mit jedem vergleichen und bei Bedarf tauschen – mehr steckt nicht hinter „I Can't Believe It Can Sort“. Wer den Pseudocode liest, hält ihn für kaputt, doch das Array ist am Ende tatsächlich sortiert. Der Algorithmus stammt aus einem Forschungspapier von Stanley P. Y. Fung und läuft in O(n²), ist also deutlich langsamer als quicksort oder mergesort.

Der Grund für den Namen ist, dass man beim Blick auf den Pseudocode nicht glaubt, dass er tatsächlich sortieren kann – aber er tut es.
  1. Someone

    Ein Paper dazu mit einem Beweis, wie/warum es funktioniert: https://arxiv.org/pdf/2110.01111, in dem es heißt:

    „Dieser Algorithmus hat nichts Gutes an sich. Er ist langsam – der Algorithmus läuft offensichtlich in Θ(n2)-Zeit, egal ob im Worst-Case, Average-Case oder Best-Case. Er vergleicht unnötigerweise alle Positionspaare zweimal (aber siehe Abschnitt 3). Es scheint keine Intuition dahinter zu stecken, und seine Korrektheit ist nicht ganz offensichtlich. Man möchte ihn sicher nicht als erstes Beispiel verwenden, um Studierende in Sortieralgorithmen einzuführen. Er ist nicht stabil, funktioniert nicht gut für externes Sortieren, kann keine online eintreffenden Eingaben sortieren und profitiert nicht von teilweise sortierten Eingaben. Sein einziger Reiz mag seine Einfachheit sein, was die Anzahl der Codezeilen und die „Symmetrie“ der beiden Schleifen betrifft.“

  2. petercooper

    Zum Thema lustige kleine Sortieralgorithmen: Ich war immer ganz angetan vom „Sleep Sort“:

    a=[5,3,1,4,2];b=[];a.map(n=>setTimeout(()=>b.push(n),n))

    Natürlich sollte man das nie in echt verwenden, aber ich fand es unterhaltsam, über das Verhalten und die Fallstricke dieses Algorithmus in verschiedenen Sprachen nachzudenken.

  3. fwlr

    Es gibt zwei Gründe, warum es (intuitiv) nicht funktionieren sollte: Der eine ist, dass die innere for-Schleife ebenfalls von vorne beginnt, ohne zu prüfen, wo die äußere for-Schleife gerade steht, was bedeutet, dass man `compare(a[0], a[2]) == true` erhält, aber auch `compare(a[2], a[0]) == false`, sodass es scheint, als könne man aus dem Ergebnis von `compare` keine sinnvolle Bedeutung ziehen. Der andere ist, dass das Vergleichszeichen falsch herum ist.

    Irgendwie schaffen es diese beiden Gründe, warum es nicht funktionieren sollte, jedoch, so miteinander zu interagieren, dass sie sich genau gegenseitig aufheben und eine funktionierende Sortierung erzeugen!

  4. senfiaj

    Sieht nach suboptimalem Insertion Sort aus.

    Nach dem ersten Durchlauf der verschachtelten Schleife hat A[1] den größten Wert.

    Nach dem zweiten Durchlauf der verschachtelten Schleife wird A[1] immer mit A[2] getauscht (es sei denn, sie sind gleich, was logischerweise nichts ändert). A[2] enthält nun den größten Wert.

    Nach dem k-ten (k >= 2) Durchlauf der verschachtelten Schleife wird, wenn man aufpasst, das k-te Element in die ersten k-1 sortierten Elemente eingefügt. Wenn j >= i, kann es nichts mehr tun, da A[k] den größten Wert enthält.

    Nach dem k-ten (k >= 2) Durchlauf der verschachtelten Schleife sind die ersten k Elemente relativ zueinander sortiert. Der erste Durchlauf der verschachtelten Schleife ist besonders, da er das größte Element nach A[1] bringt; die nachfolgenden fügen einfach A[k] in die sortierten ersten k - 1 Elemente vom Anfang des Arrays ein.

  5. edflsafoiewq

    Früher (2021): https://news.ycombinator.com/item?id=28758106

Mehr von diesem Tag

2026-11-16