Bogosort

Bogosort ist ein sehr beliebter Sortieralgorithmus. Statt die richtige Reihenfolge der Elemente aufwändig zu berechnen werden sie einfach so lange zufällig sortiert, bis es passt.

• günstigste Laufzeit: Ω(n)
• schlechteste Laufzeit: O(∞)

• C++-Compiler

#include <iostream>
#include <vector>
#include <algorithm> /* qsort() */
#include <ctime>     /* time() */
#include <sstream>
 
class BogoSort
{
 private:
    void print(std::vector<int>&);
 
 public:
    void bsort(std::vector<int>&);
};
 
//! print vector elements
void BogoSort::print(std::vector<int> &vec)
{
 for(std::vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
 {
    std::cout << *it << " ";
 }
 
 std::cout << std::endl;
}
 
//! bogosort vector
void BogoSort::bsort(std::vector<int> &vec)
{
 std::cout << "unsorted: ";
 print(vec);
 
 std::vector<int> sorted = vec;
 sort(sorted.begin(), sorted.end());
 
 std::vector<int> bogosorted;
 int pos, num = 0;
 
 while(bogosorted != sorted)
 {
    bogosorted.clear();
    vec = sorted;
 
    int size = vec.size();
    for(int i = 0; i < size; i++)
    {
        pos = rand() % vec.size();     /* choose random element */
        bogosorted.push_back(vec[pos]);/* add to bogosort vector */
        vec.erase(vec.begin() + pos);  /* remove from available elements */
    }
 
    std::cout << "bogosort run " << ++num << ": ";
    print(bogosorted);
 }
 
 std::cout << "sorted: ";
 print(sorted);
 std::cout << std::endl;
}
 
int main(int argc, char *argv[])
{
 if (argc == 1)
 {
    std::cout << "Usage  : " << argv[0] << " NUMBERS\n\n"
              << "example: " << argv[0] << " 5 2 8 3\n";
    return 1;
 }
 
 srand(time(0));
 
 std::vector<std::string> args(argv, argv + argc);
 std::vector<std::string>::iterator it = args.begin();
 
 ++it;  /* ignore argv[0] */
 
 std::vector<int> vec;
 int num;
 
 while (it != args.end())
 {
    std::stringstream strstr(*it);
    strstr >> num;
    vec.push_back(num);
    ++it;
 }
 
 
 BogoSort bsort;
 bsort.bsort(vec);
 
 return 0;
}

Anzahl der Sortierversuche bei je 10 Durchläufen.