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

■ 스무스 정렬하기 예제

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

using System;

 

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

 

SmoothSort<int>(array);

 

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

{

    Console.Write(array[i]);

    Console.Write(" ");

}

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

 

■ 스무스 정렬하기

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

using System;

 

#region Field

 

/// <summary>

/// 논리적 포인트 배열

/// </summary>

[NonSerialized]

private static int[] _logicalPointArray = new int[]

{

    1        , 1        , 3        , 5       , 9       , 15      , 25      , 41      , 67       , 109      ,

    177      , 287      , 465      , 753     , 1219    , 1973    , 3193    , 5167    , 8361     , 13529    ,

    21891    , 35421    , 57313    , 92735   , 150049  , 242785  , 392835  , 635621  , 1028457  , 1664079  ,

    2692537  , 4356617  , 7049155  , 11405773, 18454929, 29860703, 48315633, 78176337, 126491971, 204668309,

    331160281, 535828591, 866988873

};

 

#endregion

 

#region 스무스 정렬하기 - SmoothSort<T>(itemArray, lowIndex, highIndex)

 

/// <summary>/// 스무스 정렬하기

/// </summary>

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

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

/// <param name="lowIndex">하위 인덱스</param>

/// <param name="highIndex">상위 인덱스</param>

public void SmoothSort<T>(T[] itemArray, int lowIndex, int highIndex) where T : IComparable

{

    int headIndex  = lowIndex;

    int index      = 1;

    int shiftIndex = 1;

 

    while(headIndex < highIndex)

    {

        if((index & 3) == 3)

        {

            Sift(itemArray, shiftIndex, headIndex);

 

            index >>= 2;

 

            shiftIndex += 2;

        }

        else

        {

            if(_logicalPointArray[shiftIndex - 1] >= highIndex - headIndex)

            {

                Trinkle(itemArray, index, shiftIndex, headIndex, false);

            }

            else

            {

                Sift(itemArray, shiftIndex, headIndex);

            }

 

            if(shiftIndex == 1)

            {

                index <<= 1;

 

                shiftIndex--;

            }

            else

            {

                index <<= (shiftIndex - 1);

 

                shiftIndex = 1;

            }

        }

 

        index |= 1;

 

        headIndex++;

    }

 

    Trinkle(itemArray, index, shiftIndex, headIndex, false);

 

    while(shiftIndex != 1 || index != 1)

    {

        if(shiftIndex <= 1)

        {

            int trail = GetNumberOfTrailingZeros((uint)(index & ~1));

 

            index >>= trail;

 

            shiftIndex += trail;

        }

        else

        {

            index <<= 2;

 

            index ^= 7;

 

            shiftIndex -= 2;

 

            Trinkle(itemArray, index >> 1, shiftIndex + 1, headIndex - _logicalPointArray[shiftIndex] - 1, true);

 

            Trinkle(itemArray, index, shiftIndex, headIndex - 1, true);

        }

 

        headIndex--;

    }

}

 

#endregion

 

#region 스무스 정렬하기 - SmoothSort<T>(itemArray)

 

/// <summary>

/// 스무스 정렬하기

/// </summary>

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

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

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

{

    SmoothSort(itemArray, 0, itemArray.Length - 1);

}

 

#endregion

 

#region 분류하기 - Sift<T>(itemArray, shiftIndex, headIndex)

 

/// <summary>

/// 분류하기

/// </summary>

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

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

/// <param name="shiftIndex">이동 인덱스</param>

/// <param name="headIndex">헤드 인덱스</param>

private void Sift<T>(T[] itemArray, int shiftIndex, int headIndex) where T : IComparable

{

    T item = itemArray[headIndex];

 

    while(shiftIndex > 1)

    {

        int rootIndex = headIndex - 1;

        int leafIndex = headIndex - 1 - _logicalPointArray[shiftIndex - 2];

 

        if(item.CompareTo(itemArray[leafIndex]) >= 0 && item.CompareTo(itemArray[rootIndex]) >= 0)

        {

            break;

        }

 

        if(itemArray[leafIndex].CompareTo(itemArray[rootIndex]) >= 0)

        {

            itemArray[headIndex] = itemArray[leafIndex];

 

            headIndex = leafIndex;

 

            shiftIndex -= 1;

        }

        else

        {

            itemArray[headIndex] = itemArray[rootIndex];

 

            headIndex = rootIndex;

 

            shiftIndex -= 2;

        }

    }

 

    itemArray[headIndex] = item;

}

 

#endregion

 

#region 후행 0 수 구하기 - GetNumberOfTrailingZeros(value)

 

/// <summary>

/// 후행 0 수 구하기

/// </summary>

/// <param name="value"></param>

/// <returns>후행 0 수</returns>

private int GetNumberOfTrailingZeros(uint value)

{

    int i = 32;

 

    while(value != 0u)

    {

        i--;

 

        value += value;

    }

 

    return i;

}

 

#endregion

 

#region 트링클 - Trinkle<TItem>(itemArray, index, shiftIndex, headIndex, isTrusty)

 

/// <summary>

/// 트링클

/// </summary>

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

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

/// <param name="index">인덱스</param>

/// <param name="shiftIndex">이동 인덱스</param>

/// <param name="headIndex">헤드 인덱스</param>

/// <param name="isTrusty">신뢰 여부</param>

private void Trinkle<T>(T[] itemArray, int index, int shiftIndex, int headIndex, bool isTrusty) where T : IComparable

{

    T item = itemArray[headIndex];

 

    while(index != 1)

    {

        int stepIndex = headIndex - _logicalPointArray[shiftIndex];

 

        if(itemArray[stepIndex].CompareTo(item) <= 0)

        {

            break;

        }

 

        if(!isTrusty && shiftIndex > 1)

        {

            int rootIndex = headIndex - 1;

            int leafIndex = headIndex - 1 - _logicalPointArray[shiftIndex - 2];

 

            if(itemArray[rootIndex].CompareTo(itemArray[stepIndex]) >= 0 ||

                itemArray[leafIndex].CompareTo(itemArray[stepIndex]) >= 0)

            {

                break;

            }

        }

 

        itemArray[headIndex] = itemArray[stepIndex];

 

        headIndex = stepIndex;

 

        int trail = GetNumberOfTrailingZeros((uint)(index & ~1));

 

        index >>= trail;

 

        shiftIndex += trail;

 

        isTrusty = false;

    }

 

    if(!isTrusty)

    {

        itemArray[headIndex] = item;

 

        Sift(itemArray, shiftIndex, headIndex);

    }

}

 

#endregion

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

Posted by 사용자 icodebroker

댓글을 달아 주세요