첨부 실행 코드는 나눔고딕코딩 폰트를 사용합니다.

728x90
반응형
728x170

▶ 힙 정렬하기 예제

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(" ");
}

 

728x90

 

▶ 힙 정렬하기

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
728x90
반응형
그리드형(광고전용)
Posted by icodebroker

댓글을 달아 주세요