남정현의 Windows Azure 블로그

[NonSerialized]
private static int[] LP = 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 // the next number is > 31 bits.
};

private static void Sift(T[] m, int pshift, int head)
    where T : IComparable
{
    T val = m[head];

    while (pshift > 1)
    {
        int rt = head - 1;
        int lf = head - 1 - LP[pshift - 2];

        if (val.CompareTo(m[lf]) >= 0 &&
            val.CompareTo(m[rt]) >= 0)
            break;

        if (m[lf].CompareTo(m[rt]) >= 0)
        {
            m[head] = m[lf];
            head = lf;
            pshift -= 1;
        }
        else
        {
            m[head] = m[rt];
            head = rt;
            pshift -= 2;
        }
    }

    m[head] = val;
}

[CLSCompliant(false)]
private static int NumberOfTrailingZeros(uint x)
{
    int n = 32;
    while (x != 0u)
    {
        n--;
        x += x;
    }
    return n;
}

private static void Trinkle(T[] m, int p, int pshift, int head, bool isTrusty)
    where T : IComparable
{
    T val = m[head];

    while (p != 1)
    {
        int stepson = head - LP[pshift];

        if (m[stepson].CompareTo(val) <= 0)
            break;

        if (!isTrusty && pshift > 1)
        {
            int rt = head - 1;
            int lf = head - 1 - LP[pshift - 2];

            if (m[rt].CompareTo(m[stepson]) >= 0 ||
                m[lf].CompareTo(m[stepson]) >= 0)
                break;
        }

        m[head] = m[stepson];

        head = stepson;
        int trail = NumberOfTrailingZeros((uint)(p & ~1));
        p >>= trail;
        pshift += trail;
        isTrusty = false;
    }

    if (!isTrusty)
    {
        m[head] = val;
        Sift(m, pshift, head);
    }
}

public static TimeSpan SmoothSort(T[] m, int lo, int hi)
    where T : IComparable
{
    DateTime start = DateTime.Now;
    int head = lo;
    int p = 1;
    int pshift = 1;

    while (head < hi)
    {
        if ((p & 3) == 3)
        {
            Sift(m, pshift, head);
            p >>= 2;
            pshift += 2;
        }
        else
        {
            if (LP[pshift - 1] >= hi - head)
                Trinkle(m, p, pshift, head, false);
            else
                Sift(m, pshift, head);

            if (pshift == 1)
            {
                p <<= 1;
                pshift--;
            }
            else
            {
                p <<= (pshift - 1);
                pshift = 1;
            }
        }

        p |= 1;
        head++;
    }

    Trinkle(m, p, pshift, head, false);

    while (pshift != 1 || p != 1)
    {
        if (pshift <= 1)
        {
            int trail = NumberOfTrailingZeros((uint)(p & ~1));
            p >>= trail;
            pshift += trail;
        }
        else
        {
            p <<= 2;
            p ^= 7;
            pshift -= 2;

            Trinkle(m, p >> 1, pshift + 1, head - LP[pshift] - 1, true);
            Trinkle(m, p, pshift, head - 1, true);
        }

        head--;
    }

    return DateTime.Now - start;
}

public static TimeSpan SmoothSort(T[] items)
    where T : IComparable
{
    return SmoothSort(items, 0, items.Length - 1);
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

private static void SiftDown(T[] items, int start, int end)
    where T : IComparable
{
    int root = start;

    while (root * 2 + 1 <= end)
    {
        int child = root * 2 + 1;

        if (child < end && items[child].CompareTo(items[child + 1]) < 0)
            child++;

        if (items[root].CompareTo(items[child]) < 0)
        {
            T temp = items[root];
            items[root] = items[child];
            items[child] = temp;
            root = child;
        }
        else
            return;
    }
}

private static void HeapifyDown(T[] items, int count)
    where T : IComparable
{
    int start = (count - 2) / 2;

    while (start >= 0)
    {
        SiftDown(items, start, count - 1);
        start--;
    }
}

public static TimeSpan HeapSortDown(T[] items, int count)
    where T : IComparable
{
    DateTime start = DateTime.Now;
    HeapifyDown(items, count);
    int end = count - 1;

    while (end > 0)
    {
        T temp = items[end];
        items[end] = items[0];
        items[0] = temp;

        SiftDown(items, 0, end - 1);
        end--;
    }

    return DateTime.Now - start;
}

public static TimeSpan HeapSortDown(T[] items)
    where T : IComparable
{
    return HeapSortDown(items, items.Length);
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

public static TimeSpan ShellSort(T[] items)
    where T : IComparable
{
    DateTime start = DateTime.Now;

    int inc = (int)Math.Round(items.Length / 2d);
    while (inc > 0)
    {
        for (int i = inc; i < items.Length; i++)
        {
            T temp = items[i];
            int j = i;

            while (j >= inc && items[j - inc].CompareTo(temp) > 0)
            {
                items[j] = items[j - inc];
                j -= inc;
            }

            items[j] = temp;
        }

        inc = (int)Math.Round(inc / 2.2d);
    }

    return DateTime.Now - start;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

public static TimeSpan InsertionSort(T[] items)
    where T : IComparable
{
    DateTime start = DateTime.Now;

    for (int i = 1; i < items.Length; i++)
    {
        T value = items[i];
        int j = i - 1;
        bool done = false;

        do
        {
            if (items[j].CompareTo(value) > 0)
            {
                items[j + 1] = items[j];
                j--;

                if (j < 0)
                    done = true;
            }
            else
                done = true;
        }
        while (!done);
        items[j + 1] = value;
    }

    return DateTime.Now - start;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

private static int Partition(T[] items, int left, int right, int pivotIndex)
    where T : IComparable
{
    T pivotValue = items[pivotIndex];

    T temp = items[pivotIndex];
    items[pivotIndex] = items[right];
    items[right] = temp;

    int storeIndex = left;

    for (int i = left; i < right; i++)
    {
        if (items[i].CompareTo(pivotValue) <= 0)
        {
            temp = items[i];
            items[i] = items[storeIndex];
            items[storeIndex] = temp;
            storeIndex++;
        }
    }

    temp = items[storeIndex];
    items[storeIndex] = items[right];
    items[right] = temp;
    return storeIndex;
}

public static TimeSpan QuickSort(T[] items, int left, int right)
    where T : IComparable
{
    DateTime start = DateTime.Now;

    if (right > left)
    {
        int pivotIndex = (left + right) / 2;
        int pivotNewIndex = Partition(items, left, right, pivotIndex);
        QuickSort(items, left, pivotNewIndex - 1);
        QuickSort(items, pivotNewIndex + 1, right);
    }

    return DateTime.Now - start;
}

public static TimeSpan QuickSort(T[] items)
    where T : IComparable
{
    return QuickSort(items, 0, items.Length - 1);
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

public static TimeSpan OddEvenSort(T[] items)
    where T : IComparable
{
    DateTime start = DateTime.Now;
    bool sorted = false;

    while (!sorted)
    {
        sorted = true;

        for (int x = 1; x < items.Length - 1; x += 2)
        {
            if (items[x].CompareTo(items[x + 1]) > 0)
            {
                T temp = items[x];
                items[x] = items[x + 1];
                items[x + 1] = temp;
                sorted = false;
            }
        }

        for (int x = 0; x < items.Length - 1; x += 2)
        {
            if (items[x].CompareTo(items[x + 1]) > 0)
            {
                T temp = items[x];
                items[x] = items[x + 1];
                items[x + 1] = temp;
                sorted = false;
            }
        }
    }

    return DateTime.Now - start;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

public static TimeSpan GnomeSort(T[] items)
    where T : IComparable
{
    DateTime start = DateTime.Now;

    int pos = 0;

    while (pos < items.Length)
    {
        if (pos == 0 || items[pos].CompareTo(items[pos - 1]) >= 0)
            pos++;
        else
        {
            T temp = items[pos];
            items[pos] = items[pos - 1];
            items[pos - 1] = temp;
            pos--;
        }
    }

    return DateTime.Now - start;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

public static TimeSpan CombSort(T[] items)
    where T : IComparable
{
    DateTime start = DateTime.Now;

    int gap = items.Length;
    bool swapped = true;

    while (gap > 1 || swapped)
    {
        if (gap > 1)
            gap = (int)(gap / 1.3d);

        int i = 0;
        swapped = false;

        while (i + gap < items.Length)
        {
            if (items[i].CompareTo(items[i + gap]) > 0)
            {
                T temp = items[i];
                items[i] = items[i + gap];
                items[i + gap] = temp;
                swapped = true;
            }

            i++;
        }
    }

    return DateTime.Now - start;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

public static TimeSpan CocktailSortV2(T[] items)
    where T : IComparable
{
    DateTime start = DateTime.Now;
    bool swapped;
    int begin = (-1);
    int end = items.Length - 1;

    do
    {
        swapped = false;
        begin++;

        for (int i = begin; i < end; i++)
        {
            if (items[i].CompareTo(items[i + 1]) > 0)
            {
                T temp = items[i];
                items[i] = items[i + 1];
                items[i + 1] = temp;
                swapped = true;
            }
        }

        if (!swapped)
            break;

        swapped = false;
        end--;

        for (int i = end; i >= begin; i--)
        {
            if (items[i].CompareTo(items[i + 1]) > 0)
            {
                T temp = items[i];
                items[i] = items[i + 1];
                items[i + 1] = temp;
                swapped = true;
            }
        }
    }
    while (swapped);

    return DateTime.Now - start;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

public static TimeSpan CocktailSortV1(T[] items)
    where T : IComparable
{
    DateTime start = DateTime.Now;
    bool swapped;

    do
    {
        swapped = false;

        for (int i = 0; i < items.Length - 1; i++)
        {
            if (items[i].CompareTo(items[i + 1]) > 0)
            {
                T temp = items[i];
                items[i] = items[i + 1];
                items[i + 1] = temp;
                swapped = true;
            }
        }

        if (!swapped)
            break;

        swapped = false;

        for (int i = 0; i < items.Length - 1; i++)
        {
            if (items[i].CompareTo(items[i + 1]) > 0)
            {
                T temp = items[i];
                items[i] = items[i + 1];
                items[i + 1] = temp;
                swapped = true;
            }
        }
    }
    while (swapped);

    return DateTime.Now - start;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.