(Newbie) Need C++ programming help

[gus7984]

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;

}

[kes166]

for your insertion and bubble sort, you are returning the comparison value, but you are not assinging it to anything when that value is returned. In your main

insertionSort(copy_integers_1);

Change that to:

int compInsertion = 0;
...
compInsertion = insertionSort(copy_integers_1);

and do the same with your bubble sort.

It actually would work the way it is, but the second time you call your functions (in your cout statements in main) the arrays are already sorted.

As for your error, try this

int *L = new int[Left_Size];
int *R = new int[Right_Size];

Also, you probably don't need to declare Left_Size or Right_Size as const.

[gus7984]

Thank you so much kes166. My code now works thanks to you. Could you explain to me why initializing them this way works?
1.
int *L = new int[Left_Size];
2.
int *R = new int[Right_Size];

[kes166]

Basically, arrays need to be declared with a known size prior to execution. You were trying to declare a fixed array even though it had a variable size. If you don't know the size of the array, you need to create the space for it dynamically which is what

int *array = new int[size];

does.

Since there is no way to to know the size needed of the array, you have to either make it large enough so the array won't go out of bounds or declare the array dynamically. Whenever you need to declare an array of size n, you need to declare it dynamically.

I think some compilers allow you to write code where if you use a variable it will declare it dynamically, but if you get an error from trying to declare an array with a varaible size, it's most likly trying to declare a fixed array as a dynamic array.