[자료구조]CH9. 정렬(히프 정렬~트리 정렬)

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부날짜 : 21.04.03

 

<Section  9> 히프 정렬

 

1. 히프정렬의 이해

 

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

[자료구조]CH7. 트리(히프)

히프에서는 항상 가장 큰 원소가 루투 노드가 되고, 삭제 연산을 하면 항상 루토 노드의 원소를 삭제하여 반환하는 특징이 있다. 

그러므로 최대히프에서 삭제연산을 수행하면 내림차순으로 정렬된 원소를 얻을 수 있다.

 

* 순서

① 초기 상태 : 정렬되지 않은 자료를 삽입 연산을 이용해 최대 히프를 구성한다.

② 히프의 삭제연산을 수행하여 루트 노드(가장 큰 원소)를 구한 후 배열의 가장 마지막 자리에 저장한다.

③ 나머지 히프를 최대히프로 재구성한다.

④ ②~③반복

⑤ 나머지 히프가 공백 히프가 될 때까지 삭제와 히프 재구성을 반복하고 공백 히프가 되면 히프 정렬을 종료한다.

 

히프 정렬의 시간 복잡도는 O(nlog2(지수)n)

 

 

<Section 10> 트리 정렬

 

1. 트리 정렬의 이해

 

 이진 탐색 트리를 이용하여 정렬하는 방법이다.

중위 순회 방법으로 순회하며 꺼내면 오름차순으로 정렬이 가능하다.

[자료구조]CH7. 트리(이진 탐색 트리)

* 순서

① 정렬할 원소들을 차례대로 삽입하여 이진 탐색 트리를 구성한다.

② 중위 순회 방법으로 순회하면서 원소 저장(LRD)

 

 

2. 트리 정렬 알고리즘

 

 treeSort(a[] , n)

    for (i ← 0 ; i < n ; i ← i+1) do

        insert(BST , a[i]); //이진 탐색 트리 삽입 연산

    inorder(BST); //중위 순회 연산

 end treeSort()