첨부 실행 코드는 나눔고딕코딩 폰트를 사용합니다.
유용한 소스 코드가 있으면 icodebroker@naver.com으로 보내주시면 감사합니다.
블로그 자료는 자유롭게 사용하세요.

■ 힙 정렬하기 예제

----------------------------------------------------------------------------------------------------

using System;

 

int[] array = new int[] { 10, 50, 30, 20, 90, 80, 15, 20 };

 

HeapSort<int>(array);

 

for(int i = 0; i < array.Length; i++)

{

    Console.Write(array[i]);

    Console.Write(" ");

}

----------------------------------------------------------------------------------------------------

 

■ 힙 정렬하기

----------------------------------------------------------------------------------------------------

using System;

 

#region 힙 정렬하기 - HeapSort<TItem>(itemArray, count)

 

/// <summary>

/// 힙 정렬하기

/// </summary>

/// <typeparam name="T">항목 타입</typeparam>

/// <param name="itemArray">항목 배열</param>

/// <param name="count">횟수</param>

public void HeapSort<T>(T[] itemArray, int count) where T : IComparable

{

    HeapDown(itemArray, count);

 

    int endIndex = count - 1;

 

    while(endIndex > 0)

    {

        T temporaryItem = itemArray[endIndex];

 

        itemArray[endIndex] = itemArray[0];

        itemArray[0       ] = temporaryItem;

 

        SiftDown(itemArray, 0, endIndex - 1);

 

        endIndex--;

    }

}

 

#endregion

 

#region 힙 정렬하기 - HeapSort<T>(itemArray)

 

/// <summary>

/// 힙 정렬하기

/// </summary>

/// <typeparam name="T">항목 타입</typeparam>

/// <param name="itemArray">항목 배열</param>

public void HeapSort<T>(T[] itemArray) where T : IComparable

{

    HeapSort(itemArray, itemArray.Length);

}

 

#endregion

 

#region 아래로 이동하기 - SiftDown<T>(itemArray, startIndex, endIndex)

 

/// <summary>

/// 아래로 이동하기

/// </summary>

/// <typeparam name="T">항목 타입</typeparam>

/// <param name="itemArray">항목 배열</param>

/// <param name="startIndex">시작 인덱스</param>

/// <param name="endIndex">종료 인덱스</param>

private void SiftDown<T>(T[] itemArray, int startIndex, int endIndex) where T : IComparable

{

    int rootIndex = startIndex;

 

    while(rootIndex * 2 + 1 <= endIndex)

    {

        int childIndex = rootIndex * 2 + 1;

 

        if(childIndex < endIndex && itemArray[childIndex].CompareTo(itemArray[childIndex + 1]) < 0)

        {

            childIndex++;

        }

 

        if(itemArray[rootIndex].CompareTo(itemArray[childIndex]) < 0)

        {

            T temporaryItem = itemArray[rootIndex];

 

            itemArray[rootIndex ] = itemArray[childIndex];

            itemArray[childIndex] = temporaryItem;

 

            rootIndex = childIndex;

        }

        else

        {

            return;

        }

    }

}

 

#endregion

 

#region 아래로 쌓기 - HeapDown<T>(itemArray, count)

 

/// <summary>

/// 아래로 쌓기

/// </summary>

/// <typeparam name="T">항목 타입</typeparam>

/// <param name="itemArray">항목 배열</param>

/// <param name="count">횟수</param>

private void HeapDown<T>(T[] itemArray, int count) where T : IComparable

{

    int startIndex = (count - 2) / 2;

 

    while(startIndex >= 0)

    {

        SiftDown(itemArray, startIndex, count - 1);

 

        startIndex--;

    }

}

 

#endregion

----------------------------------------------------------------------------------------------------

Posted by 사용자 icodebroker
TAG

댓글을 달아 주세요