Bogosort

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Среднее время работы алгоритма: O\left(n\cdot\sum_{i=1}^{\infty}{\frac{i}{n!}\cdot \left(1-\frac{1}{n!}\right)^{i-1}}\right) = O(n\cdot\;n!).

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

Кол-во элементов 1 2 3 4 5 6 7 8 9 10 11 12
Среднее время 1 с 4 с 18 с 96 с 10 мин 1.2 часов 9.8 часов 3.7 сут 37.8 сут 1.15 лет 13.9 лет 182 года

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

Кол-во элементов 10 11 12 13 14 15 16 17 18 19 20
Среднее время 0.0037 с 0.045 с 0.59 с 8.4 с 2.1 мин 33.6 мин 9.7 часов 7.29 сут 139 дней 7.6 лет 160 лет

Колода в 32 карты будет сортироваться компьютером, в среднем, 2,7\cdot\;10^{19} лет.

Примеры реализации[править | править вики-текст]

C#[править | править вики-текст]

using System;
 
class Program
{
    static bool IsSorted<T>(T[] array) where T: IComparable<T>
    {
        for (int i = 0; i < array.Length - 1; i++)
            if (array[i].CompareTo(array[i + 1]) == 1)
                return false;
        return true;
    }
 
    static void Swap<T>(ref T a, ref T b)
    {
        T buffer = a;
        a = b;
        b = buffer;
    }
 
    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();
        for (int i = 0; i < array.Length; i++)
            Swap<T>(ref array[i], ref array[random.Next(0, array.Length)]);
    }
 
    static void BogoSort<T>(T[] array) where T: IComparable<T>
    {
        while (!IsSorted<T>(array))
            Shuffle<T>(array);
    }
 
    static void Main(string[] args)
    {
        int[] a = new int[] { 1, 0, 2, 5, 2 };
        BogoSort(a);
        Console.WriteLine(string.Join(", ", a));
    }
}

Си[править | править вики-текст]

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);
}

С++[править | править вики-текст]

#include <vector>
#include <algorithm>
 
void bogoSort(std::vector<int> &arr)
{
    const auto begin = arr.begin();
    const auto end = arr.end();
 
    while (!std::is_sorted(begin, end))
        std::random_shuffle(begin, end);
}

D[править | править вики-текст]

import std.range, std.algorithm, std.random;
 
void bogoSort(R)(R r) if (isRandomAccessRange!R)
{
    while (!isSorted(r))
        randomShuffle(r);
}

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(n.length);
        int temp = n[i];
        n[i] = n[swapPosition];
        n[swapPosition] = temp;
    }
}
 
public boolean inOrder(int[] n) {
    int length = n.length - 1;
    for (int i = 0; i < length; 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)
    }
}

Scala[править | править вики-текст]

def isSorted(l: List[Int]) = l.iterator sliding 2 forall (s => s.head < s.last)
def bogosort(l: List[Int]): List[Int] = if (isSorted(l)) l else bogosort(scala.util.Random.shuffle(l))

Delphi[править | править вики-текст]

program Bogosort;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
const n=10;
 
Type Arr=array[1..n] of integer;
 
function InOrder(M:Arr):boolean;
var i:Integer;
begin
  for i:=1 to n-1 do
  begin
    if M[i]> M[i+1] then
      begin
        result:=False;
        Break;
      end
    else Result:=True;
  end;
end;
 
procedure Shuffle(var M:arr);
var RandomIndex,temp,i:integer;
begin
  for i:=1 to n do
    begin
      RandomIndex:=Random(n)+1;
      temp:=m[i];
      m[i]:=m[RandomIndex];
      m[RandomIndex]:=temp;
    end;
end;
 
var TestArray:arr;
            i:integer;
begin
  Randomize;
  for i:=1 to n do TestArray[i]:=Random(n*n);
  while Not InOrder(TestArray) do Shuffle(TestArray);
  Readln;
end.

Python[править | править вики-текст]

from random import shuffle
 
def issorted(array):
    return not any(
        array[i] > array[i+1]
        for i in xrange(len(array)-1)
    )
 
def bogosort(array):
    while not issorted(array):
        shuffle(array)
 
    return array

Perl[править | править вики-текст]

use List::Util qw(shuffle);
 
my $sorted = join(' ', sort { $a <=> $b } @array );
while( $sorted ne join(' ', @array ) ) {
    @array = shuffle(@array);
}

См. также[править | править вики-текст]