Bogosort
Bogosort, Pogosort, Dumbsort oder Stupidsort (auch Omarsort) bezeichnet ein nicht-stabiles Sortierverfahren, bei dem die Elemente so lange zufällig gemischt werden, bis sie sortiert sind. Wegen der langen Laufzeit ist Bogosort der Prototyp eines schlechten Algorithmus. Bogosort wird insbesondere in der Informatik-Ausbildung in den Bereichen Datenstrukturen und Algorithmen verwendet, um an einem Extrembeispiel die Eigenschaften von Sortierverfahren im Allgemeinen zu verdeutlichen.<ref>TU Berlin: <templatestyles src="Webarchiv/styles.css" />{{#if:20070613075034
| {{#ifeq: 20070613075034 | *
| {{#if: Informatik für Elektrotechniker II – Aufgabenblatt 5 | {{#invoke:WLink|getEscapedTitle|Informatik für Elektrotechniker II – Aufgabenblatt 5}} | {{#invoke:Webarchiv|getdomain|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20070613075034}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Informatik für Elektrotechniker II – Aufgabenblatt 5 | {{#invoke:WLink|getEscapedTitle|Informatik für Elektrotechniker II – Aufgabenblatt 5}} | {{#invoke:Webarchiv|getdomain|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20070613075034}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Informatik für Elektrotechniker II – Aufgabenblatt 5 | {{#invoke:WLink|getEscapedTitle|Informatik für Elektrotechniker II – Aufgabenblatt 5}} | {{#invoke:Webarchiv|getdomain|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Informatik für Elektrotechniker II – Aufgabenblatt 5 | {{#invoke:WLink|getEscapedTitle|Informatik für Elektrotechniker II – Aufgabenblatt 5}} | {{#invoke:Webarchiv|getdomain|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Informatik für Elektrotechniker II – Aufgabenblatt 5 | {{#invoke:WLink|getEscapedTitle|Informatik für Elektrotechniker II – Aufgabenblatt 5}} | {{#invoke:Webarchiv|getdomain|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Informatik für Elektrotechniker II – Aufgabenblatt 5 | {{#invoke:WLink|getEscapedTitle|Informatik für Elektrotechniker II – Aufgabenblatt 5}} | {{#invoke:Webarchiv|getdomain|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20070613075034|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf}}
|| {{#if: || }}
}}{{#if: Informatik für Elektrotechniker II – Aufgabenblatt 5
| {{#if: {{#invoke:WLink|isBracketedLink|Informatik für Elektrotechniker II – Aufgabenblatt 5}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://uebb.cs.tu-berlin.de/infet/SS05/blatt5.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}, Sommersemester 2005</ref><ref>University of Massachusetts Amherst: <templatestyles src="Webarchiv/styles.css" />{{#if:20140115051946
| {{#ifeq: 20140115051946 | *
| {{#if: CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs. | {{#invoke:WLink|getEscapedTitle|CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.}} | {{#invoke:Webarchiv|getdomain|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20140115051946}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs. | {{#invoke:WLink|getEscapedTitle|CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.}} | {{#invoke:Webarchiv|getdomain|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20140115051946}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs. | {{#invoke:WLink|getEscapedTitle|CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.}} | {{#invoke:Webarchiv|getdomain|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs. | {{#invoke:WLink|getEscapedTitle|CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.}} | {{#invoke:Webarchiv|getdomain|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs. | {{#invoke:WLink|getEscapedTitle|CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.}} | {{#invoke:Webarchiv|getdomain|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs. | {{#invoke:WLink|getEscapedTitle|CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.}} | {{#invoke:Webarchiv|getdomain|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20140115051946|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf}}
|| {{#if: || }}
}}{{#if: CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.
| {{#if: {{#invoke:WLink|isBracketedLink|CMPSCI 187 Introduction to Data Structures – Discussion #11: Sorting and Graphs.}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://twiki-edlab.cs.umass.edu/pub/_S2007Hanson187/DiscussionSheets/disc11.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}} 12. Juni 2006</ref>
Laufzeitverhalten
Bogosort ist ein (randomisierter) Las-Vegas-Algorithmus, daher ist dessen Laufzeit eine Zufallsvariable. Die erwartete Laufzeit ist im besten Fall <math>\mathcal{O}(n)</math> (angegeben in der Landau-Notation) sofern die angegebene Liste bereits sortiert ist und im schlechtesten Fall <math>\Theta(n \cdot n!)</math>.<ref name="Fun07">H. Gruber, M. Holzer und O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, S. 183–197 (PDF; 193 kB).</ref> Die Fakultät <math>n!</math> ist die Anzahl der möglichen Anordnungen (Permutationen) <math>n</math> verschiedener Elemente. Die Operation, die am häufigsten ausgeführt wird und das Laufzeitverhalten bestimmt, ist die Anzahl der Vertauschungen. Erstaunlicherweise ist die erwartete Anzahl der Vergleiche, die für große Listen gegen <math>(e-1) \cdot n!</math> strebt, wesentlich geringer.<ref name="Fun07"/> Hierbei bezeichnet <math>e</math> die Eulersche Zahl.
In der Realität kann die Laufzeit beliebig lang sein, allerdings sind übermäßig lange Laufzeiten gemäß der Markow-Ungleichung auch entsprechend unwahrscheinlich. Der Algorithmus kommt unter der Annahme echter Zufallszahlengeneratoren und einer endlichen Anzahl zu sortierender Elemente fast sicher, d. h. mit Wahrscheinlichkeit 1, nach endlich vielen Schritten zu einem Ergebnis. Das bedeutet, dass es dennoch möglich ist, dass der Algorithmus niemals terminiert. Kommt ein Pseudozufallszahlengenerator zum Einsatz, muss dessen Periode hinreichend lang sein, sodass jede mögliche Permutation mindestens einmal generiert wird, bevor sich die Folge wiederholt.
Code
Pseudocode
<syntaxhighlight lang="pascal" line="1"> while not sorted(deck):
shuffle(deck)
</syntaxhighlight>
Python
<syntaxhighlight lang="python" line="1"> from random import shuffle
def bogosort(data: list) -> list:
while not all(a <= b for a, b in zip(data, data[1:])):
shuffle(data)
return data
</syntaxhighlight>
Java
<syntaxhighlight lang="java" line="1"> class Main { public static int[] sort(int[] toSort) { Random r = new Random();
while (!isSorted(toSort)) { // Prüfen, ob sortiert int a = r.nextInt(toSort.length); int b = r.nextInt(toSort.length);
int temp = toSort[a]; toSort[a] = toSort[b]; toSort[b] = temp; } return toSort; } static boolean isSorted(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}
} </syntaxhighlight>
JavaScript
<syntaxhighlight lang="javascript" line="1"> function sort(arr) {
while(!isSorted()) {
var a = Math.floor(Math.random() * arr.length);
var b = Math.floor(Math.random() * arr.length);
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
function isSorted() {
for(var i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}
} </syntaxhighlight>
C
<syntaxhighlight lang="c" line="1"> inline void swap(register int *a, register int *b) {
register int temp = *a; *a = *b; *b = temp;
}
int isSorted(int arr[], size_t n) {
for (size_t i = 0; i < n - 1; ++i)
if (arr[i] > arr[i + 1])
return 0;
return 1;
}
void shuffle(int arr[], size_t n) {
for (size_t i = n - 1; i > 0; --i) {
int j = rand() % (i + 1);
swap(&arr[i], &arr[j]);
}
}
void bogoSort(int arr[], size_t n) {
while (!isSorted(arr, n)) shuffle(arr, n);
}
</syntaxhighlight>
Einzelnachweise
<references />
Weblinks
- Jargon File entry for bogo-sort (englisch)