Code:
# include <iostream.h>
# include <conio.h>
# include <iomanip.h>
# include <time.h>
# include <stdlib.h>
# include <fstream.h>
# define Size 30000 //need to remove the definition
void getRandomNumber(int[],int);
void MergeSort(int[], int, int);
void merge(int[], int, int);
void SelectionSort(int[], int); //Remove this
void QuickSort (int[],int);
void HeapSort(int[],int);
void InsertionSort (int[],int); //or remove this
void PrintArray(int[],int);
ofstream outf("c:\\Output.txt",ios::app); //Prints output to the c: drive
main() //Main of the Program
{
int Array[Size];
clock_t start, end;
getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
MergeSort(Array,20,20);
cout<<"Sorted array (Merge Sort): \n";
outf<<"Sorted array (Merge Sort):"<<endl; PrintArray(Array,20);
getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
SelectionSort(Array,20);
cout<<"Sorted array (Selection Sort): \n";
outf<<"Sorted array (Selection Sort):"<<endl; PrintArray(Array,20);
getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
QuickSort(Array,20);
cout<<"Sorted array (Quick Sort): \n";
outf<<"Sorted array (Quick Sort):"<<endl; PrintArray(Array,20);
getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
HeapSort(Array,20);
cout<<"Sorted array (Heap Sort): \n";
outf<<"Sorted array (Heap Sort):"<<endl; PrintArray(Array,20);
getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
InsertionSort(Array,20);
cout<<"Sorted array (Insertion Sort): \n";
outf<<"Sorted array (Insertion Sort):"<<endl; PrintArray(Array,20);
//**************************
cout<<"Size\tTime(selection)\tTime(Heap)\n";
cout<<"-----------------------------\n";
outf<<"Size\tTime(selection)\tTime(Heap)\n";
outf<<"-----------------------------\n";
//**************Major Editing
for(int i=2000; i<=Size; i=i+2000)
{
getRandomNumber(Array,i);
start = clock();
SelectionSort(Array,i);
end = clock();
cout<<i<<"\t\t"<<(end-start)/CLK_TCK<<"\t";
outf<<i<<"\t\t"<<(end-start)/CLK_TCK<<"\t";
getRandomNumber(Array,i);
start = clock();
HeapSort(Array,i);
end = clock();
cout<<(end-start)/CLK_TCK<<endl;
outf<<(end-start)/CLK_TCK<<endl;
}
getch();
return 0;
}
void getRandomNumber(int array[],int size) { srand(time(0)); for(int i=0; i<size; i++)
array[i]=rand()%201-100;
}
void PrintArray(int array[],int size)
{
for(int i=0; i<size; i++)
{
cout<<setw(4)<<array[i]<<((i+1)%10?" ":"\n");
outf<<setw(4)<<array[i]<<((i+1)%10?" ":"\n"); } cout<<endl; }
//*****************************************************************************
void MergeSort(int a[], int left, int right)
{
if(left<right)
{
int mid=(left + right)/2;
MergeSort(a, left, mid);
MergeSort(a, mid+1, right);
merge(a,left,right);
}
}
void merge(int a[],int left, int right)
{
int size=right-left+1,
mid=(left+right)/2;
int y, put;
int *b=new int[size];
int count=0;
for(int x=left;x<=mid;x++,count++)
{
b[count]=a[x];
}
for(x=right;x>=mid+1;x--,count++)
{
b[count]=a[x];
}
for(x=0,y=size-1,put=left;x<=y;put++)
{
if(b[x]<=b[y])
{
a[put]=b[x];
x++;
}
else
{
a[put]=b[y];
y--;
}
}
delete[] b;
}
//*********************************************************************************
void SelectionSort(int b[], int s)
{
int k,x,i,j;
for(i = 0; i < s-1 ; i++)
{
k = i;
x = b[i];
for(j = i+1; j< s; j++)
if(b[j] < x)
{
k=j;
x=b[j];
}
b[k]=b[i];
b[i]=x;
}
}
//******************************************************************************************
void choosePivot(int c[], int first, int last){
{
int pivotIndex;
int mid = (first + last) / 2;
if( c[ first ] <= c[ mid ] )
{ if( c[ mid ] <= c[ last ] ) pivotIndex = mid;
else pivotIndex = ( c[ first ] <= c[ last ] ? last : first );
}
else if( c[ last ] <= c[ mid ] ) pivotIndex = mid;
else pivotIndex = ( c[ first ] <= c[ last ] ? first : last );
swap( c[ first ], c[ pivotIndex ] );
}
}
void partition(int c[], int first, int last, int& pivotIndex)
{
choosePivot(c, first, last);
int pivot = c[first];
int lastS1 = first;
int firstUnknown = first + 1;
for (; firstUnknown<=last;++firstUnknown)
{
if (c[firstUnknown]<pivot)
{
++lastS1;
swap(c[firstUnknown],c[lastS1]);
}
}
swap(c[first], c[lastS1]);
pivotIndex = lastS1;
}
void quicksort(int c[], int first, int last)
{
int pivotIndex;
if (first<last)
{
partition(c, first, last, pivotIndex);
quicksort(c, first, pivotIndex-1);
quicksort(c, pivotIndex+1, last);
}
}
//*******************************************************************************
void HeapSwap(int d[], int l, int k)
{
int temp;
temp = d[l];
d[l] = d[k];
d[k] = temp;
}
void Shift(int d[], int first, int last) { int largest = 2*first+1;
while(largest <= last)
{
if(largest < last)
if(d[largest] < d[largest+1])
largest++;
if(d[first] < d[largest])
{
HeapSwap(d, first,largest);
first = largest;
largest = 2*first+1;
}
else
largest = last+1;
}
}
void HeapSort(int d[], int size)
{
register int i;
for(i = size/2-1; i >=0; --i)
Shift(d,i,size-1);
for(i = size-1; i > 1; --i)
{
HeapSwap(d, 0, i);
Shift(d,0,i-1);
}
if(d[0] > d[1])
HeapSwap(d, 0, 1);
}
//**************************************************************************
void insertionSort(int e[], int n)
{
for (int unsorted=1;unsorted<n;++unsorted)
{
int nextItem = e[unsorted];
int loc = unsorted;
for (;(loc>0) && (e[loc-1]>nextItem);--loc)
e[loc] = e[loc-1];
e[loc] = nextItem;
}
}
