C++로 배우는 보고 소트(Bogo Sort): 순열 정렬 알고리즘의 이해와 구현

이번 글에서는 보고 소트(Bogo Sort)라는 독특한 정렬 알고리즘을 살펴봅니다. 보고 소트는 순열 정렬(Permutation Sort), 바보 정렬(Stupid Sort), 느린 정렬(Slow Sort) 등 다양한 이름으로도 불립니다.

보고 소트는 실용성 측면에서 극히 비효율적인 정렬 기법으로, '생성 후 검증(Generate and Test)' 패러다임에 속합니다. 작동 원리는 매우 단순합니다. 리스트가 정렬될 때까지 요소들을 무작위로 섞는(shuffle) 과정을 반복하는 것입니다. 운이 좋다면 몇 번 만에 정렬되지만, 최악의 경우 사실상 무한히 시도해야 할 수도 있습니다.

알고리즘

bogoSort(array, n)

Begin
    while the arr is not sorted, do
        shuffle arr
    done
End

C++ 구현 예제

아래 코드는 배열이 정렬되어 있는지 확인하는 함수, 배열을 무작위로 섞는 함수, 그리고 이 둘을 결합해 정렬을 수행하는 보고 소트 함수로 구성되어 있습니다.

#include<iostream>
#include<cstdlib>
using namespace std;

bool isSorted(int arr[], int n) { // 배열이 정렬되어 있는지 확인
    while (--n > 1)
        if (arr[n] < arr[n - 1])
            return false;
    return true;
}

void shuffle(int arr[], int n) { // 배열 요소를 무작위로 섞음
    for (int i = 0; i < n; i++)
        swap(arr[i], arr[rand() % n]);
}

void bogoSort(int arr[], int n) {
    while (!isSorted(arr, n))
        shuffle(arr, n);
}

main() {
    int data[] = {54, 74, 98, 5, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    cout << "Sorted Sequence ";
    bogoSort(data, n);
    for(int i = 0; i <n;i++){
        cout << data[i] << " ";
    }
}

실행 결과

Sorted Sequence 5 13 20 32 35 40 54 74 98 98

정리

보고 소트의 평균 시간 복잡도는 O((n+1)!)로, 요소 개수가 조금만 늘어나도 실행 시간이 기하급수적으로 증가합니다. 따라서 실무에서 사용하기에는 부적합하지만, 정렬 알고리즘의 개념을 재미있게 학습하거나 확률과 알고리즘 설계를 이해하기 위한 교육적 예제로 활용하기에 좋습니다.