/*
 * =====================================================================================
 *
 *       Filename:  test.cpp
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  2016年03月31日 10时24分41秒
 *  Last Modified:  2016年03月31日 10时24分41秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  zt (),
 *   Organization:
 *
 * =====================================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <iostream>
#include <algorithm>


template<typename T>
void insertionSort ( T a[], int n )
{
  for ( int i = 1; i < n; i++ )
  {
    T t = a[i];
    int j;

    for ( j = i - 1; j >= 0 && t < a[j]; --j )
      a[j + 1] = a[j];

    a[j + 1] = t;
  }
}

int compare ( const void* a , const void* b )
{
  return ( * ( int* ) a - * ( int* ) b );
}


int main ( int argc, char* argv[] )
{
  int a[10000] = { 0 };
  int step = 10;

  double clocksPerMillis = double ( CLOCKS_PER_SEC ) / 1000;

  std::cout << "...." << std::endl;

  for ( int n = 9000; n <= 9100; n += step )
  {
    for ( int i = 0; i < n; ++i )
      a[i] = n - i;

    clock_t startTime = clock();
    //insertionSort ( a, n );
    std::qsort ( a, n, 4 , compare );
    //std::sort ( a, a + n );

    double elapsedMillis = ( clock() - startTime ) / clocksPerMillis;

    std::cout << n << '\t' << elapsedMillis << std::endl;

    if ( n == 100 )
      step = 100;
  }


  return 0;
}