Bogosort
Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.
|
Bogosort (также случайная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать её, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.
Среднее время работы алгоритма: <math>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!)</math>.
При прохождении цикла один раз в секунду сортировка следующего количества элементов в среднем может занять:
Кол-во элементов | 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 карты будет сортироваться компьютером, в среднем, <math>2,7\cdot\;10^{19}</math> лет.
Содержание
Примеры реализации
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);
}
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;
}
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
C++
#include <algorithm>
template<class Container>
void bogosort(Container & c)
{
while (!std::is_sorted(std::begin(c), std::end(c)))
std::random_shuffle(std::begin(c), std::end(c));
}
См. также
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её. |
<imagemap>: неверное или отсутствующее изображение |
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 13 октября 2011 года. |
|
Напишите отзыв о статье "Bogosort"
Отрывок, характеризующий Bogosort
– Пожалуйте, ваше благородие, – говорил первый купец, кланяясь. Офицер стоял в недоумении, и на лице его видна была нерешительность.– Да мне что за дело! – крикнул он вдруг и пошел быстрыми шагами вперед по ряду. В одной отпертой лавке слышались удары и ругательства, и в то время как офицер подходил к ней, из двери выскочил вытолкнутый человек в сером армяке и с бритой головой.
Человек этот, согнувшись, проскочил мимо купцов и офицера. Офицер напустился на солдат, бывших в лавке. Но в это время страшные крики огромной толпы послышались на Москворецком мосту, и офицер выбежал на площадь.
– Что такое? Что такое? – спрашивал он, но товарищ его уже скакал по направлению к крикам, мимо Василия Блаженного. Офицер сел верхом и поехал за ним. Когда он подъехал к мосту, он увидал снятые с передков две пушки, пехоту, идущую по мосту, несколько поваленных телег, несколько испуганных лиц и смеющиеся лица солдат. Подле пушек стояла одна повозка, запряженная парой. За повозкой сзади колес жались четыре борзые собаки в ошейниках. На повозке была гора вещей, и на самом верху, рядом с детским, кверху ножками перевернутым стульчиком сидела баба, пронзительно и отчаянно визжавшая. Товарищи рассказывали офицеру, что крик толпы и визги бабы произошли оттого, что наехавший на эту толпу генерал Ермолов, узнав, что солдаты разбредаются по лавкам, а толпы жителей запружают мост, приказал снять орудия с передков и сделать пример, что он будет стрелять по мосту. Толпа, валя повозки, давя друг друга, отчаянно кричала, теснясь, расчистила мост, и войска двинулись вперед.
В самом городе между тем было пусто. По улицам никого почти не было. Ворота и лавки все были заперты; кое где около кабаков слышались одинокие крики или пьяное пенье. Никто не ездил по улицам, и редко слышались шаги пешеходов. На Поварской было совершенно тихо и пустынно. На огромном дворе дома Ростовых валялись объедки сена, помет съехавшего обоза и не было видно ни одного человека. В оставшемся со всем своим добром доме Ростовых два человека были в большой гостиной. Это были дворник Игнат и казачок Мишка, внук Васильича, оставшийся в Москве с дедом. Мишка, открыв клавикорды, играл на них одним пальцем. Дворник, подбоченившись и радостно улыбаясь, стоял пред большим зеркалом.
– Вот ловко то! А? Дядюшка Игнат! – говорил мальчик, вдруг начиная хлопать обеими руками по клавишам.
– Ишь ты! – отвечал Игнат, дивуясь на то, как все более и более улыбалось его лицо в зеркале.
– Бессовестные! Право, бессовестные! – заговорил сзади их голос тихо вошедшей Мавры Кузминишны. – Эка, толсторожий, зубы то скалит. На это вас взять! Там все не прибрано, Васильич с ног сбился. Дай срок!