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

드디어 세 번째 커누스 형의 책!

 

첫 번째 장은 정렬에 대한 내용이다.

항목들을 오름차순 또는 내림차순으로 재배치하는 걸 공부할 예정이다.

사실은 sorting보단 ordering의 의미라고 볼 수 있겠다.

 

정렬의 가장 중요한 응용들

1. 통일성 문제 풀기 : 같은 id를 가진 모든 항목을 한 곳에 모으는 문제들.

2. 둘 이상의 파일들에 있는 항목들 부합 : 동일 순서로 정렬되어있을 시, 백업 과정 없이 한 번만 순차 검색해서 일치하는 항목 찾을 수 있음

3. 키 값으로 정보 검색 : 정렬은 검색에도 도움을 줌. 실제로 알파벳 순으로 정렬된 목록은 수치적 정보가 부정확하게 계산되어있더라도 신뢰성이 있어 보임

 

내부 정렬 : 하나의 레코드들 전부가 컴퓨터의 고속 임의 접근 메모리 안에 있는 경우에 쓰임

외부 정렬 : 한 번에 메모리에 담을 수 있는 개수 이상의 레코드들이 존재하는 경우에 쓰임