보고 정렬
 | |
| 분류 | 정렬 |
|---|---|
| 자료 구조 | 배열 |
| 최악 시간복잡도 | 무제한 (랜덤화 버전),[1] O((n+1)!) (결정화 버전) |
| 최선 시간복잡도 | O(n)[1] |
| 평균 시간복잡도 | O((n+1)!)[1] |
| 공간복잡도 | O(1) |
컴퓨터 과학에서 보고정렬(bogosort[1][2], 또한 permutation sort, stupid sort[3] 또는 slowsort[4][5])은 정렬 알고리즘 중 하나로 비효율적인 것에 속한다. 보고 정렬의 이름은 단어 "bogus"에서 유래된다. 보고정렬은 정렬하는데 유용하게 사용되지는 않지만, 실제로 사용되는 알고리즘과 비교를 통한 교육에서 사용될 수 있다. 또한 논리형 프로그래밍의 예시로서 사용되기도 한다. 만약 보고 정렬이 카드 뭉치를 정렬하는데 사용될 때 시행되는 과정은 다음과 같다.
의사 코드[편집]
- 영어
while not isInOrder(list):
shuffle(list)
- 한국어
(리스트가 배열될 때)까지 실행하기:
리스트 섞기
예시[편집]
표준 ML의 셔플을 사용한 코드 예는 아래와 같다.
val _ = load "Random";
load "Int";
val rng = Random.newgen ();
fun select (y::xs, 0) = (y, xs)
| select (x::xs, i) = let val (y, xs') = select (xs, i-1) in (y, x::xs') end
| select (_, i) = raise Fail ("Short by " ^ Int.toString i ^ " elements.");
(* Recreates a list in random order by removing elements in random positions *)
fun shuffle xs =
let fun rtake [] _ = []
| rtake ys max =
let val (y, ys') = select (ys, Random.range (0, max) rng)
in y :: rtake ys' (max-1)
end
in rtake xs (length xs) end;
fun bogosort xs comp =
let fun isSorted (x::y::xs) comp = comp(x,y) <> GREATER andalso isSorted (y::xs) comp
| isSorted _ comp = true;
val a = ref xs;
in while(not(isSorted (!a) comp)) do (
a := shuffle (!a)
); (!a) end;
런타임 및 종결[편집]
만약 정렬해야하는 원소들이 각각 독립되어 있다면, 평균적으로 시행되는 비교 횟수는 회이며, 평균적으로 시행되는 섞음의 횟수는 회이다.[1] 평균적으로 시행되는 섞음의 횟수는 비교 횟수보다 빨리 증가한다. 이는 원소들이 순서대로 정렬되어있지 않을 경우, 적은 횟수의 비교 끝에 바로 정렬되지 않은 상태라는 것이 발견되지만, 섞음의 횟수는 이와 다르게 정렬해야 하는 배열의 크기에 비례하기 때문이다. 최악의 경우, 비교의 횟수와 섞음의 횟수에는 끝이 없으며, 이는 동전을 던졌을 때 앞면이 계속 나올 수 있는 것과 같은 원리이다. 최선의 경우는 주어진 배열이 이미 정렬되어 있는 경우이다. 이때 시행되는 비교의 횟수는 회이며, 섞음은 단 한번도 시행되지 않는다.[1]
한정된 개수의 숫자 배열에 대하여 이 알고리즘의 런타임은 유한하다. 이는 무한 원숭이 정리에 기반하여 내릴 수 있는 결론이며, 섞음 후 정렬된 배열이 나올 수 있는 확률이 조금이라도 있기에, 여러번의 수행은 거의 확실히 정렬된 배열을 만들어 낼 수 있다. 하지만 랜덤한 섞음이 아닌 유사난수 생성기를 이용하여 섞음이 시행된다면 이 알고리즘에는 끝이 없을 수도 있다.
각주[편집]
- ↑ 가 나 다 라 마 바 Gruber, H.; Holzer, M.; Ruepp, O., 〈Sorting the slow way: an analysis of perversely awful randomized sorting algorithms〉, 《4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007》 (PDF), Lecture Notes in Computer Science 4475, Springer-Verlag, 183–197쪽, doi:10.1007/978-3-540-72914-3_17.
- ↑ Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), 〈Backtracking, interleaving, and terminating monad transformers: (functional pearl)〉, 《Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05)》 (PDF), SIGPLAN Notices, 192–203쪽, doi:10.1145/1086365.1086390, 2012년 3월 26일에 원본 문서 (PDF)에서 보존된 문서, 2013년 3월 31일에 확인함
- ↑ E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
- ↑ Naish, Lee (1986), 〈Negation and quantifiers in NU-Prolog〉, 《Proceedings of the Third International Conference on Logic Programming》, Lecture Notes in Computer Science 225, Springer-Verlag, 624–634쪽, doi:10.1007/3-540-16492-8_111.
- ↑ Naish, Lee (June 1995), 《Pruning in logic programming》, Tech. Report 95/16, Melbourne, Australia: Department of Computer Science, University of Melbourne, CiteSeerX: 10.1.1.54.2347.
외부 링크[편집]
- BogoSort on WikiWikiWeb
- 비효율적 정렬 알고리즘
- Bogosort: an implementation that runs on Unix-like systems, similar to the standard sort program.
- Bogosort and jmmcg::bogosort[깨진 링크(과거 내용 찾기)]: Simple, yet perverse, C++ implementations of the bogosort algorithm.