1/*
2 Copyright(C) 2002
3 All Rights Reserved. Salih Yurttas, ZCubes, BitsOfCode Software Systems, Inc..
4
5 Permission to use, copy, modify, and distribute this
6 software and its documentation for EDUCATIONAL purposes
7 and without fee is hereby granted provided that this
8 copyright notice appears in all copies.
9
10 date : January 1, 2002.
11 author : Salih Yurttas.
12
13 insertionsort.cpp
14*/
15
16
17#include <vector>
18
19using namespace std;
20
21template<class T, class C>
22void insertionsort(vector<T>& list,
23 const C& compare) {
24 int n = list.size();
25
26 for(int i=n; i>0; i--)
27 list[i]=list[i-1];
28
29 for(int i=1; i<=n; i++) {
30 T key=list[i];
31 list[0]=key;
32 int j=i-1;
33 while(compare(key,list[j])) {
34 list[j+1]=list[j];
35 --j;
36 }
37 list[j+1]=key;
38 }
39
40 for(int i=0; i<n; i++)
41 list[i]=list[i+1];
42}