Thread: A problem with a really basic program

Hi everyone,
I need to write the function:
int** ptrSort(int* arr, int size)

The function gets an array and its size,and returns a pointers array, which includes pointers that point to the array (arr) cells, so they are sorted from the smallest to the biggest, and I have to use merge sort method to do that. then, I should print the sorted numbers.

I wrote a program,and the functions of course, but it doesn't work

The file attachment doesn't work, so I pasted it here:
Pastie

Any help will be appreciated
Thanks a lot!

The code, for those who don't want to go off-site:

Code:

#include <stdio.h>
#include <stdlib.h>

//Declaration of ProtoTypes
int** ptrSort(int* arr, int size);
void mergeSort(int ** arr, int size);
void merge( int** sortArr1, int size1, int** sortArr2, int size2, int** outSortArr);
void copyArray(int ** arr, int ** tempArr, int size);
void printPointersArray(int ** pArr,int size);

void main()
{
	int numbers[4]={7,2,5,9};
	int size=4;
	int **pArr;
	 
    pArr = ptrSort(numbers, size);
	printPointersArray(pArr,size);    
}

int** ptrSort(int* arr, int size)
{
	int ** pArr;
	int index;

	pArr=(int**)malloc(sizeof(int*)*size);
	if (pArr==NULL)
	{
		printf("Bad Memory Allocation");
		exit(1);
	}
	for (index=0;index<size;index++)
	{
		pArr[index]=arr+index;
	}
	mergeSort(pArr,size);

	return pArr;
}

// "Merge sort"
void mergeSort( int ** pArr, int size)
{
	int** tempArr;
	
	if (size == 1)
	{
		return;
	}
	else{
		mergeSort(pArr, size/2);
		mergeSort(pArr+(size/2), size-(size/2));
		tempArr = (int**)malloc(sizeof(int*)*size);
		if (tempArr==NULL)
		{
			printf("Bad Memory Allocation");
			exit(1);
		}
		merge(pArr, size/2, pArr + size/2, size-(size/2), tempArr);
		copyArray(pArr, tempArr, size);
		free (tempArr);
	}
}

// Merge two sorted array into a new array
void merge( int** sortArr1, int size1, int** sortArr2, int size2, int** outSortArr)
{
	int readInd1, readInd2, writeInd;
	readInd1 = readInd2 = writeInd = 0;
	while(readInd1 < size1 && readInd2 < size2)
	{
		if(*sortArr1[readInd1] < *sortArr2[readInd2])
		{
			*outSortArr[writeInd] = *sortArr1[readInd1];
			readInd1++;
			writeInd++;
		}
		else {
			*outSortArr[writeInd] = *sortArr2[readInd2];
			readInd2++;
			writeInd++;
		}
	}
}
void copyArray(int ** arr, int ** tempArr, int size)
{
	int index;

	tempArr=(int**)malloc(sizeof(int*)*size);
	for(index=0;index<size;index++)
		*tempArr[index] = *arr[index];
}

void printPointersArray(int ** pArr,int size)
{
	int index;

	if (size==0)
	{
		printf("There are not numbers to be printed");  
		return;
	}

	printf("The sorted array is : /n");
	for (index=0;index<size;index++)
	{
		printf("%d ",*(pArr[index]));
	}
}

I had a look at this. I guess it's mandated that you need to return an array of pointers? Seems a bit wasteful when you could just return a sorted array, might be easier to debug. I'm unsure if you intended to swap the values around at merge time -- I'd probably leave the pointers pointing to the same numbers and reorder the pointers in the array, rather than changing what the pointers point to. That is, in merge() I'd dereference the pointers for the comparison but not for the subsequent assingment.

I'm afraid I'm not au fait enough with merge sort to know if your implementation of the sorting algorithm is good. I think it has problems: e.g. you seem to throw away the intermediate merge result by reallocating the temp array in copyArray. A couple of other little things came up too -- but I'd say your best bet would be to work through the algorithms atages by hand for that data set, then use a debugger or printfs to see where it's going wrong. It seems (though I could be wrong) that there are quite a lot of little bugs and mistakes, you'll definitely learn more if you debug them yourself: And probably manage it faster than me since I don't know merge sort. I don't see think there are any "horrors of C" lurking.

Hi,
I had to do it in that way because this is an exercise anyway, I sat for hours to understand all the things I did wrong and I did it

Started from the copyArray, and so on..

Thanks!

Originally Posted by smokeyangel

I had a look at this. I guess it's mandated that you need to return an array of pointers? Seems a bit wasteful when you could just return a sorted array, might be easier to debug. I'm unsure if you intended to swap the values around at merge time -- I'd probably leave the pointers pointing to the same numbers and reorder the pointers in the array, rather than changing what the pointers point to. That is, in merge() I'd dereference the pointers for the comparison but not for the subsequent assingment.

I'm afraid I'm not au fait enough with merge sort to know if your implementation of the sorting algorithm is good. I think it has problems: e.g. you seem to throw away the intermediate merge result by reallocating the temp array in copyArray. A couple of other little things came up too -- but I'd say your best bet would be to work through the algorithms atages by hand for that data set, then use a debugger or printfs to see where it's going wrong. It seems (though I could be wrong) that there are quite a lot of little bugs and mistakes, you'll definitely learn more if you debug them yourself: And probably manage it faster than me since I don't know merge sort. I don't see think there are any "horrors of C" lurking.

Thanks.. you were definitely right!
And the first thing that helped is your comment about copyArray.

Thanks again!