Bogosort

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

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

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

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

Кол-во элементов 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·1019 лет.

Пример реализации[править | править код]

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

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

Ссылки[править | править код]