Implementation of Sorting Algorithms

[bartuaslan]

You should write a program to sort an array. For this purpose you will implement two sorting algorithms: Insertion Sort and Merge Sort. For each algorithm, you are supposed to have a counter and count how many times a comparison is made to sort the array. Once this logic is implemented, create integer arrays of 1000 and 10000 elements with random values inside (you can implement a random number generator for this purpose and randomize their elements).

Then go ahead and run your application. The output should show us how many comparisons it made for each algorithm for 1000 and 10000 elements.


//header file
#include<iostream>
#include<time.h>
//using namespace
using namespace std;

// Insertion sort sorting function it will take array and its size an argument
void insertionSort(int nums[], int m, int& comparisonsCount)
{
int j, val, i;
for (j = 1; j < m; j++)
{
val = nums[j];
i = j - 1;
comparisonsCount++;
while (i >= 0 && nums[i] > val)
{
comparisonsCount++;
nums[i + 1] = nums[i];
i = i - 1;
}
nums[i + 1] = val;
}
}

// Merge sort sorting function

void merge(int nums[], int left, int middle, int right,int& comparisonsCount)
{
int m1 = middle - left + 1;
int m2 = right - middle;
int L[m1], R[m2];

for (int j = 0; j < m1; j++)
L[j] = nums[left + j];
for (int i = 0; i < m2; i++)
R[i] = nums[middle + 1 + i];
int j = 0;
int i = 0;

int s = left;

while (j < m1 && i < m2) {
if (L[j] <= R[i]) {
comparisonsCount++;
nums[s] = L[j];
j++;
}
else {
nums[s] = R[i];
i++;
}
s++;
}
while (j < m1) {

nums[s] = L[j];
j++;
s++;
}
while (i < m2) {
nums[s] = R[i];
i++;
s++;
}
}
void mergeSort(int nums[],int left,int right, int& comparisonsCount){
if(left>=right){
return;//returns recursively
}
int middle =left+ (right-left)/2;
mergeSort(nums,left,middle,comparisonsCount);
mergeSort(nums,middle+1,right,comparisonsCount);
merge(nums,left,middle,right,comparisonsCount);
}
//main function
int main()
{
srand(time(0));
int arr_1[1000]; int copy_arr1[1000];
int arr_2[10000]; int copy_arr2[10000];

for(int j=0; j<1000; j++)
{
arr_1[j]=rand();
copy_arr1[j]=arr_1[j];
}
int count_insertion=0;
int count_merge=0;
insertionSort(arr_1,1000,count_insertion);
mergeSort(copy_arr1,0,1000-1,count_merge);

cout<<"For 1000 length array: \n";
cout<<"Comparision made for insertion sort: "<<count_insertion;
cout<<"\nComparision made of merge sort : "<<count_merge;



for(int j=0; j<10000; j++)
{
arr_2[j]=rand();
copy_arr2[j]=arr_1[j];
}
count_insertion=0;
count_merge=0;
insertionSort(arr_2,10000,count_insertion);
mergeSort(copy_arr2,0,10000-1,count_merge);

cout<<"\n\nFor 10000 length array: \n";
cout<<"Comparision made for insertion sort: "<<count_insertion;
cout<<"\nComparision made of merge sort : "<<count_merge;
}

It gives Array type int m2 not assignable in Merge sort sorting function file.
And also it gives expression must contain a constant value error.How can i fix that errors?

[jonnin]

int L[m1], R[m2];

this is not legal, you have to have a compile time constant for array sizes.
you can pass the 'used' size and keep them the original size of the array -- that is how it is done in C. in c++ you would normally use a vector, which can be sized at run-time instead, but many schools seem to frown on using these tools.

I don't see the other error, because its not formatted as code and hard to follow. try putting code tags around it <> on the edit side bar, or [cod e] type tags by hand if you want.

[seeplus]

This compiles and runs:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

// Insertion sort sorting function it will take array and its size an argument
void insertionSort(int nums[], int m, int& comparisonsCount)
{
	int j, val, i;

	for (j = 1; j < m; j++)
	{
		val = nums[j];
		i = j - 1;
		comparisonsCount++;
		while (i >= 0 && nums[i] > val)
		{
			comparisonsCount++;
			nums[i + 1] = nums[i];
			i = i - 1;
		}
		nums[i + 1] = val;
	}
}

// Merge sort sorting function

void merge(int nums[], int left, int middle, int right, int& comparisonsCount)
{
	int m1 = middle - left + 1;
	int m2 = right - middle;
	//int L[m1], R[m2];
	int L[10000] {}, R[10000] {};	// TO GET TO COMPILE. TO CHANGE

	for (int j = 0; j < m1; j++)
		L[j] = nums[left + j];

	for (int i = 0; i < m2; i++)
		R[i] = nums[middle + 1 + i];

	int j = 0;
	int i = 0;
	int s = left;

	while (j < m1 && i < m2) {
		if (L[j] <= R[i]) {
			comparisonsCount++;
			nums[s] = L[j];
			j++;
		} else {
			nums[s] = R[i];
			i++;
		}
		s++;
	}

	while (j < m1) {
		nums[s] = L[j];
		j++;
		s++;
	}

	while (i < m2) {
		nums[s] = R[i];
		i++;
		s++;
	}
}

void mergeSort(int nums[], int left, int right, int& comparisonsCount) {
	if (left >= right) {
		return;//returns recursively
	}

	int middle = left + (right - left) / 2;

	mergeSort(nums, left, middle, comparisonsCount);
	mergeSort(nums, middle + 1, right, comparisonsCount);
	merge(nums, left, middle, right, comparisonsCount);
}

//main function
int main()
{
	srand(time(0));

	int arr_1[1000]; int copy_arr1[1000];
	int arr_2[10000]; int copy_arr2[10000];

	for (int j = 0; j < 1000; j++)
	{
		arr_1[j] = rand();
		copy_arr1[j] = arr_1[j];
	}

	int count_insertion = 0;
	int count_merge = 0;

	insertionSort(arr_1, 1000, count_insertion);
	mergeSort(copy_arr1, 0, 1000 - 1, count_merge);

	cout << "For 1000 length array: \n";
	cout << "Comparision made for insertion sort: " << count_insertion;
	cout << "\nComparision made of merge sort : " << count_merge;

	for (int j = 0; j < 10000; j++)
	{
		arr_2[j] = rand();
		copy_arr2[j] = arr_1[j];
	}

	count_insertion = 0;
	count_merge = 0;

	insertionSort(arr_2, 10000, count_insertion);
	mergeSort(copy_arr2, 0, 10000 - 1, count_merge);

	cout << "\n\nFor 10000 length array: \n";
	cout << "Comparision made for insertion sort: " << count_insertion;
	cout << "\nComparision made of merge sort : " << count_merge;
}

NOTE L32 & L33 changed so will compile

For 1000 length array:
Comparision made for insertion sort: 252821
Comparision made of merge sort : 4401

For 10000 length array:
Comparision made for insertion sort: 25184999
Comparision made of merge sort : 64607

[bartuaslan]

It gives error again
Error LNK1169 one or more multiply defined symbols found
Error LNK2005 "void __cdecl mergeSort(int * const,int,int,int &)" (?mergeSort@@YAXQAHHHAAH@Z) already defined in main.obj
Error LNK2005 "void __cdecl merge(int * const,int,int,int,int &)" (?merge@@YAXQAHHHHAAH@Z) already defined in main.obj

[seeplus]

Well my code above compiles ok with VS2019 as 1 compile unit. What compiler are you using? What files are you including in the compilation? It seems that you're trying to compile more than 1 file?

[bartuaslan]

i use vs2019 too. with 3 files. 1 cpp 1 header file 1 main file. and it gives that errors.

[Ganado]

seeplus's code is a one-file program. If you are redefining mergeSort or merge in another file, you are creating multiple definitions.

[doug4]

If the file containing main() #includes the other source (.cpp) file, then you can have multiple definitions that way, too.

[bartuaslan]

how can i do that with 3 files can you write the code? with 1 header and 2 cpp

[doug4]

I'm not going to write the code for you.

But, header files are intended to be #included into multiple source files.

Each source file (.cpp file) is compiled as a separate compilation unit. At the end, you link the compilation units together to get the whole program.

When you #include a file, you essentially copy its contents right where the #include statement is. So, if File A.cpp #includes B.cpp, all of B.cpp is now included in A.cpp. If both get compiled and linked together, all of the functions in B.cpp will be found in 2 places - the compiled version of A.cpp as well as the compiled version of B.cpp.

So, your A.cpp should only include the header for B.cpp, not B.cpp itself.

B.h

void b_function(int);

B.cpp

#include "b.h"
#include "iostream"
void b_function(int a)
{
    std::cout << "The int is " << a << std::endl;
}

A.cpp

#include "B.h"   // Not B.cpp
int main()
{
    b_function(5);
    return 0;
}

[jonnin]

^^ this is more important than it seems at first. When I started, I included .cpp files and it all works ... until it does not. It works so long as the projects are small and do not include the same cpp file in a way that confuses the tool, but as your code gets larger and more things happen it will invariably break trying to do it that way. Its not clear at all at first why this happens, but I encourage you to do what he said above and after a while you will see why it breaks (its because it ends up with multiple copies of the same function, and its not smart enough to know that the code is identical, it just knows that you are not supposed to have 2 copies of one function and it stops there to throw errors). The same sorts of problems can also crop up if you do not use include guards on the header files, and like the cpp issue, they often do not early on but show up as you get more complex problems. Best to get in the habit of doing this stuff right as soon as you can so it does not lead to an out of control mess later on.