#include<iostream.h>
#include <stdlib.h>

void dump(char* str,int n, float a[]);
void sort(int l, int r, float a[]);

void straightInsertion(int n, float a[20])
{
	//
	// Leaves the order of items with equal keys unchanged.
	//
	int i,j;
	float x;
	for (i=2;i<=n;i++)
	{
		dump("   Insertion steps:",n, a);
		x=a[i];
		a[0]=x;
		j=i-1;
		while(x<a[j])
		{			
			a[j+1]=a[j]; // Movement
			j--;			
		} // while
		a[j+1]=x;
	} // for
}


// ====================================================
void straightSelection(int n, float a[20])
{
	int i,j,k;
	float x;
	for (i=1;i<n;i++)
	{
		dump("   Selection steps:",n, a);
		k=i;
		x=a[i];
		// Compute the minimum of the rest.
		for(j=i+1;j<=n;j++)
		{
			if(a[j]<x)
			{
				k=j;
				x=a[j];
			}
		} // j
	
		a[k]=a[i];
		a[i]=x;

	} // i
}

// ====================================================
void straightExchange(int n, float a[20])
// bubble sort.
{
	int i,j;
	float x;
	for(i=2;i<=n;i++)
	{
		dump("    Exchange steps:",n, a);
		for(j=n;j>=i;j--)
		{
			if(a[j-1]>a[j])
			{
				// swap
				x=a[j-1];
				a[j-1]=a[j];
				a[j]=x;
			}
		} // j
	} // i

}
// *****************************************************8
void dump(char * str, int n, float a[20])
{
 int i;

 cout << str << " ";
 for(i=0;i<=n;i++)
 {
  cout <<  a[i] << " ";
 }
 cout << endl;
}
// *****************************************************
void quicksort(int n, float a[20])
{
	sort(1,n,a);
}
void sort(int l, int r, float a[20])
{
	// makes partitioning.
	int i,j;
	float x,w;
	i=l;
	j=r;
	x=a[(l+r)/2];

	do
	{
       while(a[i]<x)
	   {
		   i++;
	   }
	   while(x<a[j])
	   {
		   j--;
	   }
        if(i<=j)
		{
			w=a[i];
			a[i]=a[j];
			a[j]=w;;
			i=i+1;
			j=j-1;
		}
    
	} while(i<=j);

	   if(i<j) sort(l,j,a);
	   if(i<r) sort(i,r,a);


} // sort
// *****************************************************8
void shufle(int ind_case, int n, float a[20])
{
	int i;
	unsigned int iseed; // a seed for random number generator.

	switch (ind_case)
	{
		case 1:
		a[0]=999;
		a[1]=21;
		a[2]=5;
		a[3]=37;
		a[4]=2;
		break;
		// ------------------
		case 2:
			a[0]=999;
			a[1]=44;
			a[2]=55;
			a[3]=12;
			a[4]=42;
//
			a[5]=94;
			a[6]=18;
			a[7]=06;
			a[8]=67;
			break;
			// ------------------
		case 3:
    	iseed=1;
	    srand(iseed); // set the iseed for the random number generator.
        a[0]=999; //doesn't participate in the sorting.
		for(i=1;i<=n;i++)
		{
			a[i]=(float)rand()/(float)RAND_MAX; 
			// rand() generates a pseudo-random 
			// in the interval (0,RAND_MAX)
		}
		break;
// ------------------------------------------------------
		case 4:
			a[0]=999;
			a[1]=7;
			a[2]=3;
			a[3]=5;
			a[4]=12;
//
			a[5]=6;
			a[6]=9;
			a[7]=8;
			a[8]=4;
			break;
			// ------------------
	}
}
// ******************************************************
void binaryInsertion(int n, float a[20])
{
	//
	// Straight insertion using a Binary search.
	//
	int  i,j,l,r,m;
	float x;
	for(i=2;i<=n;i++)
	{
		x=a[i];
		l=1;
		r=i-1;
		while (l<=r)
		{
			m=(l+r)/2;
			if(x<a[m])
			{
				r=m-1;				
			}
			else
			{
				l=m+1;
			}
		} // while
		//
		for(j=i-1;j>=l;j--)
		{
			a[j+1]=a[j];
		} // for j
		//
		a[l]=x;
	} // for i
}
// ******************************************************
void shakesort(int n, float a[20])
{
	int j,k,l,r;
	float x;
	
	l=2;
	r=n;
	k=n;
	do
	{
		for(j=r;j>=l;j--)
		{
			if(a[j-1]>a[j])
			{
				x=a[j-1];
				a[j-1]=a[j];
				a[j]=x;
				k=j;
			}
        }
		l=k+1;
		//
		//
		for(j=l;j<=r;j++)
		{
			if(a[j-1]>a[j])
			{
			 x=a[j-1];
			 a[j-1]=a[j];
			 a[j]=x;
			 k=j;
			}
		}
		r=k-1;
	} while(l<=r);
}


// ====================================================