Yurttas/PL/OOL/Cplusplus/F/05/04/03/01/insertionsort.cpp

 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}