'비교기반정렬' 태그의 글 목록

비교 기반 정렬은, 키 2개를 가지고 비교를 하는 것들을 말합니다. 예를 들어서, 우리가 sort 함수를 호출할 때 이런 식으로 compare 함수를 재작성을 합니다. 그러면 이것은 key a와, b를 비교한 것입니다. 대다수의 정렬은 이 키 값 2개를 비교해서 순서를 ordering 한다고 보시면 됩니다. 물론 예외가 몇 개 있는데요. 카운트, 버킷, 기수 정렬 등이 예외입니다. 크기가 n인 배열이 있습니다. 물론, 이 n개의 수는 서로 다른 수라고 합시다. 보통 그렇게들 많이 주어지니까요. 그러면, 서로 다른 수 n개를 순서 고려해서 배열하는 가짓수는 n!입니다. 즉, 길이가 n인 순열이 n!개가 나온다는 것입니다. 예를 들어서 n = 4라고 해 봅시다. 그러면 1번째 칸에는 4개 중 하나만 들어가면..