//This program implements the well known Insertion Sort Algorithm 
//Note.  The code was debugged by simulating it using playing cards
//       with toothpicks for iterators.
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;

void showIt( vector<int>::iterator begin, vector<int>::iterator end,
	vector<int>::iterator i0,
	string si)
{
	vector <int>:: iterator i;
        for( i=begin; i!=end; i++ )
        {
                if(i == i0)
                        cout << si;
                cout << "\t";
        }
        cout << endl;
}


void print( vector<int>::iterator begin, vector<int>::iterator end,
	vector<int>::iterator sorted, vector<int>::iterator next,
	vector<int>::iterator i0)
{
	vector <int>:: iterator i;
	for( i=begin; i!=end; i++ )
		cout << *i << "\t";
	cout << endl;
	showIt(begin, end, sorted, "sorted");
	showIt(begin, end, next, "next");
	showIt(begin, end, i0, "i");
}//print

void sort( vector<int>::iterator begin, vector<int>::iterator end)
{

        vector<int>::iterator sorted;//lowest sorted item
    
        for (sorted = end-1; sorted != begin; sorted--)
	{
            vector<int>::iterator next = sorted-1;//put in place
	    int value = *next;
	    vector<int>::iterator i;
            for (i = sorted; i != end; i++)
	    {
                if (value <= *i)
			break;
		*next = *i;
		next++;
		print(begin, end, sorted, next, i);
	    }
	    *next=value;
	    print(begin, end, sorted, next, i);

        }//for next

}

int main()
{
   const int seed = static_cast<int>(time(0));
   srand(seed);//set random number differently each run

   const int Biggest = 100;
   const int Size = 6;
   const int Sample = 1;

   for(int s = 0; s<Sample; s++)
   { 
      vector <int> data;
      for(int i = 0; i< Size; i++)
      {
	   data.push_back(rand()%Biggest);
      }

      sort(data.begin(), data.end());

/* Debugging
      for(vector<int>::iterator p=data.begin(); p!=data.end(); p++)
      {
		cout << *p << "\t";
      }
      cout << "\n----------\n";
*/
   }

   return 0;
}