[C] 보고 정렬 (bogo sort, stupid sort)

 정렬 알고리즘을 찾아보는 도중에 신기한 이름을 봤다. 보고 정렬, 멍청이 정렬.. 무슨 알고리즘이길래 멍청이라는 이름을 붙여줬나 했더니 무려 랜덤으로 데이터를 재배열해서 정렬을 하는 알고리즘이다! 

 정렬이 될 때까지 랜덤으로 돌리기 때문에 최악의 경우에는 영원히 정렬이 안될 수도 있다! 언제 정렬이 완료될 지는 아무도 모른다. 이름값을 하는 정렬이다.   

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int MAX_NUM = 10;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int isSorted(int *arr, int len) {

	int i, j;

	for (i = 0; i < len; i++) {
		for (j = i + 1; j < len; j++) {
			if (arr[i] > arr[j]) return 0;
		}
	}

	return 1;

}

int main() {


	int arr[MAX_NUM];

	int count = 0;

	int i, j;

	srand(time(NULL));
	
	for (i = 0; i < MAX_NUM; i++) {
		arr[i] = rand() % 1000 + 1;
	}

	printf("정렬 전 \n");
	for (i = 0; i < MAX_NUM; i++) {
		printf("%d ", arr[i]);
		if ((i + 1) % 10 == 0) printf("\n");
	}
	printf("\n");

	while (!isSorted(arr, MAX_NUM)) {

		i = rand() % (MAX_NUM + 1);
		j = rand() % (MAX_NUM + 1);

		while (i > j) {
			i = rand() % (MAX_NUM + 1);
			j = rand() % (MAX_NUM + 1);
		}

		swap(arr + i, arr + j);
		count++;

	}

	printf("정렬 후 \n");
	for (i = 0; i < MAX_NUM; i++) {
		printf("%d ", arr[i]);
		if ((i + 1) % 10 == 0) printf("\n");
	}
	printf("\n");

	printf("정렬한 횟수 : %d\n", count);

	return 0;

}

 100개는 너무 오래걸려서 10개로 줄여서 해봤는데 약 917만번 교환 끝에 정렬이 완료된 것을 볼 수 있다. 기도빨이 잘먹히면 꽤 빨리 정렬된다.