Was ist der obskurste Sortieralgorithmus, den Sie kennen? [geschlossen]

22

Ich habe gerade über einen sortvis.org-Blog-Beitrag über Cyclesort gelesen . Dies ist wahrscheinlich das dunkelste, von dem ich bisher gehört habe, da es Mathematik verwendet, mit der ich nicht vertraut bin (Erkennen von Zyklen in Permutationen von Ganzzahlensätzen).

Was ist das dunkelste, das du kennst?

sova
quelle
4
Muss zurückkommen, um zu lesen.
Mark C
Gutes Timing, meine Datenstrukturklasse hat gerade angefangen, Sortierungen abzudecken. Jetzt verstehe ich nicht nur die grundlegenden Arten, sondern auch die verrückten.
Jason

Antworten:

9

Schon mal was von Geduldssortierung gehört ? Na jetzt hast du ...

Mason Wheeler
quelle
1
Interessanterweise verwendet Bazaar es, um Zusammenschlüsse zu lösen.
Tim Post
12

Slowsort funktioniert durch Multiplizieren und Aufgeben (im Gegensatz zu Teilen und Erobern). Es ist interessant, weil es nachweislich der am wenigsten effiziente Sortieralgorithmus ist, der erstellt werden kann (asymptotisch und mit der Einschränkung, dass ein solcher Algorithmus, obwohl er langsam ist, die ganze Zeit auf ein Ergebnis hinarbeiten muss).

Dies gleicht es von Bogosort aus, da Bogosort im besten Fall sehr effizient ist - und zwar, wenn das Array bereits sortiert ist. Slowsort „leidet“ nicht unter einem solchen Best-Case-Verhalten. Es hat auch im besten Fall noch Laufzeit $ \ Omega (n ^ \ frac {\ log_2n} {2+ \ epsilon}) $ für ϵ > 0.

Hier ist der Pseudocode aus dem Wikipedia-Artikel :

function slowsort(A, i, j):
  if i >= j: return

  m = (i + j) / 2
  slowsort(A, i, m)
  slowsort(A, m + 1, j)

  if A[j] < A[m]:
    swap(A[j], A[m])

  slowsort(A, i, j - 1)
Konrad Rudolph
quelle
1
Bogosort kann im besten Fall trivial pessimaler gemacht werden, indem man die Reihenfolge seiner Schritte umkehrt: zuerst mischen. Wenn sortiert, dann hör auf.
Alex Feinman
3
@Alex: nein. Das ändert nichts. Bogosort wäre nach dem ersten Schritt noch fertig, da das Mischen die Reihenfolge zufällig sortiert hätte. Bogosort zeigt immer noch ein ausgeprägtes Best-Case-Verhalten mit einer grundlegend anderen Laufzeit (O (n)) als im Worst-Case- und Durchschnittsfall. Slowsort hat das einfach nicht.
Konrad Rudolph
Ah, ich habe nur an Anfangsbedingungen gedacht, nicht an Ausführungspfade!
Alex Feinman
Liebe dies :) Nichts wie rohe Gewalt ...
8

Ich weiß nicht, ob dies als obskur gilt, aber einer der lächerlichsten "Sortieralgorithmen" ist Bogosort . Die Links von der Bogosort-Seite machen auch Spaß.

Und da ist dieses Juwel aus der Sektion "Quanten-Bogo-Sort".

Das Erstellen von 2 N- Universen ist wahrscheinlich auch sehr speicherintensiv.

Hmmm ... das könnte man so sagen :-).

Stephen C
quelle
Ich mag dieses. Mir gefällt besonders die Idee von "Quantum bogosort" :-)
Dean Harding
6

Ein anderer obskurer "Algorithmus" ist Intelligent Design Sort - aber kein Algorithmus ist schneller oder hat einen geringeren Speicherverbrauch :)

Caspar
quelle
Eine der besten Eigenschaften dieses Algorithmus ist, dass wir nur wissen, dass er funktioniert - es ist nicht erforderlich, etwas zu analysieren oder zu beweisen.
Caleb
6

Sleep Sort ist ziemlich neuartig.

    #!/bin/bash
    function f() {
        sleep "$1"
        echo "$1"
    }
    while [ -n "$1" ]
    do
        f "$1" &
        shift
    done
    wait

Beispielverwendung:

    ./sleepsort.bash 5 3 6 3 6 3 1 4 7
Mike Weller
quelle
5

Ich denke, die Blasenart wäre auch in dieser Situation die falsche Antwort

:)

OscarRyz
quelle
3

Knuth Volume 3 1 enthält in der Antwort auf eine der Übungen eine Implementierung eines namenlosen Sortieralgorithmus, der im Grunde genommen ein uralter Codegolf ist - die kürzeste Sortierung, die Sie in der MIX-Assemblersprache schreiben können. Der Kurzcode ist allerdings für den ach so geringen Preis von O (N 3 ) -Komplexität erhältlich ...

1 Zumindest in den älteren Ausgaben. Angesichts der Änderungen an MIXAL für die neue Edition bin ich mir nicht sicher, ob es noch vorhanden ist oder ob es überhaupt Sinn macht, was im Original-MIXAL passiert ist.

Jerry Sarg
quelle
3

Für meine Datenstrukturklasse musste ich (explizit) die Korrektheit der Stooge-Sortierung nachweisen . Es hat eine Laufzeit von O (n ^ {log 3 / log 1,5}) = O (n ^ 2,7095 ...).

Alex ten Brink
quelle
2

Ich weiß nicht, ob es die dunkelste ist, aber Spaghetti-Sorte ist eine der besten in Situationen, in denen Sie sie verwenden können.

Caleb
quelle
Dies ähnelt in seiner Idee der „Schlaf-Sortierung“ und wird interessanterweise in der Bioinformatik zur Sequenzierung von DNA (Sanger-Sequenzierung) verwendet.
Konrad Rudolph
2

Eines der ursprünglichen Bücher von Knuth, "Sortieren und Suchen", hatte eine mittlere Ausklappung, die einen Vorgang zeigte, bei dem eine Banddatei ohne Festplatte sortiert wurde. Ich denke, es wurden sechs Bandlaufwerke verwendet, und es wurde explizit gezeigt, wann jedes vorwärts, rückwärts, rückwärts oder im Leerlauf gelesen wurde. Heute ist es ein Denkmal für eine veraltete Technologie.

Andy Canfield
quelle
1

Ich habe einmal eine Blasensortierung in Vektorregistern in CRAY Assembler durchgeführt. Die Maschine hatte einen Doppelschiebebefehl, mit dem Sie den Inhalt eines Vektorregisters um ein Wort nach oben / unten verschieben konnten. Tragen Sie jeden zweiten Punkt in zwei Vektorregister ein, dann können Sie eine vollständige Blasensortierung durchführen, ohne jemals eine weitere Speicherreferenz erstellen zu müssen, bis Sie fertig sind. Mit Ausnahme des N ** 2-Charakters der Blasensorte war es effizient.

Ich musste auch einmal eine Gleitkomma-Sortierung eines Vektors der Länge 4 für eine einzelne Sortierung so schnell wie möglich durchführen. Haben Sie es durch Tabellensuche gemacht (das Vorzeichenbit von A2-A1 ist ein Bit, das Vorzeichen von A3-A1 bildet ein anderes Bit ..., dann suchen Sie den Permutationsvektor in einer Tabelle nach. Es war tatsächlich die schnellste Lösung, die ich finden konnte Funktioniert auf modernen Architekturen jedoch nicht gut, da Floating- und Integer-Einheiten zu getrennt sind.

Omega Centauri
quelle
Haben Sie noch die Quelle dafür? Ich würde es gerne ausprobieren!
Sova
Keine Quelle, es handelte sich um eine nicht veraltete Maschine für ein Unternehmen, das mich letztendlich entlassen hat. Die Tabellensuche ist nicht schwer: sb1 = 1 & ((a2-a1) >> 63); sb2 = 2 & ((a3-a1) >> 62); ... index = sb1 | sb2 | sb3 ... gefolgt durch eine Tabellensuche der Bestellung.
Omega Centauri
1

Google Code Jam hatte ein Problem mit einem Algorithmus namens Gorosort, den sie meiner Meinung nach für dieses Problem erfunden haben.

Goro hat 4 Arme. Goro ist sehr stark. Du legst dich nicht mit Goro an. Goro muss ein Array von N verschiedenen Ganzzahlen sortieren. Algorithmen sind nicht Goros Stärke; Stärke ist Goros Stärke. Goros Plan ist es, mit den Fingern an zwei Händen mehrere Elemente des Arrays festzuhalten und mit der dritten und vierten Faust so fest wie möglich auf den Tisch zu schlagen. Dadurch werden die ungesicherten Elemente des Arrays in die Luft geschleudert, werden zufällig gemischt und fallen zurück in die leeren Array-Positionen.

http://code.google.com/codejam/contest/dashboard?c=975485#s=p3

MatrixFrog
quelle
0

Ich erinnere mich nicht an den Namen, aber es war im Grunde genommen

while Array not sorted

  rearrange the array in a random order
Akash
quelle
Dies ist Bogosort, wie in anderen Antworten erwähnt.
MatrixFrog
0

Shell sortieren

Vielleicht ist der Algorithmus selbst nicht so dunkel, aber wer kann eine Implementierung nennen, die tatsächlich in der Praxis verwendet wird? Ich kann!

TIGCC (ein GCC-basierter Compiler für TI-89/92 / V200-Grafikrechner) verwendet die Shell-Sortierung für die qsortImplementierung in seiner Standardbibliothek:

__ATTR_LIB_C__ void qsort(void *list, short num_items, short size, compare_t cmp_func)
{
  unsigned short gap,byte_gap,i,j;                
  char *p,*a,*b,temp;                       
  for (gap=((unsigned short)num_items)>>1; gap>0; gap>>=1)    // Yes, this is not a quicksort,
    {                                                         // but works fast enough...    
      byte_gap=gap*(unsigned short)size;
      for(i=byte_gap; i<((unsigned short)num_items)*(unsigned short)size; i+=size)
        for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap)
          {
            a=p; b=p+byte_gap;
            if(cmp_func(a,b)<=0) break;
            for(j=size;j;j--)
              temp=*a, *a++=*b, *b++=temp;
          }
    }
}

Shell-Sortierung wurde zugunsten von QuickSort gewählt, um die Codegröße niedrig zu halten. Obwohl die asymptotische Komplexität schlechter ist, verfügt der TI-89 nicht über viel RAM (190 KB, abzüglich der Programmgröße und der Gesamtgröße aller nicht archivierten Variablen), sodass davon auszugehen ist, dass die Anzahl der Elemente größer ist niedrig sein.

Eine schnellere Implementierung wurde geschrieben, nachdem ich mich darüber beschwert hatte, dass es in einem Programm, das ich schrieb, zu langsam sei. Es werden bessere Spaltgrößen sowie Optimierungen der Baugruppe verwendet. Es kann hier gefunden werden: qsort.c

Joey Adams
quelle