It looks like you may have two bugs here:
for(j = 0; j < sizeRight; j++) {
right[i] = t[beg+j];
This should probably be:
for(j = 0; j < sizeRight; j++) {
right[j] = t[med+j];
^^^ ^^^
题
Hey everyone so my MergeSort algorithm isn't perfect, it's actually the same one that was posted here in a similar question, but that's not even the real problem. Basically the user inputs an array size, and lower & upper bounds on a range of values to be put into an array of doubles to be mergeSorted.
I can print out the array just fine but after MergeSort it returns whack negative values that I assume are addresses.
I know this has something to do with memory but I have no idea why it's messing up because I believe I allocated memory and cleared it correctly. Here is my code, any insight will be much appreciated especially before 12:00 tonight ;).
Here is main.c, mergesort.c, and mergesort.h. I am also using a makefile but I don't think that is necessary to share.
Main.c:
#include <stdlib.h>
#include <stdio.h>
#include "mergesort.h"
int lower = 0;
int upper = 0;
int n = 0;
int main(int argc,char* argv[]) {
int i = 0; // loop values
int j = 0;
int r = 0; // random number
/*int n = 0; // size of array
int lower = 0; // lower bound on values in array
int upper = 0; // upper ...*/
double *t; //array of doubles
printf("Size of array?\n");
scanf("%d", &n);
printf("Lower Bound?\n");
scanf("%d", &lower);
//globLower = lower;
printf("Upper Bound?\n");
scanf("%d", &upper);
//globUpper = upper;
t = malloc(n * sizeof *t); // allocates n slots of memory
printf("Unsorted Array:\n");
for(i=0; i<n; i++) {
r = lower + arc4random() % (upper - lower);
//printf("%d\n", r);
t[i] = r; // fills array with random values in range
printf("%g\n", t[i]);
}
printf("Before Merge Sort\n");
mergeSort(t,n); // This is supposed to sort the array...
printf("After Merge Sort\n");
i = 0; //reset
// printf("%g\n", t[0]);
printf("%g\n", t[1]);
printf("%g\n", t[2]);
free(t); // Need to free the memory allocated since is stored in the heap
return 0;
}
mergesort.c:
#include <stdlib.h>
#include <stdio.h>
#include "mergesort.h"
void mergeSort(double* t, int n) {
printf("Size: %d\n", n);
printf("Lower: %d\n", lower); // tests
printf("Upper: %d\n", upper);
printf("t[2]: %g\n", t[2]);
int beg = 0;
int end = n-1;
mergeSortHelp(t, beg, end);
}
void mergeSortHelp(double* t, int beg, int end) {
int mid = (end + beg) / 2;
if(beg < end) {
mergeSortHelp(t, beg, mid);
mergeSortHelp(t, mid+1, end);
merge(t, beg, mid, end);
}
}
void merge(double* t, int beg, int mid, int end) {
int sizeLeft = mid - beg + 1;
int sizeRight = end - mid;
double *left = malloc((sizeLeft)*sizeof(double));
double *right = malloc((sizeRight)*sizeof(double));
int i,j,k;
for(i = 0; i < sizeLeft; i++) {
left[i] = t[beg+i];
}
for(j = 0; j < sizeRight; j++) {
right[i] = t[beg+j];
}
i = 0;
j = 0;
for(k = beg; k <= end; k++) {
t[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
free(left);
free(right);
return;
}
and the header mergesort.h
extern int lower;
extern int upper;
extern int n;
Thanks!
解决方案
It looks like you may have two bugs here:
for(j = 0; j < sizeRight; j++) {
right[i] = t[beg+j];
This should probably be:
for(j = 0; j < sizeRight; j++) {
right[j] = t[med+j];
^^^ ^^^