#5-3 The Art of Computer Programming - 정렬과 검색

이번장은 최적 정렬에 대한 내용이다.

가능한 최고의 정렬 방법이란 없지만, 각 케이스마다 최대한의 최고는 있을 수 있다.

정렬에서도 여러가지 방법이 발견되기는 했지만 아직도 답을 못 찾은 것도 많다.

 

첫 번째 절은 최소 비교 정렬에 대한 내용이다.

 

n개의 원소를 정렬할 때 필요한 최소 키 비교 횟수는 0이다.

왜냐면 비교를 전혀 수행하지 않는 기수 방법들도 있기 때문이다.

그렇기 때문에 비교 횟수를 세는 것만이 정렬의 효율을 측정하는 방법이라고 할 수는 없다.

그럼에도 불구하고 비교 횟수를 자세히 조사해 보는 것은 의미가 있다.

이러한 주제를 이론적으로 연구함으로 정렬 공정의 본성에 대한 유용한 통찰을 얻을 수 있다.

 

n개의 원소들을 중복된 비교 없이 정렬하는 하나의 비교 트리의 외부 노드 개수는 정확히 n!이다.

 

일반적으로 평균 비교 횟수를 최소화하는 문제는 어렵다고 한다.