컴퓨터구조 MIPS MARS HW2 Heapsort

1. Heap Sort Algorithm

힙 정렬은 배열을 정렬하는 데 사용되는 비교 기반의 정렬 알고리즘이다. 이 알고리즘은 힙 자료구조를 이용하여 효율적으로 정렬을 수행한다. 힙은 완전 이진 트리의 특성을 가지며 최대 힙과 최소 힙의 두 가지 형태가 있다. 최대 힙에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같다. 힙 정렬에서는 최대 힙을 사용하여 정렬을 진행한다. 힙 정렬의 과정은 크게 두 단계로 나눌 수 있다. 첫 번째 단계는 주어진 배열을 최대 힙으로 변환하는 과정이다. 이 과정은 배열의 중간 지점에서 시작하여 맨 앞쪽에 있는 루트 노드를 기준으로 자식 노드와 비교하며 상향식으로 힙 속성을 유지하는 식으로 진행된다. 각 노드를 힙ify(hypify)하는 과정은 O(log n)의 시간 복잡도를 가지며, 전체 배열을 힙으로 만드는 데는 O(n) 시간이 소요된다. 이때 배열의 크기가 n이라면, 배열의 중간 지점부터 시작해 힙화 과정을 수행하게 되고, 이는 실질적인 연산 횟수를 줄여준다. 두 번째 단계는 힙에서 최대값을 추출하여 정렬된 배열에 저장하는 과정이다. 최대 힙의 루트 노드는 항상 배열에서 가장 큰 …