Bogosort
Wir haben in vielen verschiedenen Aufgaben bereits mit sortierten Listen gearbeitet und dafür unter anderem die eingebauten Sortierfunktionen verwendet. Wie diese Funktionen im Hintergrund tatsächlich arbeiten, ist jedoch nicht unbedingt offensichtlich. In diesem Kapitel beschäftigen wir uns mit einigen bekannten Sortieralgorithmen, die – je nach Anwendung – an unterschiedlichen Stellen zum Einsatz kommen.
Der erste Algorithmus, den wir uns genauer anschauen, ist der wohl absurdeste aller Sortieralgorithmen: Bogosort. In realen Anwendungen findet er keine Verwendung, und mit gutem Grund – das wird sich gleich zeigen.
Wenn wir
n Zahlen haben, funktioniert der Algorithmus, indem er die Liste immer wieder per Zufall neu mischt und anschließend prüft, ob sie sortiert ist:from random import shuffle
a = [3, 1, -2, 5, 6] # Anfangswerte
while True: # Schleife, bis das Array sortiert ist
is_sorted = True
for i in range(1, len(a)): # Eine Schleife, um zu prüfen, ob das Array sortiert ist
if a[i] < a[i-1]: # Wenn wir ein Element finden, das kleiner ist als das vorherige => es ist nicht sortiert
is_sorted = False # Wir setzen die Variable auf False und beenden die Schleife
break
if is_sorted: # Falls das Array sortiert ist => beende die Endlosschleife
break
else: # Andernfalls das Array erneut mischen
shuffle(a)
print(a) # Zum Schluss die fertige Liste ausgebenDieser Algorithmus ist rein zufällig und kann theoretisch unendlich lange benötigen, um ans Ziel zu kommen. Daher wäre es extrem riskant und ineffizient, so etwas in einer Produktionsumgebung einzusetzen.
Sie sollen nun berechnen, wie viele Iterationen der Bogosort-Algorithmus benötigt, um schließlich eine Lösung zu finden.
Input
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ).Output
Das Programm soll die Anzahl der Iterationen ausgeben, die Bogosort benötigt, um die sortierte Liste zu finden.
Examples
Input | Output |
5
5 -1 2 3 9 | 10 |
Explanation
Die Zahl 10 ist hier rein zufällig – es könnten ebenso 2 oder 200 sein. Wenn Sie das Programm mit denselben Eingaben wiederholt ausführen, werden Sie möglicherweise jedes Mal andere Resultate erhalten.
Other Ridiculous Sorting Algorithms
Weitere skurrile Sortieralgorithmen sind im unten verlinkten YouTube-Video von Ardens visuell dargestellt.
Constraints
Time limit: 60 seconds
Memory limit: 512 MB
Output limit: 1 MB