/*******************************************************************************
 * Code purpose: performance comparsion std::sort vs std::sort_heap;
 * Author: Copyright(c) 2013, Taras Sich
*******************************************************************************/
 
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
 
typedef void (*func_sort)(vector<int>::iterator first, vector<int>::iterator last);
 
inline void make_sorted_vector(vector<int> & elements, unsigned int uiCount)
{
    for(unsigned int i = 0; i < uiCount; ++i)
    {
        elements.push_back(i);
    }    
}
 
inline void make_heap_sort(vector<int>::iterator first, vector<int>::iterator last)
{
    make_heap(first, last);
    sort_heap(first, last);
}
 
void TestSortFunction(func_sort sortFunction, unsigned int uiElementsCount)
{
    /* Test on sorted range */
    {
        vector<int> elements;
        make_sorted_vector(elements, uiElementsCount);
 
        clock_t start = clock();    
        sortFunction(elements.begin(), elements.end());
        clock_t end = clock();
 
        double consumed_time = (double)(end - start) / (double)CLOCKS_PER_SEC;
        printf("Consumed time for sorted range: %lf sec.\n", consumed_time);
    }
 
    /* Test on reverse sorted range */
    {
        vector<int> elements;
        make_sorted_vector(elements, uiElementsCount);
        reverse(elements.begin(), elements.end());
        clock_t start = clock();    
        sortFunction(elements.begin(), elements.end());
        clock_t end = clock();
 
        double consumed_time = (double)(end - start) / (double)CLOCKS_PER_SEC;
        printf("Consumed time for reversed range: %lf sec.\n", consumed_time);
    }
 
    /* Test on random  range */
    {
        vector<int> elements;
        make_sorted_vector(elements, uiElementsCount);
        random_shuffle(elements.begin(), elements.end());
        clock_t start = clock();    
        sortFunction(elements.begin(), elements.end());
        clock_t end = clock();
 
        double consumed_time = (double)(end - start) / (double)CLOCKS_PER_SEC;
        printf("Consumed time for random range: %lf sec.\n", consumed_time);
    }   
}
 
int main()
{
    unsigned int uiTestCount = 10000000;
    printf("==== Comparing std::sort vs std::sort_heap performance. ===\n");
    printf("==== Range types: sorted, reversed, random\t\t===\n");
    printf("==== Range size is %u.\t\t\t\t===\n\n", 
        uiTestCount);
 
    printf("==== std::sort results:\n");
    TestSortFunction(sort, uiTestCount);
    printf("\n");
    printf("==== std::make_heap+std::sort_heap results:\n");
    TestSortFunction(make_heap_sort, uiTestCount);
}