Click here to Skip to main content
15,885,032 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Dear all,

I got the bright idea to do a merge sort code without creating arrays recursively (obviously not linked lists). The logic seems to be right and every variable behaves as it should except one, and I just can't seem to figure out why. I hope someone has some time to help me.

I will write a separate program that does merge sort on linked lists but here, I wanted to overcome merge sort's main weakness in terms of the extra overhead so I decided to experiment with this.

Please see the code below:

C++
/* includes and macros */
// required for input / output with minGW GCC
#include <stdio.h>
#define printf __mingw_printf

// required for the dynamic storage allocation and the random integer generator functions
#include <stdlib.h>

// required for the time function, which is required for rand() to work properly
#include <time.h>



/* type definitions  (structs go here) */



/* global declarations */
static unsigned short n = 0;



/* function prototypes */
void swapSort (int *, int *);
void mergeSort (int []);



/* main function */
int main ()
{
	/* some initial declarations & initializations */
	// ask the user for the amount of integers to sort
	printf("How many integers do you want sorted by Merge Sort? ");
	scanf("%hu", &n);

	// for rand()
	srand(time(NULL));

	// array input
	int arrayInput[n];


	/* array input */
	// input taken from the rand() function
	printf ("\n");
	for (register unsigned short i = 0; i <= n-1; i++)
		arrayInput[i] = rand();

	// printing the input so the user knows exactly what rand() produced
	printf ("\n");
	for (register unsigned short i = 0; i <= n-1; i++)
		printf ("[%d] ", arrayInput[i]);
	printf ("\n");


	/* sort the list by Merge Sort */
	mergeSort(arrayInput);


	/* print the sorted array */
	printf("\n");
	for (register unsigned short i = 0; i <= n-1; i++)
		printf("[%d] ", arrayInput[i]);
	printf("\n");


	/* exit main and the program */
	return 0;
}



/* function definitions */
/* simple swapping function */
void swapSort (int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}


/* the Merge Sort function, improving upon bubble sort */
void mergeSort (int mainArray[])
{
	// sort the subarrays formed by every two elements, then by every four elements, then by 8, etc.
	for (unsigned short sizeSubArr = 2; sizeSubArr <= n;)  // set the outer loop so that it sorts all the subarrays of a specific size; the subarray size will change per iteration
									      // of the loop so there may be a remainder subarray of a different size than sizeSubArr
	SubArrayMarkers:
	{
		unsigned short total_number_of_subarrays = n / sizeSubArr;
		unsigned short remSizeSubArr = n % sizeSubArr;
		unsigned short subArrLen = sizeSubArr;
		for (unsigned short mainIndex = 0, subArrNo = 1; subArrNo <= total_number_of_subarrays; mainIndex++)  // a loop that marks the beginning of each subarray as it goes through
																	                   // the main array and then the subarray is sorted by this loop's inner loops
																	                   // it also keeps track of the index of the main array
		{
			BubbleSort:
			for (unsigned short j = 0; j <= n; j = 0)  // this is where bubble sort starts, with the infinite outer loop to be broken if there are no swaps done within the bubble sort
									    // we set l to mainIndex so that if there are multiple iterations of bubble sort, it doesn't screw up mainIndex
			{
				unsigned short l = mainIndex;
				for (register unsigned short k = 1; k <= subArrLen-1; k++, l++)  // one bubble sort iteration through the current sub array of the outer loop
				{
					if (mainArray[l] > mainArray[l+1])
					{
						swapSort(&mainArray[l], &mainArray[l+1]);
						j++;
					}
				}
				if (j == 0)
				{
					mainIndex = l;  // once a subarray is sorted, we need to set mainindex to l's current value so that it can start on the next subarray the next time bubble sort is invoked
					break;
				}
			}
			subArrNo++;  // the incrementation is done here so that a final iteration can be done on the loop based on the following if statement
			if ((subArrNo > total_number_of_subarrays) && (remSizeSubArr >= 2))
			{
				subArrLen = remSizeSubArr;
				mainIndex++;
				goto BubbleSort;
			}
		}
		sizeSubArr *= 2;  // the incrementation is done here so that a final iteration can be done on the loop based on the following if statement
		if (sizeSubArr > n && remSizeSubArr != 0)
		{
			sizeSubArr = n;
			goto SubArrayMarkers;
		}
	}
}


What I have tried:

I have debugged and debugged and debugged. I have pinpointed the problem to the l variable but can't seem to see why it's inflating to 100+ value even for a 10 integer array. It's not supposed to go beyond 10, in any case.
Posted
Updated 13-Aug-16 0:47am

Bug here:
C++
int arrayInput[n];

This is ok as long as n is known at compile time. In your case, you need to resort to pointer and dynamic memory allocation at runtime.
C library function - malloc()[^]

Bug again:
C++
void mergeSort (int mainArray[])

you can't transmit an array as parameter, the parameter must be a pointer to the array.


Here is a good lecture:
The C Programming Language - Wikipedia, the free encyclopedia[^]
https://hassanolity.files.wordpress.com/2013/11/the_c_programming_language_2.pdf[^]
http://www.ime.usp.br/~pf/Kernighan-Ritchie/C-Programming-Ebook.pdf[^]

[Update]
- Bubble sort is done in place because it only resort swaping to perform the sort.
- Quick sort and Merge sort both need to resort to array copy because the merge part can't be done in place (or it need special programming to merge in place).

With linked list, you can avoid copying data because everything is done by changing pointers, but it comes at cost.
 
Share this answer
 
v3
Comments
Aamir Yousafi 13-Aug-16 6:54am    
ppolymorphe, yes, you're probably right about the dynamic memory allocation. I'm going to use that from now on for all my arrays whether or not they are linked lists.

Regarding the array / pointer being passed to the function, well, my experience is that if you're passing a pointer, you should pass it as such and when you're passing an array, you pass it as such. I remember getting frustrated with my quicksort algorithm code for recursive calls when I was trying to pass pointers that would work on the arrays because it was crashing. Finally, when I changed all of those pointers to arrays that would be recursively declared and passed to the quicksort function recursively, I got it to work. I can share my quicksort code with you so you know where I'm coming from on this.
Aamir Yousafi 13-Aug-16 6:56am    
So, actually, if you have a way to fix that quicksort function so that it doesn't need to create new arrays, which I was trying to avoid doing, then I would love that. Let me know if you want me to share that code.
Okay ... sorry, all. I found the solution. It was an if statement that was screwing things up. Anyway, here is the updated code of the if statement that was causing the problem:

C++
if ((subArrNo > total_number_of_subarrays) && (remSizeSubArr >= 2))
{
    if (remSwaps != 0)
        break;
    subArrLen = remSizeSubArr;
    mainIndex++;
    remSwaps++;
    goto BubbleSort;
}
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900