보고소트(Bogosort)는 데이터 집합을 정렬될 때까지 무작위로 계속 섞는 아주 단순하면서도 비효율적인 알고리즘입니다. 순열과 조합에 기반하여 동작하기 때문에 순열 정렬(Permutation Sort)이라고도 불리며, 그 비효율성 때문에 산탄총 정렬(Shotgun Sort), 멍청한 정렬(Stupid Sort), 원숭이 정렬(Monkey Sort), 느린 정렬(Slow Sort) 등 다양한 이름으로 불립니다.
이 알고리즘의 동작 방식은 간단합니다. 입력 배열의 모든 가능한 순열을 하나씩 생성해 가면서, 그중 우연히 정렬된 상태가 나올 때까지 과정을 반복하는 것입니다.
입력 - 53421 출력 - 12345
보고소트의 동작 원리
보고소트는 다음과 같은 단계로 진행됩니다.
1. 현재 배열의 요소들이 올바른 순서(오름차순)로 정렬되어 있는지 검사합니다.
2. 만약 정렬되어 있지 않다면, 배열의 요소들을 무작위로 섞어(shuffle) 위치를 재배치합니다.
3. 배열이 정렬될 때까지 1~2번 과정을 계속 반복합니다.
즉, 운이 좋다면 몇 번 만에 정렬이 끝날 수도 있지만, 최악의 경우 사실상 무한히 반복할 수도 있는 것이 보고소트의 특징입니다. 평균 시간 복잡도는 O(n × n!)로, 요소가 많아질수록 실행 시간이 기하급수적으로 늘어나기 때문에 실무에서는 전혀 사용되지 않고, 주로 학습용이나 재미로 활용됩니다.
C++ 구현 예제
#include <iostream>
#include <stdlib.h>
using namespace std;
int is_sorted(int *arr, int n) {
while ( --n >= 1 ) {
if ( arr[n] < arr[n-1] ) {
return 0;
}
}
return 1;
}
void shuffle(int *arr, int n) {
int temp, r;
for(int i=0; i < n; i++) {
temp = arr[i];
r = rand() % n;
arr[i] = arr[r];
arr[r] = temp;
}
}
void bogosort(int *arr, int n) {
while ( !is_sorted(arr, n) ) {
shuffle(arr, n);
}
}
int main() {
int arr[] = { 5, 3, 4, 2, 1 };
int i;
bogosort(arr, 5);
for (i=0; i < 5; i++) {
cout<< arr[i]<<"\t";
}
}코드 설명
- is_sorted(): 배열이 오름차순으로 정렬되어 있는지 확인하는 함수입니다. 인접한 두 요소를 비교하여 내림차순인 부분이 발견되면 0을 반환합니다.
- shuffle(): rand() 함수를 이용해 배열 요소들의 위치를 무작위로 교환하는 함수입니다.
- bogosort(): 배열이 정렬될 때까지 shuffle()을 반복 호출하는 핵심 함수입니다.
- main(): 정렬되지 않은 배열 {5, 3, 4, 2, 1}을 선언하고, 보고소트를 수행한 후 결과를 출력합니다.