Bogosort (также случайная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.

Среднее время работы алгоритма: .

При прохождении цикла один раз в секунду сортировка следующего количества элементов в среднем может занять:

При работе 4-ядерного процессора 2.4 ГГц (9.6 млрд операций в секунду)

Колода в 32 карты будет сортироваться компьютером, в среднем, лет.

Примеры реализации

Си

int correct( int *arr, int size )
{
    while (--size > 0)
        if (arr[size - 1] > arr[size])
            return 0;
    return 1;
}
void shuffle( int *arr, int size )
{
    int i;
    for (i = 0; i < size; i++)
        swap(arr + i, arr + (rand() % size)); 
}
void bogoSort( int *arr, int size )
{
    while (!correct(arr, size))
        shuffle(arr, size);
}

Java

Random random = new Random();
 
public void bogoSort(int[] n) {
    while(!inOrder(n))shuffle(n);
}
 
public void shuffle(int[] n) {
    for (int i = 0; i < n.length; i++) {
        int swapPosition = random.nextInt(i + 1);
        int temp = n[i];
        n[i] = n[swapPosition];
        n[swapPosition] = temp;
    }
}
 
public boolean inOrder(int[] n) {
    for (int i = 0; i < n.length-1; i++) {
        if (n[i] > n[i+1]) return false;
    }
    return true;
}

Nemerle

def bogoSort(arr){
    def random = System.Random();
    def inOrder(i) {
        | _ when (i < 2) => true
        | _ when (arr[i - 2] > arr[i- 1]) => false
        | _ => inOrder(i - 1)
    }
 
    def shuffle(i) {
        | 1 => ()
        | _ => arr[random.Next(0, arr.Length)] <-> arr[i - 1];
               shuffle(i - 1)
    }
 
    unless (inOrder(arr.Length)){
        shuffle(arr.Length);
        bogoSort(arr)
    }
}

См. также

• Лас-Вегас (алгоритм)
• Генераторы псевдослучайных чисел