힙 정렬 구현 및 테스트

  힙 정렬 

루트에 항상 가장 큰 값(혹은 가장 작은 값)이 오도록 정렬되는 힙을 사용하는 정렬 방식이다.

 

힙 만들기

입력되는 배열을 완전 이진트리로 가정하여 힙을 생성한다.

 

힙 생성 알고리즘

BuildHeap(A[], n)
{
    for i ← └n / 2┘ downto 1
    {
        Heapify(A, i, n);
    }
}

Heapfipy(A[], k, n)
{
    left ← 2k; right ← 2k + 1;
    // 작은 자식 고르기
    if (right ≤ n) then
    {
        if (A[left] < A[right]) then
        {
            smaller ← left;
        }
        else
        {
            smaller ← right;
        }
    }
    // 왼쪽 자식만 있는 경우
    else if (left ≤ n) then
    {
        smaller ← left;
    }
    // 자식이 없는 경우, 종료
    else
    {
        return;
    }
    if (A[smaller] < A[k]) then
    {
        A[k] ↔ A[smaller];
        Heapify(A, smaller, n);
    }
}

 

힙 정렬 알고리즘

힙을 만들어 데이터를 모두 삽입한 뒤 루트에서 하나씩 인출하여 순서대로 배열에 넣어준다.

 

힙 정렬 알고리즘

HeapSort(A, n)
{
    BuildHeap(A, n);
    for i ← n downto 2
    {
        A[1] ↔ A[i];
        힙 A가 힙 상태를 만족하도록 다시 정렬한다.
    }
}

 

※ 힙 정렬의 시간 복잡도는 힙을 생성하는 시간과 다시 정려하는 시간을 합쳐 Ο(nlogn)이 소요된다.

 

힙 정렬 구현

배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다.

 

HeapSort.hpp

#pragma once
#include "../Common.h"

void BuildHeap(int arr[], int n);
void Heapify(int arr[], int k, int n);

/// <summary>
/// 주어진 배열을 정렬한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="printData">중간 결과 출력 여부</param>
void HeapSort(int arr[], int n, bool printData = false)
{
	if (printData)
	{
		Common::PrintArray(arr, n);
	}

	BuildHeap(arr, n);
	for (int i = n - 1; i > 0; i--)
	{
		Common::Swap(arr, 0, i);

		if (printData)
		{
			Common::PrintArray(arr, n);
		}

		Heapify(arr, 0, i);
	}
}

/// <summary>
/// 힙을 생성한다.
/// </summary>
/// <param name="arr">힙으로 만들 배열</param>
/// <param name="n">배열의 길이</param>
void BuildHeap(int arr[], int n)
{
	for (int i = n / 2; i >= 0; i--)
	{
		Heapify(arr, i, n);
	}
}

/// <summary>
/// 배열을 힙으로 만드는 처리
/// </summary>
/// <param name="arr">힙으로 만들 배열</param>
/// <param name="k">기준 점</param>
/// <param name="n">배열의 길이</param>
void Heapify(int arr[], int k, int n)
{
	int left{ 1 }, right{ 2 };
	if (k > 0)
	{
		left = k * 2 + 1;
		right = k * 2 + 2;
	}

	if (left >= n)
	{
		return;
	}

	int bigChild = left;
	if (right < n)
	{
		if (arr[right] > arr[left])
		{
			bigChild = right;
		}
	}

	if (arr[bigChild] > arr[k])
	{
		Common::Swap(arr, k, bigChild);
		Heapify(arr, bigChild, n);
	}
}

 

arr = [ 10, 8, 6, 4, 2, 9, 7, 5, 3, 1 ], n = 10 을 입력하여 실행한 과정은 다음과 같다.

2 4 6 8 10 9 7 5 3 1
1 8 9 5 4 6 7 2 3 10
3 8 7 5 4 6 1 2 9 10
2 5 7 3 4 6 1 8 9 10
1 5 6 3 4 2 7 8 9 10
1 5 2 3 4 6 7 8 9 10
1 4 2 3 5 6 7 8 9 10
1 3 2 4 5 6 7 8 9 10
2 1 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

 

난수 1,000,000개에 대한 수행 시간은 다음과 같다.

total time is 0s ( 112ms )

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

NadanKim/Algorithm

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘