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

이번 절은 교환에 의한 정렬에 대한 내용이다.

기본적으로 순서에 맞지 않는 원소 쌍이 더 이상 존재하지 않을 때까지
각 쌍들을 교체하는 방법이다.(체계적으로)

 

직접 삽입 방법도 일종의 교환이라고 볼 수 있다.

특별히 이번 절에서는 교환선택(버블정렬), 병합 교환(배처의 병렬 정렬), 분할 교환(퀵 정렬) 기수 정렬

로 교환이 주도적인 특징인 네 종류의 정렬 방법에 대해 알아볼 것이다.

 

거품 정렬 : 순서가 맞지 않으면 교환하는 방식.

거품 정렬-개선 : 개선을 해도 큰 의미가 없음. 직접 삽입보다 효율 떨어짐

배처의 병렬 정렬 : 셸 정렬과 유사하나 교환들이 전파될 필요가 없는 방식

퀵 정렬 : 한 레코드를 선택해서 그것을 정렬된 파일에서 위치할 최종 위치로 이동. 최종 위치를 결정하는 도중에 왼쪽에 현재 레코드의 키보다 더 큰 키들이 존재하지 않도록, 오른쪽에는 그보다 더 작인 키들이 존재하지 않도록 배치

기수 정렬 : 퀵 정렬과 유사하나 기수(radix) 2 표현에 의존하는 정렬