Thread: MergeSort with array of pointers

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    23

    MergeSort with array of pointers

    Hello again,
    This is one of my favourite forums in the net.
    And now for the question:
    I am trying the recursive mergeSort approach, but now I'm using an array
    of pointers, in which each of them will point to values in another array, and in a sorted way.
    And now for the problem... In order to free the pointers array, I need to free each one of the pointers, and then free the int** address.

    But by doing so, it calls a runtime error:
    "Debug assertion failed". I think that one means that I didn't handle the pointers in the right way. After searching for several hours, I'm lost. I can't find bugs in my code. It prints output perfectly and saves the original array intact. But it has a problem by freeing the pointers in the array.

    These are my functions... I mean these functions are the only ones in my code that deals with handling and updating the pointers. Now, can someone tell me what's wrong here?
    If you need all of the code, just ask for it, but if there's a problem, it must be in here...

    Hold on tight for this one...

    Code:
    int** pointerSort(int* arr, int size){
    	int** outA;
    	int i;
    	outA=(int**)malloc(size*sizeof(int*));
    	if (outA!=NULL)
    	{
    		for (i=0; i<size; i++)
    			outA[i]=&arr[i];	
    		mergeSort(outA,size);
    	}
    	else
    		return NULL;
    
    	return outA;
    }
    
    void mergeSort(int** arr, int size)
    {
    	int** res;
    	int numRes;
    
    	if (size==1)
    	{			
    		return;
    	}
    	else
    	{
    		mergeSort(arr, size/2);
    		mergeSort(arr+size/2, size-size/2);
    		res=(int**)malloc(size*sizeof(int*));
    		if (res!=NULL)
    		{
    			merge(arr, size/2, arr+size/2, size-size/2, res, &numRes);		
    			copyPtrsArray(arr, res, size);
    			free((void*)res);
    		}
    		else
    		{
    			printf("\n failure in sorting \n");
    			return;
    		}
    	}	
    }
    
    void merge(int** src1, int size1, int** src2, int size2, int** res, int* numRes)
    {
    	int i=0,j=0, iRes=0;
    	
    	while ((i<size1)&&(j<size2))
    	{
    		if (*src1[i]<*src2[j])
    		{
    			res[iRes]=src1[i];
    			iRes++;		
    			i++;
    		}
    		else
    		{
    			res[iRes]=src2[j];
    			iRes++;		
    			j++;
    		}
    	}	
    
    	while (j<size2)
    	{
    		res[iRes]=src2[j];
    		iRes++;
    		j++;
    	}
    	
    	while (i<size1)
    	{
    		res[iRes]=src1[i];
    		iRes++;
    		i++;
    	}	
    
    	*numRes=size2+size1;
    }
    
    void freeArray(int** a1, int size){
    	int i;
    	for (i=0; i<size; i++)
    		free((void*)a1[i]);
    	free((void*)a1);
    }
    Last edited by lionheart; 07-31-2008 at 03:35 PM.

  2. #2
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Where/how are you calling freeArray?

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    23
    This is my main()

    Code:
    void main(){
    	int* arr;
    	int** a1;
    	
    	//initializing an array for sampling
    	arr=(int*)malloc(ARRAY_SIZE*sizeof(int));
    	if (arr!=NULL)
    	{
    		arr[0]=7;
    		arr[1]=2;
    		arr[2]=5;
    		arr[3]=9;
    		arr[4]=4;
    		a1=pointerSort(arr, ARRAY_SIZE);
    		if (a1!=NULL)
    		{
    			//printing the sorted and the original array, for sampling purpose
    			printf("The sorted array is: ");
    			printPtrArray(a1,ARRAY_SIZE);		
    			printf("The original array is: ");
    			printArray(arr,ARRAY_SIZE);
    			freeArray(a1, ARRAY_SIZE);
    			free((void*)arr);
    		}
    		else
    			printf("\n Failure \n");
    	}
    The assumption is that a1 is not empty, and I take care of it in pointerSort().
    Last edited by lionheart; 07-31-2008 at 07:52 PM.

  4. #4
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Seems to me you are freeing a1 twice. Once in freeArray and once in main.

  5. #5
    Registered User
    Join Date
    Jun 2008
    Posts
    23
    This is the only time... freeArray(a1, ARRAY_SIZE);

  6. #6
    Registered User
    Join Date
    Jun 2008
    Posts
    23
    I think that I need to use malloc in pointerSort() in order to allocate one pointer for each cell.

    Please tell me if this is the correct fix......
    that means adding this: (to pointerSort)
    Code:
    	for (i=0; i<size; i++)
    		outA[i]=(int*)malloc(sizeof(int));
    I've tried it and it's not working either.
    oh, and a1 is not equal to arr... that's the all point in this program.
    Last edited by lionheart; 07-31-2008 at 08:16 PM.

  7. #7
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Okay, but why do you have a free() after calling freeArray?

  8. #8
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Nevermind. Your code is confusing me.

  9. #9
    Registered User
    Join Date
    Jun 2008
    Posts
    23
    freeArray(a1, ARRAY_SIZE);
    free((void*)arr);

    'cause a1 and arr are not equal. I am freeing a1, and then arr.

    I think also that I took care of everything in this code, including indentation.
    Last edited by lionheart; 07-31-2008 at 08:40 PM.

  10. #10
    Registered User
    Join Date
    Jun 2008
    Posts
    23

    Question MergeSort with an array of pointers

    I think the problem is in mergeSort() or pointerSort() functions.

    This is their code (new fix), but still freeing of memory does not working.
    Code:
    int** pointerSort(int* arr, int size){
    	int** outA;
    	int i;
    	outA=(int**)malloc(size*sizeof(int*));
    	for (i=0; i<size; i++)
    	{
    		outA[i]=(int*)malloc(sizeof(int));
    		if (outA[i]==NULL)
    		{
    			freeArray(outA,i);
    			return NULL;
    		}
    	}
    	if (outA!=NULL)
    	{
    		for (i=0; i<size; i++)
    			outA[i]=&arr[i];	
    		mergeSort(outA,size);
    	}
    	else
    		return NULL;
    
    	return outA;
    }
    
    void mergeSort(int** arr, int size)
    {
    	int** res;
    	int numRes, i;
    
    	if (size==1)
    	{			
    		return;
    	}
    	else
    	{
    		mergeSort(arr, size/2);
    		mergeSort(arr+size/2, size-size/2);
    		res=(int**)malloc(size*sizeof(int*));
    		for (i=0; i<size; i++)
    		{
    			res[i]=(int*)malloc(sizeof(int));
    			if (res[i]==NULL)			
    			{
    				freeArray(res,i);
    				return;
    			}
    		}
    		if (res!=NULL)
    		{
    			merge(arr, size/2, arr+size/2, size-size/2, res, &numRes);		
    			copyPtrsArray(arr, res, size);
    			freeArray(res,numRes);
    		}
    		else
    		{
    			printf("\n failure in sorting \n");
    			return;
    		}
    	}	
    }
    As you can see, now I am using malloc for each of the pointers in the sorted array.
    I don't know wheter I should take care of freeing of memory, 'cause if not, everything works fine... (just kidding, I know I have to free all of my pointers)
    Last edited by lionheart; 07-31-2008 at 10:55 PM. Reason: I've got no answer yet

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    This is wrong:
    Code:
    	for (i=0; i<size; i++)
    		free((void*)a1[i]);
    You must free what you malloc/calloc, and ONLY what you malloc/calloc. You did not allocate lots of individual pointers so it is wrong to have this loop at all. Simply delete the two lines I've quoted and it should work fine. You will also not need a freeArray function.
    Your first post was closer to correct.

    Additionally, you are using malloc a lot more than you need to. A better solution would be to allocate two arrays of 'size' many pointers only once for the entire sort, and just merge between the various arrays:

    You also should not be casting your mallocs, read about this in the FAQ.
    Last edited by iMalc; 08-01-2008 at 12:24 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jun 2008
    Posts
    23
    But a1 is an array of pointers, so why shouldn't I free all of a1's pointers?

    There's logic in freeing all of the pointers that point to values in arr...

    (And about the casting, it is a matter of style)

  13. #13
    Registered User
    Join Date
    Jun 2008
    Posts
    23
    Now I get it, if I free the original array then all of the pointers that point to values in it are free too.
    Thanks, rasta_freak and thanks to this forum, I knew I could count on you...

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by lionheart View Post
    (And about the casting, it is a matter of style)
    Yes, that may be true - however, the consequence of your style choice here means that you could hide subtle and annoying bugs. For example, C allows you to use a function without a prototype. On some processors (e.g. 68K), the default return register for a pointer is different from the return register for a integral type. If you do no have malloc() declared as returning a pointer, your cast will let the compiler compile the code without error, but you will get the value from the integer result, as the default for return values is integer, not pointer. When you run that code, it will most likely crash immediately. But if you are really unlucky, the return value is "close enough" to work, and only later one will the application crash, because you overwrote some important data that malloc uses.

    So whilst it's a matter of style, it has consequences as to the ability to find potential problems in the code.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Registered User
    Join Date
    Jun 2008
    Posts
    23
    Thanks for the info, Mats, but this is really over my league. All I know is that someone asked me to cast just like that, and I'm doing it.
    I'm studying for my BSc now, and I know about the C++ way of using pointers (new, delete and etc.)... I'm only now learning the advanced programming of C, and I see how f***** up that is, and probably we will learn other issues in the future.

    Thanks for the reply...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Returning an Array of Pointers to Objects
    By randomalias in forum C++ Programming
    Replies: 4
    Last Post: 04-29-2006, 02:45 PM
  2. two-dimensional dynamic array of pointers to classes
    By Timo002 in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 06:18 AM
  3. Passing pointers between functions
    By heygirls_uk in forum C Programming
    Replies: 5
    Last Post: 01-09-2004, 06:58 PM
  4. array of pointers to struct array
    By eth0 in forum C++ Programming
    Replies: 1
    Last Post: 01-08-2004, 06:43 PM
  5. array of pointers to structs
    By stumon in forum C Programming
    Replies: 7
    Last Post: 03-24-2003, 07:13 AM