R
rkk
Hi,
My mergesort program is below. There is a small piece of logical
error/bug in this code which I can't figure out, as a result the output
array isn't completely sorted. Requesting your help to resolve this
problem. Thanks in advance.
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
typedef int (*CompareFunc)(const void*,const void*);
void MergeSort(void *array[],int left,int right,CompareFunc compare);
void Merge(void *array[],int left,int mid,int right,CompareFunc
compare);
int IntCompare(const void *a,const void *b);
int StrCompare(const void *a,const void *b);
void MergeSort(void *array[],int left,int right,CompareFunc compare)
{
int mid;
if ( left >= right ) return;
mid = (left + right)/2;
MergeSort(array,left,mid,compare);
MergeSort(array,mid + 1,right,compare);
Merge(array,left,mid,right,compare);
}
void Merge(void *array[],int left,int mid,int right,CompareFunc
compare)
{
int numElements = right - left + 1;
void **aux;
int lowerBound = left,upperBound = mid + 1,index = 0;
aux = malloc(numElements * sizeof &array[0]);
if(aux == NULL) {
fprintf(stderr,"Merge: %s\n","malloc failed");
return;
}
while ( lowerBound <= mid && upperBound <= right )
{
if(compare(&array[lowerBound],&array[upperBound]) < 0) {
aux[index++] = array[lowerBound++];
} else {
aux[index++] = array[upperBound++];
}
}
while ( lowerBound <= mid ) aux[index++] = array[lowerBound++];
while ( upperBound <= right) aux[index++] = array[upperBound++];
for(index = left ; index < numElements; index++)
array[index] = aux[index];
free(aux);
}
int IntCompare(const void *a,const void *b)
{
const int *ia = (const int*) a;
const int *ib = (const int*) b;
return ( (*ia > *ib) - (*ia < *ib) );
}
int StrCompare(const void *a,const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}
int main()
{
int i;
int iArray[] = {6,3,2,1,4,5,7,9,10,11,13,12,8,14};
int sizeOfArray = sizeof iArray/sizeof iArray[0];
MergeSort((void **)iArray,0,(sizeOfArray-1),IntCompare);
for(i=0; i < sizeOfArray; i++)
printf("%d ", iArray );
printf("\n");
return 0;
}
Here is how I compile:
$ gcc -g -o mergesort mergesort.c
Here is the output:
$ ./mergesort
2 1 3 4 5 6 7 9 10 11 13 12 8 14
Clearly the output isn't completely sorted. Kindly help.
Regards
Kalyan
My mergesort program is below. There is a small piece of logical
error/bug in this code which I can't figure out, as a result the output
array isn't completely sorted. Requesting your help to resolve this
problem. Thanks in advance.
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
typedef int (*CompareFunc)(const void*,const void*);
void MergeSort(void *array[],int left,int right,CompareFunc compare);
void Merge(void *array[],int left,int mid,int right,CompareFunc
compare);
int IntCompare(const void *a,const void *b);
int StrCompare(const void *a,const void *b);
void MergeSort(void *array[],int left,int right,CompareFunc compare)
{
int mid;
if ( left >= right ) return;
mid = (left + right)/2;
MergeSort(array,left,mid,compare);
MergeSort(array,mid + 1,right,compare);
Merge(array,left,mid,right,compare);
}
void Merge(void *array[],int left,int mid,int right,CompareFunc
compare)
{
int numElements = right - left + 1;
void **aux;
int lowerBound = left,upperBound = mid + 1,index = 0;
aux = malloc(numElements * sizeof &array[0]);
if(aux == NULL) {
fprintf(stderr,"Merge: %s\n","malloc failed");
return;
}
while ( lowerBound <= mid && upperBound <= right )
{
if(compare(&array[lowerBound],&array[upperBound]) < 0) {
aux[index++] = array[lowerBound++];
} else {
aux[index++] = array[upperBound++];
}
}
while ( lowerBound <= mid ) aux[index++] = array[lowerBound++];
while ( upperBound <= right) aux[index++] = array[upperBound++];
for(index = left ; index < numElements; index++)
array[index] = aux[index];
free(aux);
}
int IntCompare(const void *a,const void *b)
{
const int *ia = (const int*) a;
const int *ib = (const int*) b;
return ( (*ia > *ib) - (*ia < *ib) );
}
int StrCompare(const void *a,const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}
int main()
{
int i;
int iArray[] = {6,3,2,1,4,5,7,9,10,11,13,12,8,14};
int sizeOfArray = sizeof iArray/sizeof iArray[0];
MergeSort((void **)iArray,0,(sizeOfArray-1),IntCompare);
for(i=0; i < sizeOfArray; i++)
printf("%d ", iArray );
printf("\n");
return 0;
}
Here is how I compile:
$ gcc -g -o mergesort mergesort.c
Here is the output:
$ ./mergesort
2 1 3 4 5 6 7 9 10 11 13 12 8 14
Clearly the output isn't completely sorted. Kindly help.
Regards
Kalyan