Bogo sort (보고 정렬) 알고리즘
유튜브를 보다가 우연히 필자의 눈에 들어온 영상 하나가 있었다. 정렬을 비교해주는 영상이었는데, Bogo sort 부분 영상에서 음.. 이거 정렬되고 있는거 맞아? 싶었다.
<영상 링크>
찾아보니 정렬방법이 매우 충격적(?)이라 여러분들에게 같이 이 충격적인 정렬방법을 공유하고자 한다.
(정렬 알고리즘이라고 해서 그리 어려운 내용은 아니고 장난스러운 내용에 가까우니 부담없이 봐도 된다.)
정렬 메커니즘은 아주 쉽다. '운'
무슨 말인가 싶을 것이다. 좀 쉽게 예로들어보자면 이미 뒤섞여 있는 카드뭉치가 있다고 가정하자. 그 것을 여러분은 무작위로 셔플하여 정렬을 한다.
??? 정렬이 되긴 합니까? 라고 한다면 되긴 된다만 언제 될지는 보장 못한다고밖에 말을 해줄 수가 없다. 동전던지기를 하여 100번 연속으로 앞면이 나오게 하는 게임같은 거랄까? 현실적으로 힘들지만 가능성이 0%인 것은 아닌... 마치 내가 로또를 맞겠지라고 희망사항을 품고 매주 사가는 멍청한 우리와 닮았다. 뭐 당첨되면 그 자는 승리자고..
좀 더 찾아보니 Bogo가 Buy One Get One의 의미인 줄 알았는데, 이게 아니란다.
Bogo의 어원이 Bogus 라는 뜻에서 나왔는데 슬랭(Slang)언어란다. 의미는 '가짜'를 의미.. 좀 더 의미를 구체적으로 보자면 짝퉁이라는 단어와 가장 근접한 의미인 듯 하다.
Bogo sort에 대한 설명은 여기에 잘 나와있다.
en.wikipedia.org/wiki/Bogosort#cite_note-Fun07-1
링크 들어가기 귀찮을 수 있으니 이미지도 첨부하겠다.
지금까지 설명만 들어도 얼마나 비효율적인 정렬 알고리즘인지 감이 올 것이다. 그래서인지 위키피디아에서도 '멍청이 정렬', '샷건 정렬', '원숭이 정렬'같은 이름으로 알려져있다고 한다. (샷건 정렬 단어가 마음에 든다)
대강 의사코드로 보자면 다음과 같이 짤 수 있다.
while not Sorted(list) do
shuffle (list)
done
list에 정렬이 안되어있어? 그럼 셔플해. 또 정렬 안됐어? 그럼 또 셔플해... 이제 언제 끝날지 모르는 늪으로 빠져드는 것이다.
그래도 이렇게 의사코드로만 남겨놓긴 좀 아쉬우니 한 번 제대로 구현을 해보면서 테스트를 해보자. 필자가 주로 다루는 Java, Python, C, C++ 이렇게 네 가지 버전으로 구현해보고 테스트를 해보겠다.
1. Java
import java.security.SecureRandom;
import java.util.Arrays;
public class BogoSort {
static int[] sortedArr; // 비교를 위한 사전 정렬된 배열
static int[] arr; // 정렬할 배열
static int SIZE = 11;
static int RANGE = 14234;
// Random class 대신 SecureRandom을 썼음
static SecureRandom random = new SecureRandom();
public static void main(String[] args) {
arr = new int[SIZE];
sortedArr = new int[SIZE];
for (int i = 0; i < 7; i++) {
Bogosort();
System.out.println();
}
}
static void Bogosort() {
int shuffle_count = 0;
for (int i = 0; i < SIZE; i++) {
int val = random.nextInt(RANGE);
arr[i] = val;
sortedArr[i] = val;
}
// 사전 정렬 배열 정렬
Arrays.sort(sortedArr);
// 정렬되지 않은 배열 출력
System.out.println("[Not Sorted array]");
for(int i = 0; i < SIZE; i++) {
System.out.print(arr[i] + " ");
}
// 정렬 되어있는 배열 출력
System.out.println("\n[Sorted array]");
for(int i = 0; i < SIZE; i++) {
System.out.print(sortedArr[i] + " ");
}
System.out.println();
// Time Check
long start = System.nanoTime();
// 정렬될 때까지 섞는다.
while (!isSorted()) {
shuffle();
shuffle_count++;
}
long end = System.nanoTime();
// 섞은 횟수와 걸린 시간(초) 출력
System.out.println("Shuffle count : " + shuffle_count + "\nTime : " + (end - start) * 1e-9 + "s");
}
// Shuffle
static void shuffle() {
for (int i = 0; i < SIZE; i++) {
int index1 = random.nextInt(SIZE);
int index2 = random.nextInt(SIZE);
// 랜덤으로 지정 된 두 인덱스의 값을 서로 교환
swap(index1, index2);
}
}
static void swap(int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
// 정렬된 상태인지 확인
static boolean isSorted() {
for (int i = 0; i < SIZE; i++) {
if (arr[i] != sortedArr[i]) {
return false;
}
}
return true;
}
}
참고로 랜덤 함수는 Math.random, Ramdom클래스, SecureRandom클래스 중 아무거나 써도 된다. 그래도 좀 더 분포가 고른 랜덤클래스를 쓰기 위해 필자는 SecureRandom을 썼다.
그리고 좀 더 자신의 시간을 빼앗기고 싶다면 저 SIZE 변수를 조정하여 더욱 큰 수로 하면 된다. 밑의 결과를 보면 알겠지만, 잘못하면 하루 종일 안끝나서 여러분 스스로 먼저 종료하는 수가 있으니... 남는 여유시간만큼 적당하게 써보도록 하자. 아니면 친구랑 내기를 하기 위한 용도로 써도 될 것 같기도 하다.
터미널에서 실행해봤더니 11개의 원소를 정렬하는데 정말 시간이 들쑥날쑥이다. 빠르면 4초.. 느리면 361초.. 원래는 100개 사이즈로 하려다 1시간이 지나도 안되길래 그냥 포기했다. 혹시 시간 여유가 되시는 분이 한 번 해보시고 몇 초 걸렸는지 알려주신다면 정말 감사드립니다.
2. Python
파이썬의 경우 자바보다 속도 차제는 느리다.. 연산 자체가 느리다보니 아무래도 평균 시간 자체는 전체적으로 길어질 것같다. 일단 코드는 다음과 같다.
import random as rnd
import time
import numpy as np
sortedArr = []
arr = []
SIZE = 11
RANGE = 14234
# 정렬된 상태인지 체크
def isSorted():
if(np.array_equal(arr, sortedArr)):
return True
else:
return False
def shuffle() :
global arr
for i in range(SIZE):
index1 = rnd.randrange(0, SIZE)
index2 = rnd.randrange(0, SIZE)
# 인덱스 교환(swap)
arr[index1], arr[index2] = arr[index2], arr[index1]
def Bogosort():
shuffle_count = 0
global sortedArr
global arr
for i in range(SIZE):
val = rnd.randrange(0, RANGE)
arr.append(val)
sortedArr.append(val)
# 사전 정렬 배열 정렬
sortedArr.sort()
# 정렬되지 않은 배열 출력
print("[Not Sorted array]")
print(arr)
# 정렬된 배열 출력
print("[Sorted array]")
print(sortedArr)
# 타임 체크
start = time.time()
#정렬될 때 까지 계속 셔플한다
while(isSorted() == False):
shuffle()
shuffle_count= shuffle_count + 1
end = time.time()
print("Shuffle count : ",end = '')
print(shuffle_count)
print("Time : ", end = '')
print(end - start)
sortedArr.clear()
arr.clear()
for i in range(7):
Bogosort()
print()
수행시간은 다음과 같다. 물론 랜덤이다보니... 빠르면 80초였지만, 늦은 것은 25분가량 걸렸다.
3. C++
C++의 경우 자바보다 속도 차제는 빠르다. 그러다보니 평균 시간 자체는 조금 빠르나 운나쁘면 1, 2번보다 느릴수도.. 코드는 다음과 같다.
#include <iostream>
#include <random>
#include <time.h>
using namespace std;
static int SIZE = 10;
static int* arr;
static int* sortedArr;
static int RANGE = 14234;
static random_device rd;
bool isSorted(void) {
for(int i = 0; i < SIZE; i++){
if(arr[i] != sortedArr[i]){
return false;
}
}
return true;
}
void shuffle() {
mt19937 randset(rd());
uniform_int_distribution<int> rnd(0, SIZE);
for(int i = 0; i < SIZE; i++){
int index1 = rnd(randset);
int index2 = rnd(randset);
swap(arr[index1], arr[index2]);
}
}
void Bogosort(){
int shuffle_count = 0;
mt19937 randset(rd());
uniform_int_distribution<int> rnd(0, RANGE);
arr = new int[SIZE];
sortedArr = new int[SIZE];
for(int i = 0; i < SIZE; i++){
int val = rnd(randset);
arr[i] = val;
sortedArr[i] = val;
}
// 사전 정렬 배열 정렬
sort(sortedArr, sortedArr + SIZE);
// 정렬되지 않은 배열 출력
cout << "[Not Sorted array]" << endl;
for(int i = 0; i < SIZE; i++){
cout << arr[i] << " ";
}
// 정렬된 배열 출력
cout << endl << "[Sorted array]" << endl;
for(int i = 0; i < SIZE; i++){
cout << sortedArr[i] << " ";
}
cout << endl;
// 타임 체크
clock_t start = clock();
while(!isSorted()){
shuffle();
shuffle_count++;
}
clock_t end = clock();
cout << "Shuffle count : " << shuffle_count << endl;
cout << "Time : "<< ((double)(end - start)/CLOCKS_PER_SEC) << "s" << endl;
// clear
fill(arr, arr+SIZE, 0);
fill(sortedArr, sortedArr+SIZE, 0);
}
int main(){
for(int i = 0; i < 7; i++){
Bogosort();
cout << endl;
}
}
C++의 경우는 앞서 SIZE=11 인 경우와 달리 10 Size로 시작했다. 4개 언어를 모두 테스트하다보니 시간이 많이 걸려서,, 양해해주길 바란다.
아래는 C++ 결과다.
4. C
C는 동적할당을 쓸려다가 필자가 MacOS다보니 포인터가 가리키는 힙 메모리 할당 크기를 _msize()가 아닌 malloc_size() 함수를 써야한다. 애초에 표준함수가 아닌지라.. 만약 동적할당을 하고싶다면 *arr, *sortedArr 포인터에 malloc으로 메모리를 할당해주고, 배열 사이즈를 구할 때엔 윈도우는 malloc.h에 있는 _msize()를 써서 int사이즈를 나누어주면 되고, MacOS의 경우는 malloc_size()를 써주면 된다.
다만, 주의할 것이 위와같이 하는 경우는 malloc()함수가 요청한 크기보다 더 많이 메모리를 할당할 수 있기 때문에 반드시 사이즈 체크를 해야한다.
그리고 C언어는 bool타입이 없는 것이 아니라 C99부터 지원하는 엄연한 표준 함수이니.. 이해하기 쉽도록 stdbool.h을 포함시켜 bool타입을 사용할 것이다. 벌써 20년도 넘게 지원되고 있는데, 왜 없다고 가르치는걸까..
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <memory.h>
static int SIZE = 10;
static int arr[10];
static int sortedArr[10];
static int RANGE = 14234;
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int compare(const void *a, const void *b) // 오름차순 비교 함수 구현
{
int num1 = *(int *)a;
int num2 = *(int *)b;
if (num1 < num2)
return -1;
if (num1 > num2)
return 1;
return 0;
}
bool isSorted(void) {
for(int i = 0; i < SIZE; i++){
if(arr[i] != sortedArr[i]){
return false;
}
}
return true;
}
void shuffle() {
srand((unsigned int) time(NULL));
for(int i = 0; i < SIZE; i++){
int index1 = rand() % SIZE;
int index2 = rand() % SIZE;
swap(&arr[index1], &arr[index2]);
}
}
void Bogosort(){
int shuffle_count = 0;
srand((unsigned int) time(NULL));
for(int i = 0; i < SIZE; i++){
int val = rand() % RANGE;
arr[i] = val;
sortedArr[i] = val;
}
// 사전 정렬 배열 정렬
qsort(sortedArr, SIZE, sizeof(int), compare);
// 정렬되지 않은 배열 출력
printf("[Not Sorted array]\n");
for(int i = 0; i < SIZE; i++){
printf("%d ", arr[i]);
}
// 정렬된 배열 출력
printf("\n[Sorted array]\n");
for(int i = 0; i < SIZE; i++){
printf("%d ", sortedArr[i]);
}
printf("\n");
// 타임 체크
clock_t start = clock();
while(!isSorted()){
shuffle();
shuffle_count++;
}
clock_t end = clock();
printf("Shuffle count : %d\n",shuffle_count);
printf("Time : %.6lfs\n", ((double)(end - start)/CLOCKS_PER_SEC));
// clear
memset(arr, 0, SIZE * sizeof(int));
memset(sortedArr, 0, SIZE * sizeof(int));
}
int main(){
for(int i = 0; i < 7; i++){
Bogosort();
printf("\n");
}
return 0;
}
필자는 운이 드럽게 없나보다. 이거 테스트하느라 시간 다 갈 것 같아 그냥 5개로 했다. 코드에서는 10개로 되어있는데, 만약 돌렸을 때 결과가 한참동안 안나온다면 그 건 여러분의 운이....
시간복잡도는 상한선이 없어(운이 드럽게 없다면 영원히 안끝날수도 있기 때문에..) 빅오(Big-O)표기법으로는 O(∞)라고 해야하나.. 애초에 무한대 의미 자체가 수가 아닌데 이런 표현이 존재하긴 할까 싶다.. 그래도 세타 표기법으로는 대강 예상은 할 수 있다.
음.. N 사이즈의 배열이 있다면 정렬된 상태의 배열이 나올 확률은 (1 / N!) 이니 역으로 말하면 정렬된 순열을 생성하기 전까지 생성되는 배열(순열)의 수는 N!이고, 이 놈이 정렬되어있는지, 아닌지를 확인하기 위해 매번 배열을 한 번 탐색을 하기 때문에 N이 곱해져야 할 것이다. 즉, θ(N · N!) 이라는 결과가 나온다. 보통은 이를 반쯤 혼용해서 빅오로도 표기하니 O(N · N!) 이라고 해도 될 듯.
(참고로 N=10일 때는 399,168,000이라는 숫자가 나온다! 정말 이렇게 비효율적일수가..)
대신에 엄청 운이 좋을경우 O(N)만에 가능하다.
참고로 로또 1등 확률이 1/8,145,060 이라 하니 여러분들은 위 코드를 가지고 배열 크기를 48로 설정하고 돌리자! 만약 1초안에 정렬이 되면 당신은 오늘 운이 좋은 것이니 로또를 사보는 것도..? 사행성 조장같으니 말은 더이상 안하겠다.
'이모저모' 카테고리의 다른 글
숏코딩을 해보자 (Code Golf) (8) | 2020.07.26 |
---|