11장 정렬 선택 방식<힙 정렬, 트리 정렬>

정렬

순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다.

 

내부 정렬

1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵)

2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸)

3. 병합 방식 - 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)

4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수)

5. 선택 방식 - 이진 트리를 사용하여 정렬하는 방식(힙, 트리)

 

정렬되지 않은 { 69, 10, 30, 2, 16, 8, 31 }을 예시로 들겠다.

힙 정렬

힙 정렬은 힙 자료구조를 이용하여 정렬하는 방법이다.

 

1. 정렬할 원소가 8개 이므로 노드가 8개인 완전 이진 트리를 만들고, 최대 힙으로 구성한다.

2. 힙에 삭제 연산을 수행하여 루트 노드의 원소 69를 구해서 배열의 비어있는 마지막 자리에 저장하고, 나머지 원소들에 대해서 최대 힙으로 재구성한다.

3. 힙에 삭제 연산을 수행하여 루트 노드의 원소 31를 구해서 배열의 비어있는 마지막 자리에 저장하고, 나머지 원소들에 대해서 최대 힙으로 재구성한다.(룰에 따라 반복)

4. 힙에 삭제 연산을 수행하여 루트 노드의 원소 2를 구해서 배열의 비어있는 마지막 자리에 저장한다. 나머지 원소들에 대해서 최대 힙으로 재구성해야 하는데, 이미 공백 힙이 되었으므로 힙 정렬을 종료한다.

 

트리 정렬

트리 정렬은 이진 탄색 트리를 이용하여 정렬하는 방법이다. 정렬할 원소들을 이진 탐색 트리로 구성하고 중위 순회 방법을 사용하여 이진 탐색 트리의 원소들을 순회하여 꺼내면 오름차순 정렬이 된다.

 

1. 정렬할 원소 8개를 차례대로 트리에 삽입하여 이진 탐색 트리를 구성한다.

2. 이진 탐색 트리를 중위 순회 방법으로 순회 하면서 원소를 완성한다.