In preparation to write some papers about software design techniques, I am planning to illustrate those techniques with a variety of examples. As part of the effort I will document my thoughts while doing reflective practicum, identifying and documenting patterns of thought while programming solutions to several kinds of problems; including implementation of simple algorithms like insertion sort, selection sort, bubble sort and more complex ones. By now, let’s see the code so far.Consider the following main function:
#include <iostream> #include <vector> #include <iterator> using namespace std; void main() { sort( sort_by_selection<vector<int> >() ); sort( sort_by_insertion<vector<int> >() ); sort( sort_by_bubble<vector<int> >() ); }
template<typename T> void sort(T sort_algorithm) { int v[]={100,80,70,70,60,50,40,40,20,10,-1,-2}; vector<int> V(v,v+sizeof(v)/sizeof(int)); ostream_iterator<int> out(cout," "); copy(V.begin(),V.end(),out); sort_algorithm(V); cout << endl; copy(V.begin(),V.end(),out); cout << endl; }
template<typename T> class sort_by_selection { public: void operator()(T& v) { T::size_type length=v.size(); if(length<2) return; for(int k=0;k<length;++k) { int min=k; for(int j=k+1;j<length;++j) if(v[j] < v[min]) min=j; T::value_type t=v[k]; v[k]=v[min]; v[min]=t; } } }; template<typename T> class sort_by_insertion { public: void operator()(T& v) { T::size_type length=v.size(); for(int k=1;k<length;++k) { T::value_type key=v[k]; int j=k-1; while(j>=0 && key < v[j]) { v[j+1]=v[j]; --j; } v[j+1]=key; } } }; template<typename T> class sort_by_bubble { public: void operator()(T& v) { T::size_type length=v.size(); for(int k=0; k<length-1; ++k) { for(int j=length-1; j>k; --j) { if( v[j] < v[j-1] ) { T::value_type t=v[j-1]; v[j-1]=v[j]; v[j]=t; } } } } };