최소값을 선택하는 정렬

55. [22] M > 1일 때, 분할 원소가 세 키 (28)의 중앙값이 되도록 프로그램 Q를 수정하는 방법을 보여라.

56. [M43] 연습문제 55에서처럼 세 원소의 중앙값을 취하도록 프로그램이 수정되었을 때 알고리즘 Q의 실행 시간에서 발생하는 양들의 평균 행동을 분석하라. (연습문제 29를 보라.)

정렬 기법의 또 다른 중요한 패밀리는 반복 선택의 아이디어에 기반한다. 가장 단순한 선택 방법은 아마도 다음과 같다:

정렬 기법의 또 다른 중요한 패밀리는 반복 선택의 아이디어에 기반한다. 가장 단순한 선택 방법은 아마도 다음과 같다:

i) 가장 작은 키를 찾는다; 해당 레코드를 출력 영역으로 전송한다; 그런 다음 키를 ∞ 값(어떤 실제 키보다 높다고 가정됨)으로 대체한다.

ii) 단계 (i)를 반복한다. 이번에는 가장 작은 키가 ∞로 대체되었으므로 두 번째로 작은 키가 선택된다.

ii) 단계 (i)를 반복한다. 이번에는 가장 작은 키가 ∞로 대체되었으므로 두 번째로 작은 키가 선택된다.

iii) N개의 레코드가 선택될 때까지 단계 (i)를 계속 반복한다.

선택 방법은 정렬을 진행하기 전에 모든 입력 항목이 존재해야 하며, 최종 출력을 순서대로 하나씩 생성한다. 이는 본질적으로 삽입의 반대이다. 삽입에서는 입력이 순차적으로 수신되지만 정렬이 완료될 때까지 최종 출력을 알 수 없다.