Jump to content

  • Log In with Google      Sign In   
  • Create Account

Merge Sort


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 Prof G   Members   -  Reputation: 129

Like
0Likes
Like

Posted 24 October 2012 - 12:56 PM

I'm not new to programming, but new to the C language. I'm using it as my vehicle for exploring different classic algorithms and I'm a bit stumped when it comes to this particular divide-and-conquer algorithm known as Merge Sort. I understand conceptually how it is supposed to work, but when actually implementing it in a programming language, my code below is causing my program to crash.

Any help or feedback would be appreciated! Oh and no, this isn't a homework assignment Posted Image Please find the code below...

Edited by cnewbie, 24 October 2012 - 12:58 PM.

Done > Perfect

Sponsor:

#2 Prof G   Members   -  Reputation: 129

Like
0Likes
Like

Posted 24 October 2012 - 12:58 PM


#include <stdlib.h>

#include <stdio.h>

#include <time.h>



const int ARRAY_SIZE = 11;

void merge_sort(int a[], int l, int r);

void merge(int a[], int i, int j, int k, int size);

void print_array(int* a[]);

int main(){

    int a[] = {10,9,8,7,6,5,4,3,2,1,0};

    printf("AFTER SORT\n");

    clock_t begin, end;

    double time_spent;

    begin = clock();

    merge_sort(a,0,ARRAY_SIZE);

    end = clock();

    time_spent = (float)(end - begin)/ CLOCKS_PER_SEC;

    printf("TOOK: %f TO SORT", time_spent);

    getchar();

}

void merge_sort(int a[], int l, int r)

{

    int mid;

    if(r <= l)

	    return;

    mid = (r+l-1)/2;

    merge_sort(a, l, mid);

    merge_sort(a, mid+1, r);

    merge(a, l, mid, r, r-l+1);

}

void merge(int a[], int i, int j, int k, int size)

{

    int ipos = i;

    int jpos = j+1;

    int mpos = 0;

    int m[size];

    while(ipos <= j || jpos <= k){

	    if(ipos <= j && jpos <= k){

		    if(a[ipos] <= a[jpos]){

			    m[mpos] = a[ipos];

			    mpos++;

			    ipos++;

		    }else if(a[jpos] <= a[ipos]){

			    m[mpos] = a[jpos];

			    mpos++;

			    jpos++;

		    }

	    }else if(ipos > j){

		    while(jpos <= k){

			    m[mpos] = a[jpos];

			    mpos++;

			    jpos++;

		    }

	    }else if(jpos > k){

		    while(ipos < j){

			    m[mpos] = a[ipos];

			    mpos++;

			    ipos++;

		    }

	    }

    }

    return m;

}

void print_array(int* a[]){

    int i = 0;

    for(i = 0; i < ARRAY_SIZE; i++)

	    printf("%d: %d\n", i+1, a[i]);

}


Done > Perfect

#3 rip-off   Moderators   -  Reputation: 8745

Like
0Likes
Like

Posted 24 October 2012 - 02:14 PM

Your crash is almost certainly caused by out-of-bounds access. One way to start is using a debugger, another is to add assertions.

I find it hard to follow your code because of the poor variable names. Are you sure you need all those variables and parameters for the "merge" function?

#4 fastcall22   Crossbones+   -  Reputation: 4463

Like
1Likes
Like

Posted 24 October 2012 - 02:15 PM

You cannot return m in merge because merge is defined not to return a value and m is an array on the stack. As soon as merge returns, the memory that contained the array for m is destroyed/trashed/undefined/etc. You will either need to use dynamic memory allocation (malloc and free) to create and return the array m, or use the in-place flavor of merge sort.

Also, watch your ipos and jpos carefully, as a[jpos] is an invalid element when jpos == k == ARRAY_SIZE.

Edited by fastcall22, 24 October 2012 - 02:17 PM.

c3RhdGljIGNoYXIgeW91cl9tb21bMVVMTCA8PCA2NF07CnNwcmludGYoeW91cl9tb20sICJpcyBmYXQiKTs=




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS