Bogosort algorithm.

Сегодня я узнал что в computer science наряду с нормальными и практически применимыми подходами к упорядочиванию (sorting) элементов есть еще один алгоритм сортировки (bogosort) который всерьез применяют, по крайней мере для оценки сложности и при обсуждении вопросов в глубоком CS а так же для сравнения с другими алгоритмами...  Но то детали.



Алгоритм то смешной. Если есть неупорядоченная последовательность, например список, то данный алгоритм на каждой итерации меняет порядок расположения элементов случайным образом и потом проверяет, а не отсортирована ли после этого последовательность )

Звучит даже экстравагантно. В общем чего только не придумают для академической computer science.

Вот реализация на 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;
}

Его еще называют обезьяньей сортировкой и случайной сортировкой. Впрочем статья википедии на которую я уже сослался достаточно красноречива, плюс есть английский вариант. Мне это показалось довольно странныйм, а потому любопытным.