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

177

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!))?

womp
quelle
10
Wie viele Bogomips pro Bogosort? Neugierige wollen es wissen.
Zombat
13
Schließen Sie zur Verdeutlichung den trivialen Fall aus, in dem die beste Fallleistung O (∞) ist?
Tloflin
6
Ich habe gehört, dass die Affensorte auch als "Trunkenbold-Sorte" bekannt ist, ein Name, den ich viel eindrucksvoller finde.
Matteo Italia
6
@Matteo Italia - oder es könnte "Toddler Sort" genannt werden, wie jeder mit 2 Jahren bezeugen kann.
Martin Capodici

Antworten:

442

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!

BioGeek
quelle
94
Auch bekannt als "Assumption Sort": Angenommen, die Liste ist sortiert, return!
BioGeek
42
+100 - Diese Antwort besteht aus 100% reinem Gewinn.
Womp
11
Hallo! Vergessen Sie nicht "Unentschlossene Sortierung" (auch als "Schrödingers Sortierung" oder "Quantensortierung" bekannt), bei der die Liste sortiert sein kann oder nicht. Wenn Sie sie jedoch überprüfen, wird angezeigt, ob dies der Fall ist oder nicht. Hier ist meine Beispielimplementierung : void quantum_sort (void *b, size_t n, size_t s, int (*c)(const void *, const void*)) { if (rand () % 2) qsort (b, n, s, c); }.
Joe D
6
Wir sollten diese Candide-Sorte synchronisieren :"This is the best of all posibble worlds because it is the world that is, and so in the best possible world the array would already be sorted!"
Echochamber
2
Zum einen begrüße ich unseren neuen Sortier-Overlord. Alle begrüßen den Sortierer!
Bryson
298

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"?

Keith Thompson
quelle
39
Ich gehe davon aus, dass man kosmische Strahlung verwenden kann, um die Richtigkeit dieses Algorithmus zu beweisen.
Ghord
1
Was ist das große O davon? O(2^N)?
Mooing Duck
12
@MooingDuck: Ich glaube nicht, dass es tatsächlich ein großes O. hat
Keith Thompson
5
@MooingDuck: Genau genommen ist es kein Algorithmus, wenn es nicht beendet wird, sowohl nach dem, was sie mir im College beigebracht haben, als auch nach dem Wikipedia-Artikel .
Keith Thompson
7
@Olathe: Das Halteproblem besagt, dass wir nicht für alle Programme bestimmen können, ob sie anhalten, aber es gibt viele Programme, für die wir diese Bestimmung treffen können. Wir wissen, dass Quicksort und Bubblesoft anhalten, und wir wissen, dass es sich um Algorithmen handelt.
Keith Thompson
132

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.

BioGeek
quelle
42
Aber in dem Universum, das du gerade zerstört hast, hört die Zeit auf zu existieren. Ein Beobachter in einem Universum, den Sie noch nicht überprüft haben, kann also nicht sagen, wie viel des Algorithmus ausgeführt wurde. Daher benötigt dieser Algorithmus immer O (1) Zeit, da frühere Universumszerstörungen nicht mehr existieren.
Barry Brown
12
Ja, in dem einzigen Universum, das die Liste sortiert beobachtet, dauerte die Ausführung O (n) Zeit - wie lange es in anderen Universen gedauert hat, ist irrelevant.
Nick Johnson
19
Dieser Algorithmus hat jedoch ein viel größeres Problem. Angenommen, Sie werden fälschlicherweise zu dem Schluss kommen, dass eine Liste sortiert ist, wenn dies nicht der Fall ist. Es sind 20! Möglichkeiten zum Sortieren einer Liste mit 20 Elementen. Nach der Sortierung sind die verbleibenden Universen diejenigen, in denen die Liste korrekt sortiert wurde, und die 2,4 Millionen Universen, in denen der Algorithmus fälschlicherweise zu dem Schluss kam, dass die Liste korrekt sortiert wurde. Was Sie hier haben, ist ein Algorithmus zum massiven Vergrößern der Fehlerrate eines Maschinenstücks.
Nick Johnson
10
Dies ist offensichtlich der beste Sortieralgorithmus, nicht der schlechteste.
Boann
11
Wenn Sie den Rat des Käfers nicht befolgen, können alle Universen zerstört werden.
CrashCodes
60

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.

Kw4s
quelle
3
Dies scheint eine O(N)Art zu sein, wird aber in Wahrheit dadurch eingeschränkt, dass das Betriebssystem Timer implementiert.
Mooing Duck
7
Wie auch immer Sie es schneiden, dies zeigt wahrscheinlich ein besseres Wachstum als Bogosort.
Mooing Duck
8
Ich sehe dort eine Rennbedingung.
5
Sie können das ändern sleep "$1", sleep "0.$(printf "%010d" $1)"um die Leistung deutlich zu verbessern. time ./sleepsort.sh 8864569 7läuft dann in 0,009s auf meinem Laptop.
Sam Kellett
1
Dies läuft in O (N) -Komplexität (natürlich abhängig von der Implementierung des Timers), es ist eine einfache Bucket-Sortierung in unterschiedlicher Form.
Qwerty01
60

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.

Curtis Lassam
quelle
50

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)

Daniel
quelle
4
Interessanter zu analysieren ist der Durchschnittsfall , der ...?
Mooing Duck
4
Wie die besten Lehrbücher sagen, bleibt dies eine Übung für den Leser!
Daniel
40
Mooing Duck: O (manchmal)
Ilya O.
1
@MooingDuck dann müssen wir die Kardinalität des Elementtyps und der Verteilung kennen, die zum Generieren zufälliger Elemente in zufälligen Arrays verwendet werden.
Anzeigename
5
Die Komplexität ist O (N! * Z ^ N), wobei Z die Größe der Menge möglicher Werte und N die Länge des Arrays ist.
Jakubiszon
30

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
Yuval Adam
quelle
14
Aber es braucht O (n), um zu überprüfen, ob es sortiert ist, damit Sie O (n * n!)
erikkallen
3
@erikkallen: Natürlich können wir einen Algorithmus entwickeln, um die Sortierung zu überprüfen, die schlechter als O (n) ist. Stellen Sie beispielsweise für jedes Element im Array sicher, dass es größer als alle vorherigen Elemente ist, ähnlich wie beim Einfügen. Das ist ein O (n ^ 2) -Algorithmus, und ich bin sicher, ich könnte mir bei ein wenig Überlegung etwas Schlimmeres einfallen lassen.
David Thornley
7
@ David Thornley: Der folgende Überprüfungsalgorithmus würde möglicherweise den gleichen Geist wie der Bogosort zeigen: Wählen Sie zwei zufällige Elemente aus, überprüfen Sie, ob das mit dem kleineren Index kleiner oder gleich dem mit dem größeren Index ist, und wiederholen Sie dann. Behalten Sie eine quadratische Bitmatrix bei, um zu sehen, welche Kombinationen bereits überprüft wurden. Natürlich könnte die Überprüfung dieser Matrix auch in einem zufälligen Spaziergang erfolgen ...
Svante
19

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.

Playnwinplayer
quelle
5
Heilige Mutter des Codes. Ich denke, wir können sogar einen Bogolplex-Kurzfilm machen.
MrKekson
19

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

Derrick Turk
quelle
19

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 .

Kolibri
quelle
1
tolle Antwort. traurig, dass es keine Sichtbarkeit hat
swyx
16

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

Seth
quelle
Die zweite ist fast das Äquivalent einer Bozo-Sorte. Das erste ist allerdings klug.
Mooing Duck
1
Das erste ist Miracle Sort.
Charles
14

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; }
}
IceMetalPunk
quelle
5
Ich mag die Idee, dass dieser Algorithmus so konzipiert ist, dass er "vor dem Hitzetod des Universums für eine beträchtliche Liste" niemals beendet wird
A.Grandt
10

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.

Patrick Karcher
quelle
9
Nein, das ist schlimmer, weil es keine Chance gibt, dass es gelingt. Wie würden die Karteikarten in Ihre Küche gelangen? Sie blasen draußen herum. Es heißt, ähm, Buttheadsort.
Patrick Karcher
Ich denke, er meint, die Karten draußen in die Luft zu werfen und dann drinnen den Boden zu überprüfen , wo es garantiert keine Karten gibt. Obwohl kein "benannter" Algorithmus ... ist es sicherlich schlimmer!
Womp
10
@ Patrick Quantentunneln.
Kennytm
8
@ KennyTM. Das war mir tatsächlich eingefallen. Es besteht eine äußerst geringe Wahrscheinlichkeit, dass ein Objekt an jedem anderen Punkt im Universum verschwindet und wieder auftaucht. Ich denke, es könnte tausend Karteikarten passieren. . . Oi. Verdammt, mein Algorithmus ist fehlerhaft . Ich werde es reparieren . . .
Patrick Karcher
3
Es ist so, als würde man gleichzeitig Tee und keinen Tee trinken. Oder Raumfahrt mit einem unendlichen Unwahrscheinlichkeitsantrieb.
Barry Brown
9

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

david.pfx
quelle
8

Nichts kann schlimmer sein als unendlich.

Joseph Salisbury
quelle
38
Unendlichkeit + 1. Jinx, keine Rückkehr.
Zombat
24
Nicht für extrem große Werte von 1;)
Zombat
8
Was mich an dem Konzept der Unendlichkeit wirklich beeindruckt, ist, dass man verschiedene "Größen" der Unendlichkeit haben kann. Betrachten Sie zum Beispiel die Menge aller ganzen Zahlen - sie ist unendlich groß. Betrachten Sie nun die Menge aller geraden ganzen Zahlen - sie ist ebenfalls unendlich groß, aber eindeutig halb so groß wie die erste Menge. Beide unendlich, aber unterschiedlich groß. So genial. Das Konzept der "Größe" funktioniert im Kontext der Unendlichkeit einfach nicht.
Zombat
4
@zombat: Sie sprechen von Kardinalität, nicht von Unendlichkeit als Symbol für einen Trend auf der realen Linie / komplexen Ebene.
Kennytm
18
@ Zombat. Die Größe des Satzes gerader Ganzzahlen entspricht der Größe des Satzes der Ganzzahlen, wie die Tatsache zeigt, dass Sie sie in einer Eins-zu-Eins-Korrespondenz platzieren können. Jetzt gibt es mehr reelle Zahlen als ganze Zahlen, wie Cantor zuerst gezeigt hat.
David Thornley
5

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

tloflin
quelle
5

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.
CrashCodes
quelle
4

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 2 ) 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 :)

Anurag
quelle
3

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.

Ben Goldberg
quelle
3
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);
}
Benutzer3667082
quelle
2

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; }
        }
}
fsanches
quelle
2

Doppelter Bogosort

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

Viktor Mellgren
quelle
1

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.
Brendan Long
quelle
1

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 (;;);
}
Joe D.
quelle
1

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

AJMansfield
quelle
1

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.

Steven Armstrong
quelle