Reflecting in action: programming simple algorithms - Marco Dorantes' WebLog - Site Home

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