Bogosort ist ein sehr beliebter Sortieralgorithmus. Statt die richtige Reihenfolge der Elemente aufwändig zu berechnen wird sie einfach solange geraten, bis ein Treffer erzielt wird. Einen wirklichen Zweck hat dieses Programm also nicht.

Die zu sortierende Zahlenfolge wird mit dem Parameter -s angegeben. Es wird empfohlen, bei mehr als 10 Zahlen auf ein Mehrprozessorsystem zurück zu greifen und die Anzahl der Threads mit dem Parameter -j entsprechend anzupassen.

• C++-Compiler
• Humor

/*      bogo_sort.cpp
 *
 *      This is a bloated, messy, threadable implementation of bogosort for
 *      research purposes.
 *      
 *      Copyright 2009 Alexander Heinlein
 *      
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; either version 3 of the License, or
 *      (at your option) any later version.
 *      
 *      This program is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 *      
 *      You should have received a copy of the GNU General Public License
 *      along with this program; if not, write to the Free Software
 *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 *      MA 02110-1301, USA.
 */
 
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm> /* qsort() */
#include <cstdlib>   /* rand_r() */
#include <ctime>     /* time() */
#include <cstring>   /* memset() */
#include <pthread.h>
#include <signal.h>
#include <sys/time.h> /* gettimeofday() */
 
// each thread holds own run number, avoids the need for
// constant (un-)locking when using a global run counter
std::vector<unsigned long long> runs;
// start time of program
unsigned long start = 0;
// length of sequence, needed to calculate bogosorts/s
unsigned int seq_len;
bool finished = false;
 
pthread_mutex_t finish_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t init_mutex   = PTHREAD_MUTEX_INITIALIZER;
 
//! initialize thread by assignign distinct thread number
unsigned int init_thread()
{
 unsigned int num;
 pthread_mutex_lock(&init_mutex);
 // resize vector and initialize run
 num = runs.size();
 runs.resize(num + 1);
 runs[num] = 0;
 pthread_mutex_unlock(&init_mutex);
 
 return num;
}
 
//! notify other threads about success (threadsafe)
void finish()
{
 pthread_mutex_lock(&finish_mutex);
 finished = true;
 pthread_mutex_unlock(&finish_mutex);
}
 
//! print current progress
void print_status()
{
 struct timeval tv;
 gettimeofday(&tv, NULL);
 unsigned long now = tv.tv_sec * 1000 * 1000 + tv.tv_usec;
 
 double u_secs = (now - start);
 
 unsigned long long total_runs = 0;
 for(std::vector<unsigned long long>::iterator it = runs.begin(); it != runs.end(); it++)
 {
    total_runs += *it;
 }
 
 // million bogosorts per second
 double m_bsorts = 0;
 if(u_secs != 0)
 {
    m_bsorts = (total_runs * seq_len) / u_secs;
 }
 
 std::cout << total_runs << " runs after " << u_secs / 1000.0 / 1000.0 << " seconds (" << m_bsorts << " million bogosorts/s)." << std::endl;
}
 
class BogoSort
{
 private:
    void print(std::vector<int>& vec);
 
 public:
    void bsort(std::vector<int> vec);
};
 
//! 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)
{
 // get distinct thread id
 unsigned int num = init_thread();
 // distinct random seed for every thread
 unsigned int seed = time(0) + num;
 
 // create sorted sequence for easy comparison
 std::vector<int> sorted = vec;
 sort(sorted.begin(), sorted.end());
 
 std::vector<int> bogosorted;
 unsigned int size = vec.size();
 unsigned int pos;
 
 // randomly sort until success
 while(bogosorted != sorted)
 {
    if(finished) return; // another thread finished successfully, let's stop
 
    runs[num]++;
    bogosorted.clear();
    vec = sorted;
 
    for(unsigned int i = 0; i < size; i++)
    {
        pos = rand_r(&seed) % vec.size(); // choose random element
        bogosorted.push_back(vec[pos]);// add to bogosort vector
        vec.erase(vec.begin() + pos);  // remove from available elements
    }
 }
 
 finish();
 
 print(bogosorted);
 print_status();
}
 
//! let thread perform bogosort
void* thread_routine(void* arg)
{
 std::vector<int>* vec = static_cast<std::vector<int>*>(arg);
 
 BogoSort bsort;
 bsort.bsort(*vec);
 
 pthread_exit(NULL);
}
 
//! signal handler
void signal_handler(int signal)
{
 switch(signal)
 {
     case SIGUSR1:
         // just print progress, but keep running
         print_status();
         break;
     case SIGINT:
     case SIGTERM:
         print_status();
         exit(0);
         break;
     default:
         std::cerr << "Received unknown signal" << std::endl;
         print_status();
         exit(1);
         break;
 }
}
 
void usage(const std::string& cmd)
{
 std::cout << "Usage: " << cmd << " [OPTION]" << std::endl << std::endl
           << "-s, --sequence SEQUENCE  sequence of numbers to sort" << std::endl
           << "-j, --jobs     NUM       number of jobs to run in parallel"  << std::endl
           << "-h, --help               print this help and exit" << std::endl
           << std::endl
           << "Example: " << cmd << " -s 75 3 84 2" << std::endl
           << "Hint: for optimum results, make sure the sequence consists of distinct numbers" << std::endl;
}
 
int main(int argc, char *argv[])
{
 if (argc < 2)
 {
    std::cerr << "You don't like arguments? So i don't like you :(" << std::endl;
    usage(argv[0]);
    return 0;
 }
 
 // parse command line arguments
 std::vector<std::string> args(argv, argv + argc);
 std::vector<int> sequence;
 int jobs = 1;
 for (std::vector<std::string>::iterator it = args.begin() + 1; it < args.end(); it++)
 {
    if (*it == "-s" || *it == "--sequence")
    {
         while (++it != args.end())
         {
             // end of sequence / next argument?
             if(it->at(0) == '-')
             {
                 --it;
                 break;
             }
 
             std::stringstream strstr(*it);
             int num;
             strstr >> num;
             sequence.push_back(num);
         }
    }
    else if (*it == "-j" || *it == "--jobs")
    {
        if(++it < args.end())
        {
            std::stringstream strstr(*it);
            strstr >> jobs;
            if(jobs < 1)
            {
                std::cerr << "Number of jobs must be at least one" << std::endl;
                return 0;
            }
        }
        else
        {
            std::cerr << "Invalid number of arguments for jobs" << std::endl;
            usage(argv[0]);
            return 0;
        }
    }
    else if (*it == "-h" || *it == "--help")
    {
        usage(argv[0]);
        return 0;      
    }
    else
    {
        std::cerr << "Invalid argument: " << *it << std::endl;
        usage(argv[0]);
        return -1;     
    }
 }
 
 if(sequence.size() <= 1)
 {
    std::cerr << "Input sequence too short" << std::endl;
    usage(argv[0]);
    return -1;
 }
 
 // register signal handler
 struct sigaction action;
 memset(&action, 0, sizeof(action));
 action.sa_handler = signal_handler;
 action.sa_flags = 0;
 sigemptyset(&action.sa_mask);
 sigaction(SIGUSR1, &action, NULL);
 sigaction(SIGINT, &action, NULL);
 sigaction(SIGTERM, &action, NULL);
 
 seq_len = sequence.size(); 
 std::cout << "Using " << jobs << " thread(s) to sort " << seq_len << " elements." << std::endl;
 
 // set start time 
 struct timeval tv;
 gettimeofday(&tv, NULL);
 start = tv.tv_sec * 1000 * 1000 + tv.tv_usec;
 
 // create threads 
 std::vector<pthread_t> threads;
 threads.reserve(jobs);
 runs.reserve(jobs);
 for(int i = 0; i < jobs; i++)
 {
     pthread_t thread;
 
     pthread_attr_t attr; 
     pthread_attr_init(&attr); 
     pthread_attr_setstacksize(&attr, 512 * 1024); // reduce default thread stack size
 
     pthread_create(&thread, &attr, &thread_routine, &sequence);
     threads.push_back(thread);
 }
 
 // we have to wait for every thread to terminate, otherwise
 // sequence may get freed to early (or some other crap happens)
 for(int i = 0; i < jobs; i++)
 {
     pthread_join(threads.at(i), NULL);
 }
 
 pthread_exit(NULL);
 
 return 0;
}

• Kompilieren: g++ -march=native -Os -o bogo_sort bogo_sort.cpp -lpthread && strip bogo_sort
• Starten: ./bogo_sort -j 2 -s 19563 56345 2423 4534 3543 (Sortieren von fünf Zahlen unter Benutzung von zwei Threads)
• Status abfragen: pkill -USR1 bogo_sort (Schreibt Anzahl bisheriger Sortierversuche auf die Standardausgabe, ohne das Programm zu beenden)

Hinweis: Die Statusabfrage und auch das Ausgeben des aktuellen Fortschritts bei Beendigung durch Senden eines Interrupts erlauben es, das Programm zu beenden und zu einem späteren Zeitpunkt erneut zu starten. Dadurch lassen sich die Anzahl der Versuche mehrerer Läufe addieren, bis schließlich einer zum Erfolg führt. Wie statistisch relevant dieses Ergebnis dadurch ist, sei dahingestellt.

Anzahl der Sortierversuche bei je 10 Durchläufen (statistisch nicht relevant).

Zusätzlich zur Anzahl der Sortierversuche gibt das Programm auch die imaginäre Metrik der Anzahl der Bogosorts pro Sekunde aus. Dieser Wert ist natürlich unabhängig von der Länge der zu sortierenden Folge, solange sie hinreichend lang ist. Die folgende Tabelle liefert einige Aufschlüsse darüber, mit welcher Prozessorleistung welche MBpS erreichbar sind.

Hinweis: Dieses Programm ist für Benchmarks natürlich ungeeignet, da die zu erreichenden MBpS von vielen Einflüssen abhängen.