//Perform an Insertion sort on a Vector and time it
//Param:  Vector to sort
//Post:   Returns the number of clock ticks elapsed during sort
clock_t timedInsertionSort(vector<int> &a) {
  clock_t start, end; // For tracking start and end times
  unsigned int s = a.size();

  start = clock();  // Start time
  for(unsigned int i = 1; i < s; i++) { // Start at the second element (if there is one)
    unsigned int j = i;
    while(j > 0 && a[j] < a[j-1]) { // Move backward and push elements as necessary
      swap(a[j], a[j-1]);
      j--;
    }
  }
  end = clock();    // Stop time

  return end - start;
}

template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
class vector : protected _STLP_PRIV _Vector_base<_Tp, _Alloc>
.....
{
....
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
....
  pointer _M_start;
  pointer _M_finish;


....
  iterator begin()             { return this->_M_start; }
  const_iterator begin() const { return this->_M_start; }
  iterator end()               { return this->_M_finish; }
  const_iterator end() const   { return this->_M_finish; }
....
  reference at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
....

  reference operator[](size_type __n) { return *(begin() + __n); }
....

};

// snagged from here: http://linux.wku.edu/~lamonml/algor/sort/insertion.html
// this one is pretty standard and can be found all over the place
void insertionSort(int numbers[], int array_size) {
	int i, j, index;

	for (i=1; i < array_size; i++) {
		index = numbers[i];
		j = i;
		while ((j > 0) && (numbers[j-1] > index)) {
			numbers[j] = numbers[j-1];
			j--;
		}
		numbers[j] = index;
	}
}

QUOTE(chaosTechnician @ 30 May, 2008 - 08:00 AM)

// Benchmark for std::vector....

#include <windows.h>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <vector>
#include <algorithm>

template <typename Iterator>
Iterator rand_partition(Iterator b, Iterator e)
{
    Iterator v = b + (rand() % ( e - b ));
    Iterator oe = e;
    typeof (*v) vv = *v;
    typeof (*v) t;
    *v = *b;
    *b = vv;
    v = b;
    b = b + 1;
    e = e - 1;
    
    for(;;) {
        while(*b < vv) { b++; if(b == oe) break; }
        while(vv < *e) { e--; if(e == v) break; }
        if(b >= e) break;
        t = *b;
        *b = *e;
        *e = t;
        b++; e--;
    }
    
    b--;
    t = *b;
    *b = *v;
    *v = t;
    return b;
}

template <typename Iterator>
void quick_sort(Iterator begin, Iterator end)
{
    if(end - 1 <= begin) return;
    Iterator i = rand_partition(begin, end);
    quick_sort(begin, i);
    quick_sort(i + 1, end);
}


template <typename Iterator, typename Function>
void fill_random(Iterator begin, Iterator end, Function f)
{
    for(Iterator i = begin; i != end; i++)
        *i = f();
}

struct quick_sort_test
{
    template <typename InputIterator>
    void operator()(InputIterator begin, InputIterator end)
    { quick_sort(begin, end); }
};

struct sort_test
{
    template <typename InputIterator>
    void operator()(InputIterator begin, InputIterator end)
    { std::sort(begin, end); }
};

struct stable_sort_test
{
    template <typename InputIterator>
    void operator()(InputIterator begin, InputIterator end)
    { std::stable_sort(begin, end); }
};

template <typename InputIterator>
bool is_sorted(InputIterator i1, InputIterator i2)
{
    if(i2 - i1 <= 1) return true;
    for(InputIterator i = i1; i != i2 - 1; i++)
        if(*i > *(i + 1)) return false;
    return true;
}


template <typename Function> 
void perform_test(int N, Function f, const char* test, std::ostream& os)
{
    using std::setw;
    int* ar = new int[N];
    std::vector<int> ar2(N);
    LARGE_INTEGER start, end, start2, end2, freq;


    fill_random(ar, ar + N, rand);
    std::copy(ar, ar + N, ar2.begin()); 
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&start);
    f(ar, ar + N);
    QueryPerformanceCounter(&end);
    QueryPerformanceCounter(&start2);
    f(ar2.begin(), ar2.end());
    QueryPerformanceCounter(&end2);
    
    os << setw(20) << std::setprecision(2) << std::fixed << std::left << test << std::right << " "
       << setw(10) << N << "  " 
       << setw(10) << 1000.0 * (end.QuadPart - start.QuadPart) / freq.QuadPart << " ms " 
       << setw(10) << 1000.0 * (end2.QuadPart - start2.QuadPart) / freq.QuadPart << " ms    "
       << setw(4) << std::left << (is_sorted(ar, ar + N) ? "Yes" : "No") << " " << std::endl;
    delete [] ar;
}

int main()
{
    using std::setw;
    using std::setfill;
    int N = 10000000;
    SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);

    std::cout 
       << setw(20) << std::left << "Test" << " "
       << setw(10) << "N" << "  " 
       << setw(10) << "int[]" << "    " 
       << setw(10) << "vector<int>" << "      "
       << setw(7) << "Sorted?" << std::endl;
    std::cout 
       << setw(20) << setfill('=') << "" << " "
       << setw(10) << setfill('=') << "" << "  " 
       << setw(13) << setfill('=') << "" << " " 
       << setw(13) << setfill('=') << "" << "    "
       << setw(7)  << setfill('=') << "" << setfill(' ') << std::endl;

    srand(time(0));
    for(int n = 100; n <= N; n *= 10) {
        perform_test(n, sort_test(), "std::sort", std::cout);
        perform_test(n, stable_sort_test(), "std::stable_sort", std::cout);
        perform_test(n, quick_sort_test(), "quick_sort", std::cout); 
    }
    return 0;
}