자료구조 프로그래밍 과목을 배우면서 c++로 작성한 힙 정렬입니다.
#include <iostream>
using namespace std;
template <class T>
void PrintArray(T *a, const int n)
{
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
}
template <class T>
void Adjust(T *a, const int root, const int n)
{
//자료는 a[1:n]에 저장되어 있고, root의 좌측트리와 우측트리가 Heap인
//상태에서 root를 포함하여 heap가 되게 한다
T e = a[root]; //root 위치에 있는 노드 copy
int j;
for (j = 2 * root; j<=n; j *= 2)
{
if (j < n&&a[j] < a[j + 1]) //왼쪽 자식보다 오른쪽 자식이 크다면
j++;
if (e >= a[j]) //e는 j의 부모여야한다
break;
a[j / 2] = a[j]; //부모가 자식 위치로 내려온다
}
a[j / 2] = e; //해당 위치에 copy한 노드 저장
}
template <class T>
void HeapSort(T *a, const int n)
{
for (int i = n / 2; i >= 1; i--) //Adjust n/2번 진행(그 이후는 다 단말노드이므로 정렬할 필요가 없다)
Adjust(a, i, n);
for (int i = n - 1; i >= 1; i--)
{
swap(a[1], a[i + 1]); //i+1번째 위치에 정렬이 제일 큰 값을 저장
Adjust(a, 1, i); //a[1]의 자료 이동으로 a[1:i]를 heap로 바꿈
}
}
int main(void)
{
int a[] = { 0, 26, 5, 77, 1, 61, 11, 59, 15, 48, 19 }; //0번째는 사용 안됨
int n = sizeof(a) / sizeof(int) - 1; //0번째 성분 제외
cout << "Before Sorting : ";
PrintArray(a, n);
HeapSort(a, n);
cout << "After Sorting : ";
PrintArray(a, n);
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~