Code:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib> // Needed for rand() function
#include <ctime> // needed for time() function
using namespace std;
ofstream fout("MergeSort_versus_Quicksort_output.txt");
//***********************************************************************************
void Merge(int h, int m, const int U[], const int V[], int S[])
{
int j = 0;
int k = 0;
for (int i = h; i < m; i++)
{
if (U[j] < V[k]) {
S[i] = U[j];
j++;
}
else
{
S[i] = V[k];
k++;
}
}
}
//***********************************************************************************
void Swap(int & a, int & b)
{
int temp;
temp = a;
a = b;
b = temp;
}
//***********************************************************************************
void Partition(int low, int high, int S[])
{
int i, j;
int pivotpoint, pivotitem;
pivotitem = S[low];
j = low;
for(i = low + 1; i <= high; i++)
if (S[i] < pivotitem) {
j++;
Swap(S[i], S[j]);
}
pivotpoint = j;
Swap(S[low], S[pivotpoint]);
}
//***********************************************************************************
void QuickSort(int low, int high)
{
int pivotpoint;
if(high > low) {
Partition(low,high,pivotpoint);
QuickSort(low, pivotpoint - 1);
QuickSort(pivotpoint + 1, high);
}
}
//***********************************************************************************
void MergeSort(long n, int S[])
{
if(n > 1)
{
int U[n/2];
int V[n/2];
MergeSort(n/2,U);
MergeSort(n/2,V);
}
}
//***********************************************************************************
void StringOutput(char * s)
{
cout << s;
fout << s;
}
//***********************************************************************************
void OutputArray(long n, int S[])
{
long i;
for (i = 1; i <= n; i++)
{
cout << S[i] << " ";
fout << S[i] << " ";
}
cout << endl << endl;
fout << endl << endl;
}
//***********************************************************************************
int main()
{
cout << fixed << setprecision(3);
fout << fixed << setprecision(3);
StringOutput("------------------------------------------------------------\n");
StringOutput("MergeSort vs. QuickSort.\n");
StringOutput("------------------------------------------------------------\n\n\n");
long n, // size of the array
i, // loop counter
initialSize,
lastSize,
increment;
int upperLimit, // values in array will be from 1 to upperLimit
*S_0, // S_0 stores the unsorted array
*S_1, // S_1 array will be MergeSorted
*S_2; // S_2 array will be QuickSorted
clock_t startQuickSort, endQuickSort, startMergeSort, endMergeSort;
srand(time(NULL)*1000); // Seed the random number generator
//************ PART 1 **********************************************************************
StringOutput("--- Part 1 --------------------------------------------\n");
StringOutput("First we will test if MergeSort and QuickSort work:\n\n\n\n");
StringOutput("Enter the size of the array, or 0 to move on: ");
cin >> n;
fout << n << endl;
while (n > 0)
{
StringOutput("Enter the upper limit of array elements: ");
cin >> upperLimit;
fout << upperLimit << endl;
S_0 = new int[n+1];
S_1 = new int[n+1];
S_2 = new int[n+1];
for (i = 1; i <= n; i++)
S_0[i] = S_1[i] = S_2[i] = 1 + rand() % upperLimit;
MergeSort(n, S_1);
QuickSort(low, high, S_2);
StringOutput("\nUnsorted, the array is: \n\n");
OutputArray(n, S_0);
StringOutput("MergeSort results in: \n\n");
OutputArray(n, S_1);
StringOutput("QuickSort results in: \n\n");
OutputArray(n, S_2);
delete S_0;
delete S_1;
delete S_2;
StringOutput("------------------------------------------------------------\n");
StringOutput("\nEnter the size of the array, or 0 to move on: ");
cin >> n;
fout << n << endl;
}
//************ PART 2 **********************************************************************
StringOutput("\nMoving on...\n\n\n\n\n");
StringOutput("--- Part 2 -----------------------------------------------------------------\n");
StringOutput("Now we will time MergeSort vs. QuickSort.\n\n\n");
StringOutput("Enter the upper limit of array elements (to be used for all tests): ");
cin >> upperLimit;
fout << upperLimit << endl;
StringOutput("\n\nEnter the initial size of the list, or 0 to quit: ");
cin >> initialSize;
fout << initialSize << endl;
while (initialSize > 0)
{
StringOutput("Enter the lastSize of the list: ");
cin >> lastSize;
fout << lastSize << endl;
StringOutput("Enter the increment: ");
cin >> increment;
fout << increment << endl;
StringOutput("\n\n Size MergeSort QuickSort\n");
StringOutput("---------------------------------------------------------------\n\n");
for (n = initialSize; n <= lastSize; n = n + increment)
{
S_1 = new int[n+1];
S_2 = new int[n+1];
for (i = 1; i <= n; i++)
S_1[i] = S_2[i] = 1 + rand() % upperLimit;
cout << setw(8) << n;
fout << setw(8) << n;
startMergeSort = clock();
MergeSort(n, S_1);
endMergeSort = clock();
cout << setw(11) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.";
fout << setw(11) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.";
startQuickSort = clock();
QuickSort(low, high, S_2);
endQuickSort = clock();
cout << setw(13) << double((endQuickSort - startQuickSort))/CLK_TCK << " sec.\n";
fout << setw(13) << double((endQuickSort - startQuickSort))/CLK_TCK << " sec.\n";
delete S_1;
delete S_2;
}
StringOutput("------------------------------------------------------------------------------\n\n");
StringOutput("\n\nEnter the initial size of the list, or 0 to move on: ");
cin >> initialSize;
fout << initialSize << endl;
}
//************ PART 3 **********************************************************************
StringOutput("\nMoving on...\n\n\n\n\n");
StringOutput("--- Part 3 -----------------------------------------------------------------\n");
StringOutput("Now we will just time MergeSort by itself on very large list sizes.\n\n\n\n");
StringOutput("Enter the initial size of the list, or 0 to quit: ");
cin >> initialSize;
fout << initialSize << endl;
while (initialSize > 0)
{
StringOutput("Enter the lastSize of the list: ");
cin >> lastSize;
fout << lastSize << endl;
StringOutput("Enter the increment: ");
cin >> increment;
fout << increment << endl;
StringOutput("\n\n Size MergeSort \n");
StringOutput("------------------------------------------------------------------------------\n\n");
for (n = initialSize; n <= lastSize; n = n + increment)
{
S_1 = new int[n+1];
for (i = 1; i <= n; i++)
S_1[i] = 1 + rand() % upperLimit;
cout << setw(10) << n;
fout << setw(10) << n;
startMergeSort = clock();
MergeSort(n, S_1);
endMergeSort = clock();
cout << setw(13) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.\n";
fout << setw(13) << double((endMergeSort - startMergeSort))/CLK_TCK << " sec.\n";
delete S_1;
}
StringOutput("------------------------------------------------------------------------------\n\n");
StringOutput("\n\nEnter the initial size of the list, or 0 to quit: ");
cin >> initialSize;
fout << initialSize << endl;
}
StringOutput("\nBye!\n\n");
}
I get the following errors: