The Art of Computer Programming 3: 정렬과 검색(개정 2판)

정렬과 검색을 통한 이상적인 알고리즘의 발견

이 책은 다른 기본적인 구조적 착안들에 선형 순서 자료의 개념을 더하는 것이므로, 제1권 제2장의 정보 과학 내용과 관련해서, 그 자연스러운 속편에 해당한다. "정렬과 검색"이라는 제목 때문에, 이 책을 범용 정렬 루틴이나 정보 조회를 위한 응용프로그램에 관계되는 시스템 프로그래머들만을 위한 책으로 오해할 수도 있으나 사실 이 책에서 다루는 내용은 다음과 같은 다양한 종류의 주요 주제들에 대한 이상적인 틀을 제공한다.

• 좋은 알고리즘은 어떻게 발견되는가?
• 알고리즘과 프로그램을 개선하려면?
• 알고리즘의 효율을 수학적으로 분석하려면?
• 같은 과제를 위한 서로 다른 알고리즘들 중 적절한 것을 합리적으로 선택하려면?
• 어떤 의미 하에서 알고리즘이 "가능한 최고"임을 증명할 수 있는가?
• 컴퓨팅 이론이 현실의 고려사항들과 어떻게 연동되는가?
• 커다란 데이터베이스를 위해 테이프, 드럼, 디스크 같은 외부 기억장치들을 효율적으로 사용하려면?

주요 내용

• 순열과 조합 성질
• 내부 정렬
• 최적 정렬
• 외부 정렬
• 순차 검색
• 키 비교에 의한 검색
• 숫자별 검색
• 해싱
• 2차키에 의한 조회

"사실 프로그래밍에서 정렬과 검색이 중요하지 않다고 생각하는 사람은 별로 없을 것입니다. 오히려 더 중요한 질문은 "정렬과 검색 알고리즘들을 어느 선까지 파헤치고 분석해야 만족할 수 있을 것인가"일 것입니다. 이 책의 접근방식이 과도하게 집요하고 장황하다고 생각할 수도 있겠지만, 그런 의문에 대해서는 이 책의 저자 서문의 둘째 문단과 그 다음의 불릿 목록이 답이 될 것이며, 또한 제2권 역자 서문의 둘째, 셋째 문단도 나름의 답이 될 것입니다. 그리고 Beautiful Code : 38인의 코딩 명장들이 말하는 내 생애 가장 아름다운 코드(찰스 페촐드 외 37인 지음, 류광 옮김, 한빛미디어, 2007)의 제4장과 제7장에 나오는 Java 라이브러리 이진 검색 루틴의 버그 이야기도 많은 것을 말해 줍니다. 이 책 어딘가에 나오듯이 이진 검색은 개념이 제안된 지 12년이 지난 후에야 "버그 없는" 알고리즘이 등장했다고 하는데, 그 후 수십 년이 지났어도 여전히 점검할 것이 남아 있었던 것입니다!."
_역자 서문 중에서