Gibt es schlechtere Sortieralgorithmen als Bogosort (auch bekannt als Monkey Sort)? [geschlossen]

Meine Mitarbeiter haben mich heute Morgen mit einer Diskussion über Sortieralgorithmen in die Zeit meiner Universität zurückversetzt. Wir erinnerten uns an unsere Favoriten wie StupidSort , und einer von uns war sich sicher, dass wir einen Sortieralgorithmus gesehen hatten O(n!). Das brachte mich dazu, mich nach den "schlechtesten" Sortieralgorithmen umzusehen, die ich finden konnte.

Wir postulierten, dass eine völlig zufällige Sortierung ziemlich schlecht wäre (dh die Elemente randomisieren - ist sie in Ordnung? Nein? Erneut randomisieren), und ich sah mich um und fand heraus, dass sie anscheinend BogoSort oder Monkey Sort oder manchmal nur Random Sort heißt .

Monkey Sort scheint eine Worst-Case-Leistung von O(∞), eine Best-Case-Leistung von O(n)und eine durchschnittliche Leistung von zu haben O(n·n!).

Was ist der derzeit offiziell akzeptierte Sortieralgorithmus mit der schlechtesten durchschnittlichen Sortierleistung (und daher schlechter als O(n·n!))?

Auf der Seite Esoterische Algorithmen von David Morgan-Mar : Intelligent Design Sort

Einführung

Intelligent Design Sort ist ein Sortieralgorithmus, der auf der Theorie des intelligenten Designs basiert.

Beschreibung des Algorithmus

Die Wahrscheinlichkeit, dass die ursprüngliche Eingabeliste genau in der Reihenfolge ist, in der sie sich befindet, beträgt 1 / (n!). Die Wahrscheinlichkeit dafür ist so gering, dass es eindeutig absurd ist zu sagen, dass dies zufällig passiert ist. Daher muss es von einem intelligenten Sortierer bewusst in diese Reihenfolge gebracht worden sein. Daher kann man davon ausgehen, dass es bereits in irgendeiner Weise optimal sortiert ist, die unser naives sterbliches Verständnis von "aufsteigender Ordnung" übersteigt. Jeder Versuch, diese Reihenfolge zu ändern, um sie unseren eigenen Vorurteilen anzupassen, würde sie tatsächlich weniger sortieren.

Analyse

Dieser Algorithmus ist zeitlich konstant und sortiert die Liste an Ort und Stelle, ohne dass zusätzlicher Speicher erforderlich ist. Tatsächlich erfordert es nicht einmal irgendetwas von diesem verdächtigen technologischen Computerzeug. Lobe den Sortierer!

Feedback

Gary Rogers schreibt:

Wenn die Sortierung zeitlich konstant gehalten wird, wird die Kraft von The Sorter verweigert. Der Sortierer existiert außerhalb der Zeit, daher ist die Sortierung zeitlos. Wenn Sie Zeit benötigen, um die Sortierung zu validieren, wird die Rolle des Sortierers verringert. Also ... diese besondere Art ist fehlerhaft und kann nicht 'The Sorter' zugeschrieben werden.

Ketzerei!

Vor vielen Jahren habe ich MiracleSort erfunden (aber nie implementiert).

Start with an array in memory.
loop:
    Check to see whether it's sorted.
    Yes? We're done.
    No? Wait a while and check again.
end loop

Schließlich sollten Alpha-Partikel, die Bits in den Speicherchips umdrehen, zu einer erfolgreichen Sortierung führen.

Kopieren Sie das Array für eine höhere Zuverlässigkeit an einen abgeschirmten Ort und vergleichen Sie potenziell sortierte Arrays mit dem Original.

Wie können Sie das potenziell sortierte Array mit dem Original vergleichen? Sie sortieren einfach jedes Array und prüfen, ob sie übereinstimmen. MiracleSort ist der naheliegende Algorithmus für diesen Schritt.

EDIT: Genau genommen ist dies kein Algorithmus, da nicht garantiert wird, dass er beendet wird. Qualifiziert sich "kein Algorithmus" als "schlechterer Algorithmus"?

Quantum Bogosort

Ein Sortieralgorithmus, der davon ausgeht, dass die Vielweltinterpretation der Quantenmechanik korrekt ist:

1. Überprüfen Sie, ob die Liste sortiert ist. Wenn nicht, zerstöre das Universum.

Am Ende des Algorithmus wird die Liste nach dem einzigen verbleibenden Universum sortiert. Dieser Algorithmus benötigt die Zeit für den schlechtesten Fall O (N) und den durchschnittlichen Fall O (1). Tatsächlich beträgt die durchschnittliche Anzahl der durchgeführten Vergleiche 2: Es besteht eine 50% ige Chance, dass das Universum beim zweiten Element zerstört wird, eine 25% ige Chance, dass es beim dritten Element zerstört wird, und so weiter.

Ich bin überrascht, dass noch niemand Schlafsort erwähnt hat ... Oder habe ich es nicht bemerkt? Wie auch immer:

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

Anwendungsbeispiel:

./sleepsort.sh 5 3 6 3 6 3 1 4 7
./sleepsort.sh 8864569 7

In Bezug auf die Leistung ist es schrecklich (insbesondere das zweite Beispiel). Fast 3,5 Monate auf das Sortieren von 2 Zahlen zu warten, ist ein bisschen schlecht.

Jingle Sort, wie hier beschrieben .

Sie geben jeden Wert in Ihrer Liste an Weihnachten einem anderen Kind. Kinder, die schreckliche Menschen sind, werden den Wert ihrer Gaben vergleichen und sich entsprechend sortieren.

Ich hatte einen Dozenten, der einmal vorschlug, ein zufälliges Array zu generieren, zu überprüfen, ob es sortiert war, und dann zu überprüfen, ob die Daten mit dem zu sortierenden Array übereinstimmten.

Bester Fall O (N) (erstes Mal Baby!) Schlimmster Fall O (Nie)

Wenn Sie den Algorithmus in irgendeiner Weise aussagekräftig halten, O(n!)ist dies die schlechteste Obergrenze, die Sie erreichen können.

Da das Überprüfen jeder Möglichkeit, ob Permutationen eines zu sortierenden Satzes sortiert werden, n!Schritte erfordert, können Sie nicht schlechter werden.

Wenn Sie mehr Schritte ausführen, hat der Algorithmus keinen wirklich nützlichen Zweck. Ganz zu schweigen von dem folgenden einfachen Sortieralgorithmus mit O(infinity):

list = someList
while (list not sorted):
    doNothing

Bogobogosort. Ja, das ist eine Sache. zu Bogobogosort, Sie Bogosort das erste Element. Überprüfen Sie, ob dieses eine Element sortiert ist. Als ein Element wird es sein. Dann fügen Sie das zweite Element hinzu und sortieren diese beiden Elemente, bis sie sortiert sind. Dann fügen Sie ein weiteres Element hinzu, dann Bogosort. Fügen Sie weitere Elemente und Bogosorting hinzu, bis Sie endlich alle Elemente ausgeführt haben. Dies sollte niemals mit einer umfangreichen Liste vor dem Hitzetod des Universums erfolgreich sein.

Sie sollten sich mit dem spannenden Gebiet der Pessimalalgorithmen und der Simplexitätsanalyse befassen . Diese Autoren arbeiten an dem Problem, eine Sorte mit einem pessimalen Best-Case zu entwickeln (der beste Fall Ihres Bogosort ist Omega (n), während Slowsort (siehe Artikel) eine nicht-polynomielle Best-Case-Zeitkomplexität aufweist).

Es gibt eine Sorte, die Bogobogosort heißt. Zuerst werden die ersten beiden Elemente überprüft und falsch sortiert. Als nächstes prüft es die ersten 3, vermasselt sie und so weiter.

Sollte die Liste zu irgendeinem Zeitpunkt nicht in Ordnung sein, wird sie neu gestartet, indem die ersten 2 erneut falsch sortiert werden. Normaler Bogosort hat eine durchschnittliche Komplexität von O(N!), dieser Algorithmus hat eine durchschnittliche Komplexität vonO(N!1!2!3!...N!)

Bearbeiten : Um Ihnen eine Vorstellung davon zu geben, wie groß diese Zahl für 20Elemente ist, benötigt dieser Algorithmus durchschnittlich 3.930093*10^158 Jahre , weit über dem vorgeschlagenen Hitzetod des Universums (falls er auftritt) von 10^100 Jahren .

Während die Zusammenführungssortierung ungefähr .0000004 Sekunden , die Blasensortierung .0000016 Sekunden und die Bogosortierung 308 Jahre , 139 Tage , 19 Stunden , 35 Minuten , 22.306 Sekunden dauert , vorausgesetzt, ein Jahr beträgt 365,242 Tage und ein Computer führt 250.000.000 32-Bit-Ganzzahloperationen pro Sekunde aus.

Edit2 : Dieser Algorithmus ist nicht so langsam wie die Wundersorte "Algorithmus", die wahrscheinlich wie diese Art den Computer in das Schwarze Loch saugt, bevor er erfolgreich 20 Elemente sortiert, aber wenn dies der Fall wäre, würde ich eine durchschnittliche Komplexität schätzen von 2^(32(the number of bits in a 32 bit integer)*N)(the number of elements)*(a number <=10^40) Jahren ,

Da die Schwerkraft die Alpha-Bewegung der Chips beschleunigt und es 2 ^ N Zustände gibt, was 2^640*10^40ungefähr 5.783*10^216.762162762 Jahren entspricht . Wenn die Liste jedoch sortiert beginnen würde, wäre ihre Komplexität nur O(N)schneller als die Zusammenführungssortierung, die nur N log N ist im schlimmsten Fall.

Edit3 : Dieser Algorithmus ist tatsächlich langsamer als die Wundersortierung, da die Größe sehr groß wird, beispielsweise 1000, da mein Algorithmus eine Laufzeit von 2.83*10^1175546 Jahren haben würde , während der Wundersortierungsalgorithmus eine Laufzeit von 1.156*10^9657 Jahren haben würde .

Hier sind 2 Sorten, die ich mir mit meinem Mitbewohner im College ausgedacht habe

1) Überprüfen Sie die Reihenfolge 2) Vielleicht ist ein Wunder passiert, gehen Sie zu 1

und

1) Überprüfen Sie, ob es in Ordnung ist, wenn nicht. 2) Fügen Sie jedes Element in ein Paket ein und leiten Sie es von einem entfernten Server an sich selbst zurück. Einige dieser Pakete werden in einer anderen Reihenfolge zurückgegeben. Fahren Sie daher mit 1 fort

Es gibt immer den Bogobogosort (Bogoception!). Es führt Bogosort für immer größere Teilmengen der Liste aus und beginnt dann von vorne, falls die Liste jemals nicht sortiert wird.

for (int n=1; n<sizeof(list); ++n) {
  while (!isInOrder(list, 0, n)) {
    shuffle(list, 0, n);
  }
  if (!isInOrder(list, 0, n+1)) { n=0; }
}

1 Legen Sie Ihre zu sortierenden Gegenstände auf Karteikarten.
2 Werfen Sie sie an einem windigen Tag, eine Meile von Ihrem Haus entfernt, in die Luft.
2 Wirf sie in ein Lagerfeuer und bestätige, dass sie vollständig zerstört sind.
3 Überprüfen Sie Ihren Küchenboden auf die richtige Bestellung.
4 Wiederholen Sie diesen Vorgang, wenn die Reihenfolge nicht korrekt ist.

Das beste Szenario ist O (∞)

Bearbeiten Sie oben basierend auf einer scharfsinnigen Beobachtung von KennyTM.

Das "Was soll es sein?" Sortieren

1. Notieren Sie die Systemzeit.
2. Sortieren Sie mit Quicksort (oder etwas anderem, das vernünftigerweise sinnvoll ist), ohne den allerletzten Tausch.
3. Notieren Sie die Systemzeit.
4. Berechnen Sie die erforderliche Zeit. Erweiterte Präzisionsarithmetik ist eine Voraussetzung.
5. Warten Sie die erforderliche Zeit.
6. Führen Sie den letzten Tausch durch.

Es kann nicht nur jeden denkbaren O (x) -Wert kurz vor unendlich implementieren, die benötigte Zeit ist nachweislich korrekt (wenn Sie so lange warten können).

Nichts kann schlimmer sein als unendlich.

Die Bozo-Sortierung ist ein verwandter Algorithmus, der prüft, ob die Liste sortiert ist, und wenn nicht, zwei Elemente nach dem Zufallsprinzip austauscht. Es hat die gleichen besten und schlechtesten Leistungen, aber ich würde intuitiv erwarten, dass der durchschnittliche Fall länger ist als Bogosort. Es ist schwierig, Daten zur Leistung dieses Algorithmus zu finden (oder zu produzieren).

Segmente von π

Angenommen, π enthält alle möglichen endlichen Zahlenkombinationen. Siehe math.stackexchange-Frage

1. Bestimmen Sie die Anzahl der benötigten Stellen anhand der Größe des Arrays.
2. Verwenden Sie Segmente von π-Stellen als Indizes, um zu bestimmen, wie das Array neu angeordnet werden soll. Wenn ein Segment die Größengrenzen für dieses Array überschreitet, passen Sie den π-Dezimalversatz an und beginnen Sie von vorne.
3. Überprüfen Sie, ob das neu geordnete Array sortiert ist. Wenn es woot ist, passen Sie den Versatz an und beginnen Sie von vorne.

Eine Worst-Case-Leistung von O (∞) macht es nach einigen möglicherweise nicht einmal zu einem Algorithmus .

Ein Algorithmus besteht nur aus einer Reihe von Schritten, und Sie können immer schlechter abschneiden, indem Sie ihn ein wenig optimieren, um die gewünschte Ausgabe in mehr Schritten als zuvor zu erhalten. Man könnte absichtlich das Wissen über die Anzahl der Schritte in den Algorithmus einfließen lassen und ihn erst dann beenden und die richtige Ausgabe erzeugen, Xwenn die Anzahl der Schritte ausgeführt wurde. Das Xkönnte sehr gut in der Größenordnung von O (n ² ) oder O (n ^n! ) Liegen oder was auch immer der Algorithmus tun wollte. Dies würde sowohl die Best-Case- als auch die durchschnittlichen Fallgrenzen effektiv erhöhen.

Aber dein Worst-Case-Szenario kann nicht übertroffen werden :)

Mein bevorzugter langsamer Sortieralgorithmus ist die Handlanger-Sortierung:

void stooges(long *begin, long *end) {
   if( (end-begin) <= 1 ) return;
   if( begin[0] < end[-1] ) swap(begin, end-1);
   if( (end-begin) > 1 ) {
      int one_third = (end-begin)/3;
      stooges(begin, end-one_third);
      stooges(begin+one_third, end);
      stooges(begin, end-one_third);
   }
}

Die schlimmste Komplexität ist O(n^(log(3) / log(1.5))) = O(n^2.7095...).

Ein anderer langsamer Sortieralgorithmus heißt eigentlich slowsort!

void slow(long *start, long *end) {
   if( (end-start) <= 1 ) return;
   long *middle = start + (end-start)/2;
   slow(start, middle);
   slow(middle, end);
   if( middle[-1] > end[-1] ) swap(middle-1, end-1);
   slow(start, end-1);
}

Dieser nimmt O(n ^ (log n))im besten Fall ... sogar langsamer als Handlanger.

Recursive Bogosort (probably still O(n!){
if (list not sorted)
list1 = first half of list.
list 2 = second half of list.
Recursive bogosort (list1);
Recursive bogosort (list2);
list = list1 + list2
while(list not sorted)
    shuffle(list);
}

Diese Seite ist eine interessante Lektüre zum Thema: http://home.tiac.net/~cri_d/cri/2001/badsort.html

Mein persönlicher Favorit ist Tom Duffs Dummkopf:

/*
 * The time complexity of this thing is O(n^(a log n))
 * for some constant a. This is a multiply and surrender
 * algorithm: one that continues multiplying subproblems
 * as long as possible until their solution can no longer
 * be postponed.
 */
void sillysort(int a[], int i, int j){
        int t, m;
        for(;i!=j;--j){
                m=(i+j)/2;
                sillysort(a, i, m);
                sillysort(a, m+1, j);
                if(a[m]>a[j]){ t=a[m]; a[m]=a[j]; a[j]=t; }
        }
}

Doppelter Bogosort

Bogosort zweimal und vergleiche die Ergebnisse (nur um sicherzugehen, dass sie sortiert sind), wenn du es nicht noch einmal machst

Sie können jeden Sortieralgorithmus verlangsamen, indem Sie Ihren Schritt "Ist es sortiert" zufällig ausführen. Etwas wie:

1. Erstellen Sie ein Array von Booleschen Werten, die dieselbe Größe haben wie das Array, das Sie sortieren. Setzen Sie sie alle auf false.
2. Führen Sie eine Iteration von Bogosort aus
3. Wähle zwei zufällige Elemente aus.
4. Wenn die beiden Elemente relativ zueinander sortiert sind (i <j && array [i] <array [j]), markieren Sie die Indizes beider Elemente im booleschen Array mit true. Beginnen Sie von vorne.
5. Überprüfen Sie, ob alle Booleschen Werte im Array wahr sind. Wenn nicht, gehen Sie zurück zu 3.
6. Getan.

Ja, SimpleSort, theoretisch läuft es in, O(-1)aber dies ist äquivalent zu,O(...9999) was wiederum äquivalent zu O (∞ - 1) ist, was zufällig auch äquivalent zu O (∞) ist. Hier ist meine Beispielimplementierung:

/* element sizes are uneeded, they are assumed */
void
simplesort (const void* begin, const void* end)
{
  for (;;);
}

Eine, an der ich gerade gearbeitet habe, besteht darin, zwei zufällige Punkte auszuwählen und, wenn sie in der falschen Reihenfolge sind, den gesamten Unterbereich zwischen ihnen umzukehren. Ich habe den Algorithmus unter http://richardhartersworld.com/cri_d/cri/2001/badsort.html gefunden , der besagt, dass der durchschnittliche Fall wahrscheinlich irgendwo um O (n ^ 3) oder O (n ^ 2 log n) liegt ( er ist sich nicht wirklich sicher).

Ich denke, es könnte möglich sein, es effizienter zu machen, weil ich denke, dass es möglich sein könnte, die Umkehroperation in O (1) -Zeit durchzuführen.

Eigentlich habe ich gerade gemerkt, dass dies das Ganze ausmachen würde, was ich vielleicht sage, weil ich gerade realisiert habe, dass die Datenstruktur, an die ich gedacht habe, den Zugriff auf die zufälligen Elemente bei O (log n) und die Bestimmung, ob sie bei O (n umgekehrt werden muss) ermöglichen würde ).

Randomsubsetsort.

Wählen Sie bei einem Array von n Elementen jedes Element mit einer Wahrscheinlichkeit von 1 / n aus, ordnen Sie diese Elemente zufällig zu und prüfen Sie, ob das Array sortiert ist. Wiederholen, bis sortiert.

Die erwartete Zeit bleibt dem Leser als Übung.