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 Please find the code below...
Merge Sort
#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);
}
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?
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?
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.
Also, watch your ipos and jpos carefully, as a[jpos] is an invalid element when jpos == k == ARRAY_SIZE.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement