Einführung
Bei dieser Herausforderung geht es um drei (schlechte) Sortieralgorithmen: Bogosort
und zwei weitere Varianten, die ich mir ausgedacht habe (an die ich aber wahrscheinlich irgendwann gedacht habe): Bogoswap
(AKA Bozosort) und Bogosmart
.
Bogosort
funktioniert, indem das Array vollständig zufällig gemischt und überprüft wird, ob es sortiert wird (aufsteigend). Wenn nicht, wiederholen.
Bogoswap
funktioniert, indem zwei Elemente zufällig ausgewählt und ausgetauscht werden. Wiederholen, bis sortiert (aufsteigend).
Bogosmart
funktioniert, indem zwei Elemente zufällig ausgewählt und nur dann ausgetauscht werden, wenn das Array näher an der Sortierung (aufsteigend) liegt, d. h. wenn das Element mit dem niedrigeren Index ursprünglich größer war als das mit dem höheren. Wiederholen, bis sortiert.
Die Herausforderung
Diese Herausforderung untersucht die Effizienz (oder das Fehlen) jedes dieser drei Sortieralgorithmen. Der Golfcode wird
Generieren Sie ein gemischtes 8-Element-Array der Ganzzahlen 1-8 einschließlich (lesen Sie weiter, um zu sehen, wie Sie dies tun sollten).
Wenden Sie jeden Algorithmus auf dieses Array an. und
Zeigen Sie das ursprüngliche Array an, gefolgt von der Anzahl der für jeden Algorithmus erforderlichen Berechnungen, getrennt durch ein Leerzeichen (nachfolgendes Leerzeichen ok) im Format
<ARRAY> <BOGOSORT> <BOGOSWAP> <BOGOSMART>
.
Das Programm wird 10 Testfälle erstellen; Sie können alle zehn am Anfang oder einzeln generieren, was auch immer. Beispielausgabe unten.
Einzelheiten:
Denn Bogosort
es sollte aufzeichnen, wie oft das Array gemischt wurde.
Denn Bogoswap
es sollte die Anzahl der getätigten Swaps aufzeichnen.
Denn Bogosmart
es sollte die Anzahl der getätigten Swaps aufzeichnen.
Beispielausgabe:
87654321 1000000 100 1
37485612 9050000 9000 10
12345678 0 0 0
28746351 4344 5009 5
18437256 10000 523 25
15438762 10000 223 34
18763524 58924 23524 5
34652817 9283 21 445
78634512 5748 234 13
24567351 577 24 34
Ich habe diese Zahlen erfunden; Natürlich druckt Ihr Programm unterschiedliche Ausgaben, jedoch im gleichen Format.
Regeln
- Alle in Ihrem Programm verwendeten Zufälligkeiten müssen von Pseudozufallszahlengeneratoren stammen, die Ihnen zur Verfügung stehen und ansonsten von Ihnen nicht umfassend berechnet werden. Sie müssen sich keine Sorgen um Samen machen.
- Es gibt keine zeitliche Begrenzung für die Programme.
- Die Arrays sind aufsteigend zu sortieren.
- Nachgestellte Leerzeichen oder ein zusätzlicher Zeilenumbruch sind keine große Sache.
- Denn
Bogosort
das Array muss mit einem beliebigen unvoreingenommenen Mischalgorithmus wie Fisher-Yates oder Knuth Shuffling gemischt werden , der in Ihrer Erklärung explizit angegeben ist. Eingebaute Mischmethoden sind nicht zulässig. Generieren Sie Ihre Testarrays auf die gleiche Weise. - Wenn das Array nach dem Mischen oder Austauschen gleich bleibt, zählt es weiterhin und sollte in die Programmanzahl einbezogen werden. Beispielsweise zählt das zufällige Mischen des Arrays zu sich selbst als Mischen, und das Austauschen eines Elements mit sich selbst gilt als Austausch, obwohl keine dieser Operationen das Array ändert.
- Wenn mein Speicher mir richtig dient, sollte ein 8-Elemente-Array für keinen der drei Algorithmen zu lange dauern. Tatsächlich denke ich, dass ein paar Mal für ein 10-Elemente-Array, als ich es ausprobierte,
Bogoswap
nur ein paar tausend (oder weniger) tatsächliche Mischvorgänge und weit weniger als 10 Sekunden erforderlich waren. - Ihr Code muss die Arrays tatsächlich sortieren und nicht nur erwartete Werte oder mathematische Berechnungen für eine erwartete Antwort angeben.
- Dies ist eine Code-Golf-Herausforderung, sodass das kürzeste Programm in Bytes gewinnt.
Hier sind einige Beispielschritte für jeden Sortieralgorithmus:
BOGOSORT
56781234
37485612
28471653
46758123
46758123
12685734
27836451
12345678
BOGOSWAP
56781234
16785234
17685234
12685734
12685743
12685734
12485763
12385764
12385764
12345768
12345678
BOGOSMART
56781234
16785234
12785634
12785364
12785364
12385764
12385674
12345678
In diesem Fall würde das Programm ausgeben 56781234 7 10 7
und dann zehnmal dasselbe tun. Sie müssen die Arrays nicht drucken, während die Sortierung ausgeführt wird, aber ich habe die obigen Beispielschritte angegeben, damit Sie verstehen, wie jeder Algorithmus funktioniert und wie Berechnungen gezählt werden.
Antworten:
Pyth,
6260 BytesDas hat sehr viel Spaß gemacht. Ich bin mir nicht sicher, ob dies gültig ist. Ich verwende wahrscheinlich einige ungeschriebene Lücken.
Eine Beispielausgabe wäre:
Erläuterung:
Meine Shuffle-Funktion verwendet die eingebaute Funktion
order-by
. Grundsätzlich ordne ich jedem Element der Liste eine Zufallszahl des Intervalls zu[0-1)
und sortiere die Liste nach ihnen. Dies gibt mir ein unvoreingenommenes zufälliges Mischen.Äußere Schleife
Der
VT
zu Beginn wiederholt den folgenden Code 10 Mal.Vorbereitung
Bogosort
Bogoswap
Bogosmart
Drucken
quelle
=JXJO.cJ2)
ist das gleiche wie=XJO.cJ2)
- erweiterte Zuordnung. Gleiches gilt für=bXb
später. Ich denke auch, dass Swaps die Paare mit Ersatz (.C
).c
oder.C
erlaubt sind. Zum Beispiel.C[3 1 2)2
gibt das Paar nicht zurück[2, 1]
. Welches ist eine Eigenschaft, die ich in meinem Algorithmus ausnutze.*JJ
dann? Es ist auch ein Zeichen kürzer, was schön ist.JavaScript ( ES6 ), 319
345Es überrascht nicht, dass dies ziemlich lang ist.
Für Random Shuffle wird @ core1024 gutgeschrieben (besser als meins für das gleiche Chellenge)
Testen Sie das Snippet (Firefox nur wie gewohnt)
quelle