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

이번 절은 선택에 의한 정렬이다.

 

선택 정렬은

1. 가장 작은 키를 찾고 해당 레코드를 출력 영억으로 보냄. 해당 키 값을 가장 큰 값으로 대체

2. 1을 반복. 두 번째로 작은 키를 선택

3. N개의 레코드들이 선택될 때까지 1을 반복

 

삽입 정렬은 정렬이 완료되기 전까지 최종 출력을 전혀 알 수 없으나

선택 정렬은 한 번에 하나씩 최종 결과를 출력.

 

직접 선택을 개선하기 위해서는 몇 개씩 그룹핑을 해서 최댓값을 구하는 방법이 있다.

몇 개를 n 차라고 부른다. 트리 선택이라고도 부른다.

 

트리 선택 정렬의 원리는 '토너먼트'와 유사하다.

탈락식 토너먼트의 원리를 적용한 게 힙 정렬이다.

 

힙 정렬 : 힙이라는 자료구조의 형태로 만들어 놓고 정렬

우선순위 대기열 : 힙 정렬을 활용하여 우선순위 대기열을 만들어서 활용