보고소트(BogoSort)란?
이 글에서는 보고소트(BogoSort), 일명 순열 정렬(Permutation Sort) 알고리즘을 파이썬으로 구현하는 방법을 살펴봅니다.
보고소트는 '생성 후 검증(Generate and Test)' 패러다임에 기반한 정렬 알고리즘입니다. 배열의 요소를 무작위로 섞은 뒤 정렬 여부를 확인하고, 정렬된 상태가 나올 때까지 이 과정을 계속 반복하는 매우 단순한 방식입니다.
문제 정의
문제: 하나의 배열이 주어졌을 때, 순열 정렬의 개념을 활용하여 해당 배열을 오름차순으로 정렬해야 합니다.
이 알고리즘은 다음 두 가지 핵심 함수로 구성됩니다.
- is_sorted(): 배열이 정렬되었는지 검사합니다.
- shuffle(): 배열의 요소를 무작위로 재배치합니다.
배열이 아직 정렬되어 있지 않다면 셔플을 반복 수행하며, 우연히라도 정렬된 상태가 만들어질 때까지 과정을 되풀이합니다.
파이썬 구현 코드
# random 모듈 임포트
import random
# 정렬 함수
def bogoSort(a):
n = len(a)
while (is_sorted(a) == False):
shuffle(a)
# 정렬 여부 검사
def is_sorted(a):
n = len(a)
for i in range(0, n-1):
if (a[i] > a[i+1]):
return False
return True
# 무작위 순열 생성(셔플)
def shuffle(a):
n = len(a)
for i in range(0, n):
r = random.randint(0, n-1)
a[i], a[r] = a[r], a[i]
# 메인 실행부
a = [1, 5, 3, 4, 8, 6, 3, 4, 5]
bogoSort(a)
print("Sorted array is :")
for i in range(len(a)):
print(a[i], end=" ")실행 결과
Sorted array is : 1 3 3 4 4 5 5 6 8
코드 동작 원리
모든 변수는 지역 범위(local scope) 안에서 선언되며, 각 함수는 다음과 같은 역할을 수행합니다.
- bogoSort(): is_sorted()가 False를 반환하는 동안 shuffle()을 계속 호출하며 정렬을 시도합니다.
- is_sorted(): 인접한 두 요소를 차례로 비교하여, 앞 요소가 뒤 요소보다 큰 경우 False를 반환합니다.
- shuffle(): random.randint()로 임의의 인덱스를 뽑고, 현재 위치의 요소와 서로 교환(swap)하여 새로운 순열을 만듭니다.
시간 복잡도
보고소트는 구현이 매우 간단하지만 효율성은 극히 낮습니다. 평균 시간 복잡도는 O((n+1)!) 수준이며, 최악의 경우 이론상 끝나지 않을 수도 있습니다. 따라서 실무에서는 거의 사용되지 않고, 정렬 알고리즘의 개념을 재미있게 익히기 위한 학습용 예제로 활용됩니다.
결론
이번 글에서는 파이썬으로 보고소트(순열 정렬) 프로그램을 작성하는 방법을 알아보았습니다. 무작위 셔플과 정렬 검증이라는 두 가지 핵심 로직만으로 정렬을 완성할 수 있다는 점에서, 알고리즘 입문자에게 유익한 예제가 됩니다.