Bogosort Guide, Meaning , Facts, Information and Description

According to the Jargon File, the bogosort is "the archetypal perversely awful algorithm", one example of which is attempting to sort a deck of cards by repeatedly throwing the deck in the air, picking the cards up at random, and then testing whether the cards are in sorted order. It is named after the humourous term quantum bogodynamics and ultimately, the word bogus. Other names are bozo sort and blort sort.

Here is the pseudocode of the algorithm:

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

This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected complexity is O(n × n!). The exact expected running time depends on how many different element values occur, and how often each of them occurs, but for non-trivial cases the expected running time is exponential or super-exponential in n.

It should be noted that with real-world pseudo-random number algorithms, which have a finite number of states and are not in any case actually random, the algorithm may never terminate for certain inputs.

Bogosort is not a stable sort.

Table of contents

1 Implementations 1.1 Python 1.2 C++ 2 External links

Implementations

Python

import random

def is_sorted(array):
    for i in range(1, len(array)):
        if (array[i] < array[i-1]):
            return False
    return True

def bogosort(array):
    while not is_sorted(array):
        random.shuffle(array)

C++

#include 
#include 

template
void bogosort(std::vector& array)
{
    while (! is_sorted(array))
        std::random_shuffle(array.begin(), array.end());
}

template
bool is_sorted(const std::vector& array)
{
    for (typename std::vector::size_type i = 1; i < array.size(); ++i)
        if (array[i] < array[i-1]) return false;
    return true;
}

External links

• Jargon File entry for bogo-sort

This is an Article on Bogosort. Page Contains Information, Facts Details or Explanation Guide About Bogosort

	Web www.E-paranoids.com