컴퓨터구조 MIPS MARS HW2 Heapsort

소개

"컴퓨터구조 MIPS MARS HW2 Heapsort"에 대한 내용입니다.

목차

1. Heap Sort Algorithm

2. 코드 분석
2-1) 입출력
2-2) swap
2-3) heapify
2-4) heapsort

3. 실행 결과

본문내용

최대 힙(max heap)이란, 각 노드의 키 값이 자식의 키 값보다 큰 완전 이진 트리이다. 또한 모든 배열은 완전 이진 트리로 변환할 수 있다. 완전이진 트리로 나타낸 Figure 2에서처럼 자식 노드에 접근하고자 하려면 어떻게 해야 할까? 부모 노드의 index를 p, 왼쪽에 위치한 자식 노드의 인덱스를 l, 오른쪽에 위치한 자식 노드의 인덱스를 r이라고 하면 l=2*p, r=2*p+1로 하여 인덱스로써 접근할 수 있다. 하지만 C언어에서는 배열의 인덱스가 0에서부터 시작되므로 l=2*p+1, r=2*p+2 가 된다. 완전이진 트리에서는 마지막 레벨이 아닌 각 레벨에서 원소의 수가 그 이전 레벨 원소 수의 두배로 결정되기 때문에 이러한 연산에 의한 접근이 가능하다.
가장 큰 값이 첫번째 노드로 오게 하는 최대 힙을 이용해서 배열이 오름차순으로 정렬되도록 할 수 있음을 알아보자. 말단에 있는 leaf노드들을 제외한 n/2개의 노드에 대해 자식 노드들과 최대 힙 구조를 이루도록 교환 연산을 모든 노드에 대해 수행하면, 가장 큰 원소가 가장 위에 올 것이다.

참고자료

· 없음