Hi,
I am trying to implement a bottom-up merge sort using void pointers, but I am having some problems.
I am using visual studio to compile it and it gives an error that requires me to break the execution.
I am new using void pointers, so I am positive that could be the problem, I'd appreciate if anyone can help me fix it.
Thanks in advance.
Here's my code.
#include <iostream>
#include <conio.h>
using namespace std;
const int MAX_SIZE = 10;
int compare(const void *,const void *);
void merge(void *,int , int , int, int,int (*compare) (const void * , const void *));
void mergesort(void *, int , int , int (*compare) (const void * , const void *));
int main()
{
int arr[6] = {3,4,0,2,6,10};
cout << "Unsorted Array" << endl;
for(int i=0; i<6; i++)
{
cout << arr[i] << " ";
}
mergesort(&arr,6,sizeof(int),compare);
cout << endl << "Sorted Array" << endl;
for(int i=0; i<6; i++)
{
cout << arr[i] << " ";
}
getch();
return 0;
}
int compare(const void *x,const void *y)
{
return(* ((int*)x)-*((int *)y));
}
void merge(void *keys,int first, int mid, int last, int size, int (*compare) (const void * , const void *))
{
char *tempArray;
char *akeys;
akeys= (char *) keys;
tempArray = (char *) malloc(sizeof(char)*MAX_SIZE); // temporary array
// initialize the local indexes to indicate the subarrays
int first1 = first; // beginning of first subarray
int last1 = mid; // end of first subarray
int first2 = mid + 1; // beginning of second subarray
int last2 = last; // end of second subarray
// while both subarrays are not empty, copy the
// smaller item into the temporary array
int index = first1; // next available location in
// tempArray
for (; (first1 <= last1) && (first2 <= last2); ++index)
{ // Invariant: tempArray[first..index-1] is in order
if (compare(&akeys[first1*size],&akeys[first2*size]) < 0)
{
memcpy(&tempArray[index*size],&akeys[first1*size],size);
++first1;
}
else
{ memcpy(&tempArray[index*size],&akeys[first2*size],size);
++first2;
} // end if
} // end for
// finish off the nonempty subarray
// finish off the first subarray, if necessary
for (; first1 <= last1; ++first1, ++index)
// Invariant: tempArray[first..index-1] is in order
memcpy(&tempArray[index*size],&akeys[first1*size],size);
// finish off the second subarray, if necessary
for (; first2 <= last2; ++first2, ++index)
// Invariant: tempArray[first..index-1] is in order
memcpy(&tempArray[index*size],&akeys[first2*size],size);
// copy the result back into the original array
for (index = first; index <= last; ++index)
memcpy(&akeys[index*size],&tempArray[index*size],size);
} // end merge
void mergesort(void *keys, int n, int size, int (*compare) (const void * , const void *))
{
//#define min(A, B) (A < B) ? A : B
int i, m;
int l = 0; //first index
int r = n-1; //last index
for (m = 1; m < r-l; m = m+m)
{
for (i = l; i <= r-m; i += m+m)
{
int qv=i+m+m-1;
if(compare(&qv,&r) < 0)
{
merge(&keys, i, i+m-1,i+m+m-1,size,compare);
}
else
{
merge(&keys, i, i+m-1,r,size,compare);
}
}
}
} // end mergesort