mergesort array of int using pointers

Question

For school I have to program a merge sort using only pointers. I've tried almost everything, but I can not get it working.

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

#define num_elementi(array) (sizeof(array)/sizeof(array[0]))

void selsort(int arr[],int n);
void swap(int * a, int * b);
void print(int arr[],int n);
void insort(int arr[],int n);
void mergesort(int arr[],int *p,int *u);
void merge(int arr[],int * p, int * q,int * u);

int main(int argc, char *argv[]){
    int arr[]={99,12,14,65,2,7,54,78,5,1,43,59,88,28,61};
    int n=num_elementi(arr);
    printf("numero elementi array: %d\n",n);
    print(arr,n);
    printf("numero elementi array: %d\n",n);    
    mergesort(arr,&arr[0],&arr[n-1]);
    print(arr,n);
    system("pause");
}

void selsort(int arr[],int n){
    int *i,*j;
    for(i=arr;i<&arr[n-1];i++){
        for(j=i+1;j<&arr[n];j++){
            if(*j<*i)swap(i,j);;
        }

    }
}

void swap(int * a, int * b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void print(int arr[],int n){
    int * p=arr;
    for(p;p<&arr[n];p++)printf("%d ",*p);
    printf("\n");
}

void insort(int arr[],int n){
    int *i,*k;
    for(i=&arr[1];i<&arr[n];i++){
        k=i-1;
        while(k>=&arr[0]&& *k>*(k+1)){
            swap(k,k+1);
            k=k-1;
        }
    }
}


void mergesort(int arr[],int *p,int *u){
    if (p<u){
        int *q=((u-p)/2)+p;
        mergesort(arr,p,q);
        mergesort(arr,q,u-1);
        merge(arr,p,q,u);
    }

}

void merge(int arr[],int * p, int * q,int * u){
    int arr1[u-p]; //inizializzazione array di dimensioni utili
    int * i=p; //puntatore al primo elemento di arr
    int *j=q+1; //puntatore al elemento di mezzo +1 di arr
    int *k= arr1; //puntatore al primo elemento di arr1
    if (u-p==1){ 
        if (*u<*p){
            swap(u,p);
        }
        return;
    }
    while(i<q && j<u){
        if(*i<*j){ 
            *k=*i;
            i=i+1;
        }
        else{
            *k=*j;
            j=j+1;
        }
        k=k+1;
    }
    while(i<q){*k=*i;i++;k++;}
    while(j<u){*k=*j;j++;k++;}

    i=p;
    k=arr1;
    for(i,k;i<&arr[u-p];i++,k++){
        *i=*k;
    }
}

Can someone please explain what I did wrong? Thank you so much!!

PS: Please forgive my really bad English.

EDIT new code for the suggestion of Maciej Hehl

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

#define num_elementi(array) (sizeof(array)/sizeof(array[0]))

void swap(int * a, int * b);
void print(int arr[],int n);
void mergesort(int arr[],int * arr_begin,int * arr_end);
void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end);

int main(int argc, char *argv[]){
    int arr[]={99,12,14,65,2,7,54,78,5,1,43,59,88,28,61};
    int n=num_elementi(arr);
    print(arr,n);  
    mergesort(arr,&arr[0],&arr[n-1]);
    print(arr,n);
    system("pause");
}

void swap(int * a, int * b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void print(int arr[],int n){
    int * p=arr;
    for(p;p<&arr[n];p++)printf("%d ",*p);
    printf("\n");
}

void mergesort(int arr[],int * arr_begin,int * arr_end){
    int * med,*arr1,*p,*p1;
    printf("i'm doing something\n");
    if(arr_begin<arr_end){
        med=arr[arr_end-arr_begin]/2+arr_begin;
        mergesort(arr,arr_begin,med);
        mergesort(arr,med+1,arr_end);
        arr1=malloc((arr_end-arr_begin)*sizeof(int));
        printf("msort calls ended begin merge\n");
        merge(arr1,arr_begin,med,med+1,arr_end);
        for(p=arr,p1=arr1;p<arr_end&&p1<&arr1[arr_end-arr_begin];p++,p1++){
            *p=*p1;
        }
    }

}

void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end){
    int *pdest=destination;
    if (r1_end-r1_begin==1){ 
        if (*r1_end<*r1_begin){
            swap(r1_end,r1_begin);
        }
        return;
    }
    if (r2_end-r2_begin==1){ 
        if (*r2_end<*r2_begin){
            swap(r2_end,r2_begin);
        }
        return;
    }
    while(r1_begin<=r1_end&&r2_begin<=r2_end){
        if(*r1_begin<*r2_begin){
            *pdest=*r1_begin;
            r1_begin++;
        }
        else{
            *pdest=*r2_begin;
            r2_begin++;
        }
        pdest++;
    }
    while(r1_begin<r1_end){
        *pdest=*r1_begin;
        r1_begin++;pdest++;        
    }
    while(r2_begin<r2_end){
        *pdest=*r2_begin;
        r2_begin++;pdest++;
    }

}

Can you tell us what isn't working? Does it not compile or what output do you get? — Lucas
– Lucas, Commented Jul 6, 2010 at 15:18
it is compiled correctly but it seems to don't sort correctly.. — tommaso capelli
– tommaso capelli, Commented Jul 7, 2010 at 17:30

Maciej Hehl · Accepted Answer · 2010-07-07 18:36:03Z

EDIT

Your edits made my original answer (below) nonsensical to other readers :) Oh, well...

First thing is to decide if Your begin and end pointers define a range [begin, end) or [begin, end]. I suggest the first choice because it is used in C++ library. If You agree with that, the call

mergesort(arr,&arr[0],&arr[n]);

is correct. You have to change &arr[n] to &arr[n-1] only if You decide, You want the pointers begin and end to define the range [begin, end] which I suggest not to do.

In fact the pointers begin and end are enough to sort the range and Your mergesort function doesn't need the first parameter.

The calculation of med is incorrect

med=arr[arr_end-arr_begin]/2+arr_begin;

It was correct in the previous version (the variable was named q)

The calls below are also incorrect

mergesort(arr,arr_begin,med);
mergesort(arr,med+1,arr_end);

First call is supposed to sort the range [arr_begin, med) , not [arr_begin, med] (*med doesn't belong to that range), so the second call should sort the range starting at med.

The allocation of arr1 is correct, thanks to the fact, that the difference end - begin is equal to the number of elements. That's the advantage of picking the range [begin, end) instead of [begin, end]. It would be nice however, if You freed the allocated memory after use.

The call to merge is incorrect, like the calls to mergesort above. The second range sholuld start at med because med points past the first range, not at it's last element.

The implementation of merge is overcomplicated. You don't have to swap anything. You just take elements from both ranges and copy them to the destination. Those three while loops that started my original post (below) are enough, but pay attention to the conditions.

I repeat once again med points past the first range and arr_end points past the second range. Taking it into consideration, should You use <= or < operators?

I don't like the inconsistency in the conditions i<=q, j<=u, i<q, j<u in the following code:

while(i<=q && j<=u){
    if(*i<*j){ 
        *k=*i;
        i=i+1;
    }
    else{
        *k=*j;
        j=j+1;
    }
    k=k+1;
}
while(i<q){*k=*i;i++;k++;}
while(j<u){*k=*j;j++;k++;}

You call Your mergesort like this:

mergesort(arr,&arr[0],&arr[n]);

which means, that u is a pointer, that points to the spot after the last element of Your array. In other words, You seem to think of Your pointers, like of iterators begin and end which define the range [begin, end) - *begin belongs to the range, but *end not,

In the definition of mergesort You write

int *q=((u-p)/2)+p;
mergesort(arr,p,q);
mergesort(arr,q+1,u);

which is inconsistent with the assumptions above. q may be equal p if u == p+1.

mergesort(arr,p,q); means sort the range [p, q) (q is past the range) mergesort(arr,q+1,u); means sort the range [q+1, u) (u is past the range)

If You were consistent in Your representation of a range with pointers, You would never touch the element *q this way.

Thinking of the range as [begin, end) instead of [begin, end] (in the second case *end is part of the range) is consistent with the way iterators are used in C++, but it's not obligatory. You can use pointers to define the range also the second way, but in that case, You have to change the call mergesort(arr,&arr[0],&arr[n]); to mergesort(arr,&arr[0],&arr[n-1]);. In both cases You have to rethink conditions in the code cited at the beginning.

This is a homework, so I won't solve it for You, but here is a little hint, that might help thinking about it. Redefine Your merge so it takes 2 ranges, to merge, explicitly:

void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end);

and think how to use it. Later You can simplify things. You don't really need destination parameter, and You don't have to copy all merged elements. You can copy only one range first and then, merge directly into destination, taking elements from the copy of the first range and from the second range.

Thank you so much for the answer! I did what you suggested me to do, but i think i did the same error as before! I've updated the code. Can you tell me why it work in this strange way? It seems doing nothing because it doesn't print anything, but in fact it sorts something, i don't really know how's possible!! I'm getting mad with this exercize, i've done all the exercizes about pointers the teacher gave me but i can't finish this one!

rturrado · Accepted Answer · 2010-07-06 18:22:10Z

1

At main, if you add a printf("*** n=%d\n", n) before each call to print, you will notice that, before the second call, the output is n=61. That is, you are sorting the array well, but by the time you print it a second time, you print 61 numbers.
You can notice as well that 61 is the biggest number in the array, and that n is defined just after arr, so n and arr will be in consecutive memory addresses in the stack. I think n is being overwritten during the mergesoft function call.
Effectively, the overwritting happens when you call mergesoft with &arr[n]. The last element of the array has the index n-1. The nth index actually corresponds to the n variable. Change the call to: mergesort(arr,&arr[0],&arr[n-1]);

edited Jul 6, 2010 at 18:22

answered Jul 6, 2010 at 18:06

rturrado

8,2097 gold badges44 silver badges65 bronze badges

2 Comments

rturrado Over a year ago

You should protect this call with a check for empty array, such as: if (n > 0) { mergesort(arr, &arr[0], &arr[n-1]); }

tommaso capelli Over a year ago

Thank you for the answer!!! i did what you and Maciej Hehl suggested me to do, but i think i did the same error as before! I've updated the code. Can you tell me why it work in this strange way? It seems doing nothing because it doesn't print anything, but in fact it sorts something, i don't really know how's possible!! I'm getting mad with this exercize, i've done all the exercizes about pointers the teacher gave me but i can't finish this one!

Collectives™ on Stack Overflow

mergesort array of int using pointers

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related