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

이번 절은 배분에 의한 정렬에 대한 내용이다.

본질적으로 병합과는 정확히 반대라고 할 수 있는 개념으로

전자 컴퓨터 이전 천공 카드들을 정렬하는데 주로 쓰여왔다고 한다.

 

트럼프 카드를 정렬하는 방법을 예를 든다면

일단 13개의 더미로 나누고(A, 1, 2, 3... K)

그 후에 문양 별로 정렬하면 되는 방법이다.

 

각 더미들은 단방향 링크드리스트의 자료구조를 활용하면 된다.

 

컴퓨터에서의 내부 정렬은 기수 정렬이 다른 방법에 비해 효율적이라고 한다.