I am attempting to write merge sort in c. I am having trouble getting the pointers working correctly when passing them to Merge and copying them. My array is getting corrupted with garbage data.
void Merge(long long int **numbers, int low1, int high1, int low2, int high2, int count)
{
//int count = sizeof(*numbers)/sizeof(numbers[0]);
long long int *nums1;
nums1 = (long long int *)malloc(sizeof(long long int)*count);
long long int *nums2;
nums2 = (long long int *)malloc(sizeof(long long int)*count);
memcpy(nums1,numbers,count);
memcpy(nums2,numbers,count);
//nums1 = (long long int *)numbers;
//nums2 = (long long int *)numbers;
int i = 0, j = 0, k = 0;
while(i < high1-low1 && j < high2-low2)
{
//comparison
if(nums1[i] <= nums2[j])
{
numbers[k] = &(nums1[i]); i++;
}
else
{
numbers[k] = &(nums2[j]); j++;
}
k++;
}
while(i < high1-low1)
{
numbers[k] = &(nums1[i]);
i++;
k++;
}
while(j < high2-low2)
{
numbers[k] = &(nums2[j]);
j++;
k++;
}
return;
}
/*
DESCRIPTION:
Sorts the array using the merge sort algorithm
INPUT:
numbers - unsorted list of numbers
low - starting index
high - ending index
Output:
sorted array
*/
void Mergesort(long long int *numbers, int low, int high, int count)
{
int low1, low2, high1, high2;
if(high-low > 1)
{
low1 = low;
high1 = (high-low)/2 +low;
low2 = high1;
high2= high;
Mergesort(numbers, low1, high1, count);
Mergesort(numbers, low2, high2, count);
Merge(numbers,low1, high1, low2, high2, count);
}
return;
}
/*
DESCRIPTION:
Determines whether all of the elements in a list are distinct.
The list is first sorted (in place) and then elements that are
side by side are compared to determine if they are unique.
INPUT:
numbers - unsorted list of numbers
count - the size of the numbers array
operations - pointer to in which to store the number of operations
Output:
TRUE if every element in numbers is unique, otherwise FALSE
*/
int unique3(long long int *numbers, int count, long long int *operations) {
long long int basic_operations = 0;
//sort array
int i;
for(i = 0; i < count; i++)
{
printf("%d ", numbers[i]);
printf("\n");
}
Mergesort(numbers, 0, count-1, count);
printf("\n\n\n Here \n\n\n");
for(i = 0; i < count; i++)
{
printf("%d ", numbers[i]);
printf("\n");
}
//int i;
for(i=0;i < count; i++)
{
basic_operations++;
if (numbers[i] == numbers[i+1])
return FALSE;
}
*operations = basic_operations;
return TRUE;
}
/*
DESCRIPTION:
This function reads a list of integers from a file and stores
them in an array as long long ints. The array and its size are
stored in pointers passed as arguments. Upon failure, a value
-1 is stored in address pointed to by return_size.
INPUT:
file_name - file to read values from
return_numbers - pointer to an address where the numbers are stored
return_size - pointer to an integer to store the size of the array
Output:
void
*/
void read_array(char *file_name, long long int **return_numbers, int *return_size) {
FILE *file; // file pointer used to read in file_name
char *buffer = NULL; // string of characters, set initially to null
size_t buffer_len = 0; // used to determine the number of characters read in
ssize_t char_count; // store the number of characters read in
int count;
int ii;
long long int *numbers;
file = fopen(file_name, "r"); // open the file for reading
if (file == NULL) {
// error opening the file, print error message
perror(file_name);
// set pointers to show failed state
*return_numbers = NULL;
*return_size = -1;
return;
}
// read in the first line to determine how many numbers are in the list
if ((char_count = getline(&buffer, &buffer_len, file)) == -1) {
// error openting the file, print error message
perror("error getting count");
fclose(file);
// set pointers to show failed state
*return_numbers = NULL;
*return_size = -1;
return;
}
// use atoi to convert the string to a number
count = atoi(buffer);
// dynamically allocate an array to contain count number of long long ints
numbers = (long long int *)malloc(sizeof(long long int)*count);
// read in count numbers
for(ii=0; ii < count; ii++) {
// read in a number delimited by a comma
if ((char_count = getdelim(&buffer, &buffer_len, (int)',', file)) == -1) {
// if char_count == -1, there was an error reading
perror("error reading entry");
free(buffer);
free(numbers);
fclose(file);
// set pointers to show failed state
*return_numbers = NULL;
*return_size = -1;
return;
}
// remove the comma from the end of the string
buffer[char_count-1] = '\0';
// convert the string to a long long int
numbers[ii] = atoll(buffer);
}
// free up the buffer and close the file
free(buffer);
fclose(file);
// set up pointer values
*return_numbers = numbers;
*return_size = count;
}
void timing(long long int *numbers, int count, int (*algorithm)(long long int *, int, long long int *), long long int *operations, int *unique, long int *ms_time) {
struct timeval start_tv;
struct timeval end_tv;
gettimeofday(&start_tv, NULL);
*unique = algorithm(numbers, count, operations);
gettimeofday(&end_tv, NULL);
*ms_time = (end_tv.tv_sec - start_tv.tv_sec)*1000000L + (end_tv.tv_usec - start_tv.tv_usec);
}
int main(int argc, char *argv[]) {
if(argc != 2) {
printf("Invalid Number of Arguments\n");
printf("Usage:\n");
printf("%s <file_name>\n", argv[0]);
printf("\tfile_name - name of the input file\n");
printf("It is assumed that the first line of the input file contains\n");
printf("the count of the numbers in the file. The second line is assume\n");
printf("to be a comma separated list of integers.\n");
}
else {
int count;
long long int *numbers;
long long int operations;
int is_unique;
long int ms_time;
read_array(argv[1], &numbers, &count);
if(count >= 0){
printf("%d ", count);
timing(numbers, count, unique1, &operations, &is_unique, &ms_time);
printf("(%d,%lld,%ld) ", is_unique, operations, ms_time);
timing(numbers, count, unique2, &operations, &is_unique, &ms_time);
printf("(%d,%lld,%ld) ", is_unique, operations, ms_time);
timing(numbers, count, unique3, &operations, &is_unique, &ms_time);
printf("(%d,%lld,%ld)\n", is_unique, operations, ms_time);
}
}
return 0;
}
Here is my array before and after calling the function.
Before 10 9 8 7 6 5 4 1 2 0
After
37668400 37668408 37668416 37668424 37668496 37668504 37668512 37668520 37668528 0
Note: the code outside of the merge, mergesort and unique3 are all a skeleton given to our class***
