Bogosort

Bogosort ist ein nicht-stabiler Sortieralgorithmus, bei dem die zu sortierenden Elemente nach dem Zufallsprinzip sortiert werden. Bogosort entspricht etwa dem In-die-Luft-Werfen eines Kartenstapels, solange bis die Karten sortiert auf den Boden fallen. Das Laufzeitverhalten entspricht etwa O(n · n!).

Im Hackerjargon bezeichnet man mit Bogosort auch den Prototyp eines schlechten Algorithmus.

Pseudocode des Algorithmus:

 while not is_sorted(array)
     array := random_permutation(array)

Inhaltsverzeichnis

1 Implementierungen

1.1 Python
1.2 Java
1.3 C++
1.4 Perl

2 Externe Links

Implementierungen

Python

from random import shuffle
 
 def bogosort(seq):
     while seq != sorted(seq):
         shuffle(seq)

Java

import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
 
 public class Bogosort
 {
     protected boolean isSorted (List array, Comparator cmp)
     {
         Iterator i = array.iterator();
         Object cur = null, next = i.next();
         while (i.hasNext()) {
             cur = next;
             next = i.next();
             if (cmp.compare(cur, next) > 0)
                 return false;
         }
         return true;
     }
 
     protected void bsort (List array, Comparator cmp)
     {
         do {
             Collections.shuffle(array);
         } while (!isSorted(array, cmp));
     }
 
     public void sort (Object [] array, Comparator cmp)
     {
         if (array.length > 0)
             bsort (Arrays.asList(array), cmp);
     }
 }

C++

#include <algorithm>
 #include <vector>
 
 template<class T>
 void bogosort(std::vector<T>& array)
 {
     while (! is_sorted(array))
         std::random_shuffle(array.begin(), array.end());
 }
 
 template<class T>
 bool is_sorted(const std::vector<T>& array)
 {
     for (typename std::vector<T>::size_type i = 1; i < array.size(); ++i)
         if (array[i] < array[i-1]) return false;
     return true;
 }

Perl

sub bogosort {
     my @a = @_;
     while( ! is_sorted(@a) ) {
       shuffle(\@a);
     }
     @a;
 }
 
 sub is_sorted {
     for( my $ctr = 1; $ctr <= $#_; $ctr++ ) {
       return if $_[$ctr-1] > $_[$ctr];
     }
 
     1;
 }
 
 sub shuffle {
     my $ref = shift;
     for( my $ctr = 0; $ctr < $#{$ref}; $ctr++ ) {
           my $index = $ctr + int(rand($#{$ref} - $ctr + 1));
           my $temp = $ref->[$ctr];
           $ref->[$ctr] = $ref->[$index];
           $ref->[$index] = $temp;
     }
 }

Externe Links

Jargon File entry for bogo-sort

Kategorie:Sortieralgorithmus