//======================================================================
// Double-Burst-Selectionsort
//======================================================================
template<typename ItemType>
void DoubleBurstSelectionSort(ItemType* array, unsigned size)
{
    for(unsigned minIndex = 0, maxIndex = size-1; minIndex < maxIndex;)
    {
        ItemType min = array[minIndex];
        ItemType max = array[maxIndex];
        unsigned newMinIndex = minIndex+1;
        unsigned newMaxIndex = maxIndex;

        for(unsigned index = newMinIndex; index <= newMaxIndex;)
        {
            ItemType value = array[index];

            if(value <= min)
            {
                if(value < min)
                {
                    min = value;
                    newMinIndex = minIndex;
                    array[index] = array[newMinIndex];
                }
                else
                {
                    array[index] = array[newMinIndex];
                    ++index;
                }
                array[newMinIndex] = value;
                ++newMinIndex;
            }
            else if(value >= max)
            {
                if(value > max)
                {
                    max = value;
                    newMaxIndex = maxIndex;
                }
                array[index] = array[newMaxIndex];
                array[newMaxIndex] = value;
                --newMaxIndex;
            }
            else ++index;
        }
        minIndex = newMinIndex;
        maxIndex = newMaxIndex;
    }
}

//======================================================================
// Insertion sort
//======================================================================
template<typename ItemType>
void InsertionSort(ItemType* array, unsigned size)
{
    for(unsigned i = 1; i < size; ++i)
    {
        ItemType val = array[i];
        unsigned j = i;
        while(j > 0 && array[j-1] > val)
        {
            array[j] = array[j-1];
            --j;
        }
        array[j] = val;
    }
}

//======================================================================
// Quicksort
//======================================================================
template<typename ItemType>
unsigned Partition(ItemType* array, unsigned f, unsigned l, ItemType pivot)
{
    unsigned i = f-1, j = l+1;
    while(true)
    {
        while(array[--j] > pivot);
        while(array[++i] < pivot);
        if(i<j)
        {
            ItemType tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
        else
            return j;
    }
}

#include <algorithm>

template<typename ItemType>
void QuickSortIteration(ItemType* array, unsigned f, unsigned l)
{
    while(f < l)
    {
        ItemType v1 = array[f], v2 = array[l], v3 = array[(f+l)/2];
        ItemType median =
            v1 < v2 ?
            ( v3 <= v1 ? v1 : std::min(v2, v3) ) :
            ( v3 <= v2 ? v2 : std::min(v1, v3) );
        unsigned m = Partition(array, f, l, median);
        QuickSortIteration(array, f, m);
        f = m+1;
    }
}

template<typename ItemType>
void QuickSort(ItemType* array, unsigned size)
{
    QuickSortIteration(array, 0, size-1);
}

template<typename ItemType>
void QuickSortWithInsertionSortIteration(ItemType* array,
                                         unsigned f, unsigned l)
{
    while(f+15 < l)
    {
        ItemType v1 = array[f], v2 = array[l], v3 = array[(f+l)/2];
        ItemType median =
            v1 < v2 ?
            ( v3 <= v1 ? v1 : std::min(v2, v3) ) :
            ( v3 <= v2 ? v2 : std::min(v1, v3) );
        unsigned m = Partition(array, f, l, median);
        QuickSortWithInsertionSortIteration(array, f, m);
        f = m+1;
    }
}

template<typename ItemType>
void QuickSortWithInsertionSort(ItemType* array, unsigned size)
{
    QuickSortWithInsertionSortIteration(array, 0, size-1);
    InsertionSort(array, size);
}

template<typename ItemType>
void QuickSortWithDBSelectionSortIteration(ItemType* array,
                                        unsigned f, unsigned l)
{
    while(f+30 < l)
    {
        ItemType v1 = array[f], v2 = array[l], v3 = array[(f+l)/2];
        ItemType median =
            v1 < v2 ?
            ( v3 <= v1 ? v1 : std::min(v2, v3) ) :
            ( v3 <= v2 ? v2 : std::min(v1, v3) );
        unsigned m = Partition(array, f, l, median);
        QuickSortWithDBSelectionSortIteration(array, f, m);
        f = m+1;
    }
    DoubleBurstSelectionSort(array+f, l-f+1);
}

template<typename ItemType>
void QuickSortWithDBSelectionSort(ItemType* array, unsigned size)
{
    QuickSortWithDBSelectionSortIteration(array, 0, size-1);
}



//======================================================================
// Test code
//======================================================================
#include <cstdio>
#include <cstdlib>
#include <ctime>

namespace
{
    const unsigned MaxArraySize = 10000;
    const unsigned MaxArray2Size = 100000;
    const int Seconds = 10;

    unsigned originalArray[MaxArray2Size];
    unsigned arrayToBeSorted[MaxArray2Size];

    void initializeOriginalArray(unsigned arraySize,
                                 unsigned itemMaxValue)
    {
        for(unsigned i = 0; i < arraySize; ++i)
        {
            originalArray[i] = unsigned(drand48()*itemMaxValue+.5);
        }
    }
}

template<typename SortFunction>
void checkSort(SortFunction f, const char* name)
{
    std::fprintf(stderr, "Checking integrity of %s.\n", name);

    for(unsigned i = 1; i <= MaxArraySize; i*=2)
    {
        initializeOriginalArray(MaxArraySize, MaxArraySize/i);
        std::copy(originalArray, originalArray+MaxArraySize, arrayToBeSorted);
        f(arrayToBeSorted, MaxArraySize);
        std::sort(originalArray, originalArray+MaxArraySize);
        for(unsigned i = 0; i < MaxArraySize; ++i)
        {
            if(originalArray[i] != arrayToBeSorted[i])
            {
                std::fprintf(stderr, "Oops! %s failed!\n", name);
                std::exit(1);
            }
        }
    }
}

void sanityCheck()
{
    checkSort(DoubleBurstSelectionSort<unsigned>, "DBSSort");
    checkSort(InsertionSort<unsigned>, "Insertion sort");
    checkSort(QuickSort<unsigned>, "QuickSort");
    checkSort(QuickSortWithInsertionSort<unsigned>, "QuickSort(insertion)");
    checkSort(QuickSortWithDBSelectionSort<unsigned>, "QuickSort(DBSS)");
}

template<typename SortFunction>
unsigned testSort(SortFunction f, unsigned arraySize)
{
    std::clock_t startTime = std::clock();
    unsigned times = 0;
    do
    {
        std::copy(originalArray, originalArray+arraySize,
                  arrayToBeSorted);
        f(arrayToBeSorted, arraySize);
        ++times;
    }
    while((std::clock() - startTime)/CLOCKS_PER_SEC < Seconds);

    return times;
}

//#define PRINT_HTML

void CompareInsertionAndDBSS()
{
#ifdef PRINT_HTML
    std::printf("<table border=1>\n");
    std::printf
        ("<tr><th>Max value</th><th>Array size</th><th>Insertion</th>"
         "<th>D-B-Selection</th></tr>\n");
#else
    std::printf("Insertion sort vs. Double-Burst-Selectionsort (%u seconds)\n",
                Seconds);
    std::printf("=======================================================\n");
    std::printf(" Max value | Array size | Insertion | D-B-Selection\n");
    std::printf("-----------|------------|-----------|--------------\n");
#endif

    for(unsigned maxVal = 10; maxVal <= MaxArraySize*10; maxVal *= 10)
    {
        initializeOriginalArray(MaxArraySize, maxVal);

        for(unsigned arraySize = 10;
            arraySize <= MaxArraySize; arraySize *= 10)
        {
            unsigned isTimes = testSort(InsertionSort<unsigned>, arraySize);
            unsigned dbssTimes =
                testSort(DoubleBurstSelectionSort<unsigned>, arraySize);

#ifdef PRINT_HTML
            std::printf("<tr><td align=right>%u</td>"
                        "<td align=right>%u</td>"
                        "<td align=right>%u</td>"
                        "<td align=right>%u</td></tr>\n",
                        maxVal, arraySize, isTimes, dbssTimes);
#else
            std::printf("%10u |%11u |%10u |%10u\n",
                        maxVal, arraySize, isTimes, dbssTimes);
#endif
        }
    }

#ifdef PRINT_HTML
    std::printf("</table>\n");
#else
    std::printf("\n");
#endif
}

void CompareQuickSorts()
{
#ifdef PRINT_HTML
    std::printf("<table border=1>\n");
    std::printf
        ("<tr><th>Max value</th><th>Quicksort</th><th>QS + Insertion</th>"
         "<th>QS + D-B-Selection</th></tr>\n");
#else
    std::printf("Quicksort with insertion vs dbss (%u seconds)\n", Seconds);
    std::printf("=============================================\n");
    std::printf(" Max value | Quicksort | Insertion | D-B-Selection\n");
    std::printf("-----------|-----------|-----------|--------------\n");
#endif

    for(unsigned maxVal = 10; maxVal <= MaxArray2Size*10; maxVal *= 10)
    {
        initializeOriginalArray(MaxArray2Size, maxVal);

        unsigned qsTimes = testSort(QuickSort<unsigned>, MaxArray2Size);
        unsigned isTimes = testSort(QuickSortWithInsertionSort<unsigned>,
                                    MaxArray2Size);
        unsigned dbssTimes = testSort(QuickSortWithDBSelectionSort<unsigned>,
                                      MaxArray2Size);

#ifdef PRINT_HTML
            std::printf("<tr><td align=right>%u</td>"
                        "<td align=right>%u</td>"
                        "<td align=right>%u</td>"
                        "<td align=right>%u</td></tr>\n",
                        maxVal, qsTimes, isTimes, dbssTimes);
#else
            std::printf("%10u |%10u |%10u |%10u\n",
                        maxVal, qsTimes, isTimes, dbssTimes);
#endif
    }

#ifdef PRINT_HTML
    std::printf("</table>\n");
#else
    std::printf("\n");
#endif
}

int main()
{
    sanityCheck();
    CompareInsertionAndDBSS();
    CompareQuickSorts();

    return 0;
}