Bogosort

from Wikipedia, the free encyclopedia

Bogosort , Alexsort , Monkeysort or Stupidsort describes a non- stable sorting process in which the elements are randomly mixed until they are sorted. Because of the long running time, Bogosort is the prototype of a bad algorithm . Bogosort is used in particular in computer science training in the areas of data structures and algorithms in order to illustrate the properties of sorting processes in general using an extreme example.

Runtime behavior

Bogosort is a (randomized) Las Vegas algorithm , so its running time is a random variable . The expected runtime is in the best case (given in Landau notation ) if the given list is already sorted and in the worst case . The factorial is the number of possible arrangements ( permutations ) of different elements. The operation that is performed most often and that determines the runtime behavior is the number of swaps. Amazingly, the expected number of comparisons aimed at for large lists against is significantly fewer. Here is the Euler's number .

In reality, the running time can be as long as you like, however, according to the Markov inequality , excessively long running times are correspondingly unlikely. The algorithm almost certainly works assuming true random number generators and a finite number of elements to be sorted ; H. with probability 1, after a finite number of steps to a result. This means that it is still possible that the algorithm will never terminate. If a pseudo-random number generator is used, its period must be long enough so that every possible permutation is generated at least once before the sequence is repeated.

code

Java

 1 public static int[] sort(int[] toSort) {
 2 	Random r = new Random();
 3 	
 4 	while (!isSorted(toSort)) { // Prüfen, ob sortiert
 5 		int a = r.nextInt(toSort.length);
 6 		int b = r.nextInt(toSort.length);
 7 
 8 		int temp = toSort[a];
 9 		toSort[a] = toSort[b];
10 		toSort[b] = temp;
11 	}
12 	
13 	return toSort;
14 }

JavaScript

 1 function sort(arr) {
 2     while(!isSorted()) {
 3         var a = Math.floor(Math.random() * arr.length);
 4         var b = Math.floor(Math.random() * arr.length);
 5         var tmp = arr[a];
 6         arr[a] = arr[b];
 7         arr[b] = tmp;
 8     }
 9 
10     function isSorted() {
11         for(var i = 0; i < arr.length - 1; i++) {
12             if (arr[i] > arr[i + 1]) return false;
13         }
14         return true;
15     }
16 }

Individual evidence

  1. ↑ TU Berlin : Computer Science for Electrical Engineers II - Exercise Sheet 5 ( Memento from June 13, 2007 in the Internet Archive ), summer semester 2005
  2. ^ University of Massachusetts Amherst : CMPSCI 187 Introduction to Data Structures - Discussion # 11: Sorting and Graphs. ( Memento of the original from January 15, 2014 in the Internet Archive ) Info: The @1@ 2Template: Webachiv / IABot / twiki-edlab.cs.umass.edu archive link was inserted automatically and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. June 12, 2006
  3. ^ A b H. Gruber, M. Holzer and 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, pp. 183–197 (PDF file; 193 kB).

Web links