WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

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

Кол-во элементов123456789101112
Среднее время1 с4 с18 с96 с10 мин1,2 ч9,8 ч3,7 сут37,8 сут1,15 лет13,9 лет182 лет

При работе 4-ядерного процессора на частоте 2,4 ГГц (9,6 млрд операций в секунду):

Кол-во элементов1011121314151617181920
Среднее время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) {
    for (int i = 0; i < size; ++i)
        swap(arr[i], arr[(rand() % size)]); 
}

void bogoSort(int *arr, int size) {
    while (!correct(arr, size))
        shuffle(arr, size);
}

См. также

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии