#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip.h>
#include <conio.h>


#define MAX 10000

class Sort
{
	int A[MAX];

	public:
		void Init();
		void Menu();
      void Delay(int);
	   void Loading();
		void InsertionSort();
		void ShellSort();
		void SortInterval(int,int);
		int Min(int);
		void SelectionSort();
		void BubbleSort();
		void Merge(int,int,int);
		void MergeSort(int,int);
		void Swap(int,int);
		int Partition(int,int);
		void QuickSort(int,int);
		void HeapSort(int);
		void ReheapUp(int);
		void ReheapDown(int,int);
		double ET(clock_t,clock_t);
};


void Sort::Init()
{
	int j=MAX-1;

	for (int i=0;i<MAX;i++)
	{
		A[i]=((2*j)+3)/7;
		j--;
	}
}

void Sort::Delay(int sec)
{
   int sum=0;
   time_t first, second;

   first = time(NULL);  /* Gets system
                           time */
   while(sum != sec)
   {
   	second = time(NULL); /* Gets system time again */
   	sum = second-first;
   }
}

void Sort::Loading()
{
   textattr(27);
   clrscr();
   gotoxy(28,12);
	cprintf("LOADING            ");

   for(int i=0; i<10; i++)
   {

      if(i==0)
		{
         for(int j=0;j<10;j++)
      	{
         	gotoxy(36,11);
   			cout<<(j+1)<<"%";
	      }
      }

      if(i==1)
		{
         for(int j=10;j<20;j++)
      	{
	      	gotoxy(36,11);
   			cout<<(j+1)<<"%";
	      }
   	}

      if(i==2)
		{
         for(int j=20;j<30;j++)
      	{
	      	gotoxy(36,11);
   			cout<<(j+1)<<"%";
	      }
   	}

      if(i==3)
		{
      	for(int j=30;j<40;j++)
      	{
	      	gotoxy(36,11);
   			cout<<(j+1)<<"%";
   	   }
      }

      if(i==4)
		{
         for(int j=40;j<50;j++)
      	{
	      	gotoxy(36,11);
   			cout<<(j+1)<<"%";
	      }
		}

      if(i==5)
		{
      	for(int j=50;j<60;j++)
      	{
      		gotoxy(36,11);
   			cout<<(j+1)<<"%";
	      }
   	}

      if(i==6)
		{
         for(int j=60;j<70;j++)
      	{
   	   	gotoxy(36,11);
	   		cout<<(j+1)<<"%";
	      }
   	}

      if(i==7)
		{
         for(int j=70;j<80;j++)
      	{
	      	gotoxy(36,11);
   			cout<<(j+1)<<"%";
      	}
		}

      if(i==8)
		{
         for(int j=80;j<90;j++)
      	{
	      	gotoxy(36,11);
   			cout<<(j+1)<<"%";
	      }
   	}

      if(i==9)
		{
         for(int j=90;j<100;j++)
      	{
	      	gotoxy(36,11);
   			cout<<(j+1)<<"%";
	      }
   	}

   	gotoxy(37+(i),12);
      cprintf("±");
      Delay(1);

   }


}




void Sort::Menu()
{
	char X[128],Y[128];
	_strtime(X);
	_strdate(Y);

   textattr(44);
   clrscr();
   gotoxy(29,1);
	cprintf("Welcome to SOFTWORLD!\n\r");
	cout<<"###########################################################################\n\r"
	      "#Program Name:		 SORTING-AL.exe.                                  #\n\r"
	      "#Objective:		 Showing differences among various                #\n\r"
	      "#			 sorting algorithms.                              #\n\r"
	      "#Date established:	 22 MARCH 2002.                                   #\n\r"
	      "#P/s:			 Copyrights 1999-2002. Ponomono Group.            #\n\r"
	      "#			 All Rights Reserved.				  #\n\r"
	      "###########################################################################\n\n\r";

   textcolor(15);
	cprintf("10000 elements are to be sorted on next.\n\n\r");
	cprintf("Current time is: ");
   cout<<X<<endl;
	cprintf("Current date is: ");
   cout<<Y<<endl;
	cout<<endl;
	system("pause");
}

void Sort::InsertionSort()
{
	int current,j;
	for (int i=1;i<MAX;i++)
	{
		current= A[i];
		j=i;
		while ((j>0)&&(current<A[j-1]))
		{
			A[j]= A[j-1];
			j--;
			A[j]= current;
		}
	}
}

void Sort::SortInterval(int start,int increment)
{
	int i,j,current;
	i=start+increment;
	while (i<MAX)
	{
		current=A[i];
		j=i;
		while ((j>start) && (current<A[j-increment]))
		{
			A[j]=A[j-increment];
			j=j-increment;
			A[j]= current;
		}
		i=i+increment;
	}
}

void Sort::ShellSort()
{
	int increment,start;
	increment=MAX;
	do
	{
		increment=increment/3+1;
		for (start=0;start<increment;start++)
			SortInterval(start,increment);

	}while (increment>1);
}

int Sort::Min(int pos)
{
	int i,m,index=pos;
	m=A[pos];
	for (i=pos+1;i<MAX;i++)
	{
		if(A[i]<m)
		{
			m=A[i];
			index=i;
		}
	}
	return index;
}

void Sort::SelectionSort()
{
	int i,temp,k;
	for (i=0;i<MAX;i++)
	{
		k=Min(i);
		if (A[k]<A[i])
		{
			temp=A[k];
			A[k]=A[i];
			A[i]=temp;
		}
	}
}

void Sort::BubbleSort()
{
	int i,j,temp,sorted=0;
	i=0;
	while((i<MAX)&&(sorted==0))
	{
		sorted=1;
		for (j=0;j<MAX-i-1;j++)
		{
			if (A[j]>A[j+1])
			{
				temp=A[j];
				A[j]=A[j+1];
				A[j+1]=temp;
				sorted=0;
			}
		}
		i++;
	}
}

void Sort::Merge(int lpos, int rpos, int rend)
{
	int i, lend, numelements, tmppos,TmpArray[MAX];
	lend=rpos - 1;
	tmppos=lpos;
	numelements=rend-lpos+1;

	while ((lpos<=lend)&&(rpos<=rend))
		if ( A[lpos] <= A[rpos])
			TmpArray[tmppos++] = A[lpos++];
		else
			TmpArray[tmppos++] = A[rpos++];

	while (lpos <= lend)
		TmpArray[tmppos++] = A[lpos++];

	while (rpos <= rend)
		TmpArray[tmppos++] = A[rpos++];

	for (i = 0; i < numelements; i++, rend--)
		A[rend] = TmpArray[rend];
}

void Sort::MergeSort(int left, int right)
{
	int center;

	if (left < right)
	{
		center=(left+right)/2;
		MergeSort(left,center);
		MergeSort(center+1,right);
		Merge(left,center+1,right);
	}
}

void Sort::Swap(int x, int y)
{
	int temp;
	temp=A[x];
	A[x]=A[y];
	A[y]=temp;
}

int Sort::Partition (int left, int right)
{
	int pivot;
	int i,pivotpos;
	Swap(left,(left+right)/2);
	pivot=A[left];
	pivotpos=left;
	for(i=left+1;i<=right;i++)
		if (A[i]<pivot)
			Swap(++pivotpos,i); //move large entry to right and small to left
	Swap(left,pivotpos);
	return pivotpos;
}

void Sort::QuickSort (int left,int right)
{
	int pivotpos;
	if (left<right)
	{
		pivotpos=Partition(left,right);
		QuickSort(left,pivotpos-1);
		QuickSort(pivotpos+1,right);
	}
}

void Sort::HeapSort(int last)
{
	int sorted;
	int holdData;
	int walker;

	for(walker=1;walker<=last;walker++)
		ReheapUp(walker);

	sorted=last;
	while(sorted>0)
	{
		holdData=A[0];
		A[0]=A[sorted];
		A[sorted]=holdData;
		sorted--;
		ReheapDown(0,sorted);
	}
}

void Sort::ReheapUp(int newNode)
{
	int parent;
	int hold;

	if(newNode)
	{
		parent=(newNode-1)/2;
		if(A[newNode]>A[parent])
		{
			hold=A[parent];
			A[parent]=A[newNode];
			A[newNode]=hold;
			ReheapUp(parent);
		}
	}
}

void Sort::ReheapDown(int root,int last)
{
	int hold;
	int leftkey;
	int rightkey;
	int largeChildKey;
	int largeChildIndex;

	if((root*2+1)<=last)
	{
		leftkey=A[root*2+1];
		if((root*2+2)<=last)
			rightkey=A[root*2+2];
		else
			rightkey=-1;

		if(leftkey>rightkey)
		{
			largeChildKey=leftkey;
			largeChildIndex=root*2+1;
		}
		else
		{
			largeChildKey=rightkey;
			largeChildIndex=root*2+2;
		}

		if(A[root]<largeChildKey)
		{
			hold=A[root];
			A[root]=A[largeChildIndex];
			A[largeChildIndex]=hold;
			ReheapDown(largeChildIndex,last);
		}
	}
}

double Sort::ET(clock_t start,clock_t finish)
{
	return (double) (finish-start)/CLK_TCK;
}


void main()
{
	Sort S;
	clock_t start,finish;


	S.Menu();
   system("cls");
   S.Loading();
	system("cls");

   textattr(45);
   clrscr();
	cprintf("Program initiating...\r");
	cout<<"\n\n\n\n\n";
	cout<<"			 _______________ ______________     \n"
	      "			|		|              |    \n"
		  "			| Sorting type  | Time taken   |    \n"
	      "			|_______________|______________|    \n";

	cout<<setprecision(2);

	S.Init();
	start=clock();
	S.InsertionSort();
	finish=clock();
	cout<<"			|Insertion Sort "<<"| "<<setw(5)<<S.ET(start,finish)<<" seconds"<<"|"<<endl;

	S.Init();
	start=clock();
	S.ShellSort();
	finish=clock();
	cout<<"			|Shell Sort     "<<"| "<<setw(5)<<S.ET(start,finish)<<" seconds"<<"|"<<endl;

	S.Init();
	start=clock();
	S.SelectionSort();
	finish=clock();
	cout<<"			|Selection Sort "<<"| "<<setw(5)<<S.ET(start,finish)<<" seconds"<<"|"<<endl;

	S.Init();
	start=clock();
	S.BubbleSort();
	finish=clock();
	cout<<"			|Bubble Sort    "<<"| "<<setw(5)<<S.ET(start,finish)<<" seconds"<<"|"<<endl;

	S.Init();
	start=clock();
	S.MergeSort(0,MAX-1);
	finish=clock();
	cout<<"			|Merge Sort     "<<"| "<<setw(5)<<S.ET(start,finish)<<" seconds"<<"|"<<endl;

	S.Init();
	start=clock();
	S.QuickSort(0,MAX-1);
	finish=clock();
	cout<<"			|Quick Sort     "<<"| "<<setw(5)<<S.ET(start,finish)<<" seconds"<<"|"<<endl;

	S.Init();
	start=clock();
	S.HeapSort(MAX-1);
	finish=clock();
	cout<<"			|Heap Sort      "<<"| "<<setw(5)<<S.ET(start,finish)<<" seconds"<<"|"<<endl;


	cout<<"                         ------------------------------\n";

	cout<<endl;

   textcolor(35);

	cprintf("The total memory used by above sorting algorithms is: \n\r");
   cout<<sizeof(S)<<"\n"<<endl;

	cout<<endl;

   system("pause");

}