The assignment was to write a C++ program that implements Insertion, Bubble, Merge Sorts for sorting Arrays of non-negative integers. The three Algorithms should return as output not just the sorted Array but also the number of COMPARISONS needed to sort the array. The array is has randomly generated numbers from a certain range specified by the user. A function was also needed to check if the array has been correctly sorted.

I should use the vector container from the C++ Standard Template library. I should NOT USE any other STL algorithms for sorting/merging.

I'm a beginner at C++ and this is my first assignment using C++. Please help ! ! !

My problems are that the function for Insertion Sort and Bubble Sort are not returning the correct number of Comparisons even though they are calculating the right number of Comparisons inside the function.

Also the function for Merge Sort I'm getting errors when initializing the array L[] and R[] .

This are the errors I'm getting

Error 4 error C2057: expected constant expression 156

Error 5 error C2466: cannot allocate an array of constant size 0 156

Error 6 error C2133: 'L' : unknown size 156

Error 7 error C2057: expected constant expression 156

Error 8 error C2466: cannot allocate an array of constant size 0 156

Error 9 error C2133: 'R' : unknown size 156

```
// Platform : Microsoft Visual Studio 2005 ( Visual C++ )
//Problem 1
#include <iostream>
#include <cstdlib>
#include <vector>
#include <limits>
using namespace std;
int insertionSort (vector<int> &);
int bubbleSort (vector<int> &);
int mergeSort (vector<int> &, int , int);
void populateArrayRND (vector<int> &, int);
bool isSorted (const vector<int> &);
void printArray (const vector<int> &);
int main ()
{
int aSize;
int maxElem;
cout << "Size of the Array : ";
cin >> aSize; //input size of Array
cout << "Max element in the Array : ";
cin >> maxElem; //input max element of Array
vector< int > integers(aSize);
populateArrayRND(integers, maxElem);
printArray(integers);
vector<int> copy_integers_1(integers); //copy constructor
vector<int> copy_integers_2(integers); //copy constructor
vector<int> copy_integers_3(integers); //copy constructor
insertionSort(copy_integers_1);
printArray(copy_integers_1);
cout<<"Number of Comparisons needed: "<<insertionSort(copy_integers_1)<<endl; //wrong number of comparisons
if (isSorted(copy_integers_1)==1)
cout<<"Insertion Sort Array Sorted"<<endl<<endl;
else
cout<<"Insertion Sort Array not Sorted"<<endl<<endl;
bubbleSort(copy_integers_2);
printArray(copy_integers_2);
cout<<"Number of Comparisons needed: "<<bubbleSort(copy_integers_2)<<endl; //wrong number of comparisons
if (isSorted(copy_integers_2)==1)
cout<<"Bubble Sort Array Sorted"<<endl<<endl;
else
cout<<"Bubble Sort Array not Sorted"<<endl<<endl;
mergeSort(copy_integers_3, 1, aSize);
cout<<endl;
cin>>aSize;
return 0;
}
void populateArrayRND ( vector<int> &A, int M)
{
size_t i;
size_t ArraySize = A.size();
for ( i=0; i<ArraySize; i++ )
{
A[i]= rand() %M;
}
cout<<endl<<endl;
}
int insertionSort (vector<int> &A)
{
int i,key;
int Comp=0;
size_t ArraySize = A.size();
for(int j=1; j<ArraySize; j++)
{
key = A[j];
i=j-1;
while((i>=0)&&(A[i]>key))
{
A[i+1] = A[i];
i--;
Comp=Comp+1;
}
A[i+1] = key;
Comp++;
}
cout<<"here "<<Comp; // correct number of comparisons
return Comp;
}
int bubbleSort (vector<int> &A)
{
int Temp;
int Comp=0;
size_t ArraySize = A.size();
for (int i=0; i<ArraySize; i++)
{
for (size_t j=ArraySize; j>(i+1); j--)
{
if (A[j-1]<A[j-2])
{
Temp = A[j-1];
A[j-1] = A[j-2];
A[j-2] = Temp;
Comp++;
}
}
}
cout<<"here "<<Comp; //correct number of comparisons
return Comp;
}
int mergeSort (vector<int> &A, int p, int r)
{
int Comp=0;
int q =(p+r)/2;
int n1 = (q-p+1);
int n2 = (r-q);
int i, j;
const int Left_Size = n1+1;
const int Right_Size = n2+1;
int L[Left_Size], R[Right_Size]; // line 156
for (i=0; i<n1; i++)
L[i] = A[1+i-1];
for (j=0; j<n2; j++)
R[j] = A[q+j];
L[n1+1]=R[n2+1]= numeric_limits<int>::max(); //sentinel
i=j=0;
for (int k=(p-1); k<r; k++)
{
if (L[i]<= R[j])
{
A[k] = L[i];
i=i+1;
Comp=Comp+1;
}
else
{
A[k] = R[j];
j=j+1;
Comp=Comp+1;
}
}
for (int l=0; l<r; l++)
cout<<A[l]<<" ";
cout<<endl;
cout<<Comp;
return(Comp);
}
bool isSorted (const vector<int> &A)
{
size_t ArraySize = A.size();
for ( int i=0; i<ArraySize; i++)
{
if ((i>=0)&&(A[i]<=A[i+1])){
return true;
}
else{
return false;
break;
}
}
}
void printArray (const vector<int> &A)
{
size_t ArraySize = A.size();
cout<<"Array: ";
for (int i=0; i<ArraySize; i++)
cout<<A[i]<<" ";
cout<<endl<<endl;
}
```