Различные алгоритмы сортировки

В этом небольшом посте, я выкладываю тривиальные реализации различных методов сортировки массивов с разными типами данных. Все предложенные способы сортируют массивы по возрастанию (хотя, очень легко сделать так, чтобы весь код стал универсальным: допустим, можно слегка модифицировать листинги таким образом, чтобы каждая из функций сортировки принимала на вход еще и операцию, с помощью которой будет выполнено упорядочивание).

Итак, код на D:

import std.stdio;

void exch(T)(ref T x, ref T y)
{
    T tmp = x;
    x = y;
    y = tmp;
}

T[] selectionSort(T)(T[] x)
{
    T[] res = x.dup;
    for (size_t i = 0; i < res.length - 1; i++)
    {
        size_t min = i;
        for (size_t j = i + 1; j < res.length; j++)
        {
            if (res[j] < res[min]) min = j;
        }
        exch(res[i],res[min]);
    }
    return res;
}

T[] bubbleSort(T)(T[] x)
{
    T[] res = x.dup;
    for (size_t i = 0; i < res.length; i++)
    {
        for (size_t j = 0; j < res.length - i - 1; j++)         {             if (res[j] > res[j+1]) exch(res[j],res[j+1]);
        }
    }
    return res;
}

T[] shellSort(T)(T[] x)
{
    T[] res = x.dup;
    size_t d = x.length;
    for (size_t i = d/2; i > 0; i /= 2)
    {
        for (size_t j = i; j < d; j++)         {             for (size_t k = j; k >= i && res[k-i] > res[k]; k -= i)
            {
                exch(res[k],res[k-i]);
            }
        }
    }
    return res;
}

T[] gnomeSort(T)(T[] x)
{
    T[] res = x.dup;
    size_t i = 0;
    while (i < res.length)
    {
        if (i == 0 || res[i-1] <= res[i]) i++;
        else
        {
            exch(res[i],res[i-1]);
            i--;
        }
    }
    return res;
}

T[] insertionSort(T)(T[] x)
{
    T[] res = x.dup;
    for (size_t i = 0; i < res.length; i++)
    {
        for (size_t j = i; j && res[j] < res[j-1]; j--)
        {
            exch(res[j],res[j-1]);
        }
    }
    return res;
}

T[] shakerSort(T)(T[] x)
{
    T[] res = x.dup;
    size_t beg,end;
    for (size_t i = 0; i < res.length/2; i++)     {         beg = 0;         end = res.length - 1;         do         {             if (res[beg] > res[beg+1]) exch(res[beg],res[beg+1]);
            beg++;
            if (res[end-1] > res[end]) exch(res[end-1],res[end]);
            end--;
        }
        while (beg <= end);     }     return res; } T[] combSort(T)(T[] x) {     T[] res = x.dup;     size_t size = res.length;     if (res && size)     {         size_t jump = size;         bool swapped = true;         while (jump > 1 || swapped)
        {
            if (jump > 1) jump /= 1.24733;
            swapped = false;
            for (size_t i = 0; i + jump < size; i++)
            {
                if (res[i+jump] < res[i])
                {
                    exch(res[i+jump],res[i]);
                    swapped = true;
                }
            }
        }
    }
    return res;
}

T[] oddEvenSort(T)(T[] x)
{
    T[] res = x.dup;
    bool sorted = false;

    template cycle(string num)
    {
        const char[] cycle = "for (int i = " ~ num ~ " ; i < res.length - 1; i += 2) {         if (res[i] > res[i+1]) {
        exch(res[i],res[i+1]);
        sorted = false;
    }
    }";
    }

    while (!sorted)
    {
        sorted = true;
        mixin(cycle!"1");
        mixin(cycle!"0");
    }

    return res;
}

T[] stoogeSort(T)(ref T[] x,size_t i, size_t j)
{
    // first call: stoogeSort(x,0,x.length - 1)
    if (x[j] < x[i]) exch(x[j],x[i]);     if (j - i > 1)
    {
        size_t t = (j - i + 1) / 3;
        stoogeSort(x, i  , j-t);
        stoogeSort(x, i+t, j  );
        stoogeSort(x, i  , j-t);
    }
    return x;
}

T[] quickSort(T)(T[] x)
{

    uint partition(T)(T[] x)
    {
        if (x.length < 2) return 0;
        auto pivot = x[$-1];
        uint i = -1, j = x.length-1;
        while(i < j || i == -1)
        {
            i++;
            while(x[i] < pivot) i++;
            j--;
            while(i < j && x[j] > pivot) j--;

            if(i < j && j < x.length) exch(x[i], x[j]);         }         exch(x[i], x[$-1]);         return i;     }     if (x.length > 1)
    {
        exch(x[$/2], x[$-1]);
        auto p = partition(x);
        quickSort(x[0 .. p]);
        quickSort(x[p + 1 .. $]);
    }
    return x;
}

Процедура exch – вспомогательная и служит для того, чтобы поменять значения некоторых двух переменных местами.

P.S: Код, конечно, не идеальный, но все-таки он написан мной. Кроме того, возможно, я выложу более универсальную версию данных алгоритмов.