Reflecting in action: programming simple algorithms


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> >() );
}



That sort function looks like:
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;
}



The rest:
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;
}
}
}
}
};


Comments (1)

  1. As part of the same preparation I really enjoyed to program a classic:

    Which are the 92 solutions…