Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Merge Sort in C - array output is same as input after sort routine completes

Reply
Thread Tools

Merge Sort in C - array output is same as input after sort routine completes

 
 
rkk
Guest
Posts: n/a
 
      09-22-2006
Hi,

I have written a generic mergesort program which is as below:
---------------------------------------------------------
mergesort.h
-----------------------

void
MergeSort(void *array[],int p,int r,int elemSize,int(*Compare)(const
void *keyA,const void *keyB));
void
Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
void *keyA,const void *keyB));
int
IntegerComp(const void *keyA,const void *keyB);

mergesort.c
--------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mergesort.h"


void
MergeSort(void *array[],int p,int r,int elemSize,int(*Compare)(const
void *keyA,const void *keyB))
{
int q;
if(p < r) {
q = (p + r)/2;
MergeSort(array,p,q,elemSize,Compare);
MergeSort(array,q + 1,r,elemSize,Compare);
Merge(array,p,q,r,elemSize,Compare);
}
}

void
Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
void *keyA,const void *keyB))
{
void **out = (void **)malloc(elemSize * r);
int i,k,j;
i = k = p;
j = q + 1;
while( i <= q && j <= r ) {
if( Compare( &array[i * elemSize],&array[j * elemSize] ) <= 0 ) {
out[k++] = array[i++];
} else {
out[k++] = array[j++];
}
}
while( i <= q ) out[k++] = array[i++];
while( j <= r ) out[k++] = array[j++];

for (i = p;i < r; i++) {
array[i] = out[i];
}
free(out);
}


int
IntegerComp(const void *keyA,const void *keyB)
{
if( (const int *) keyA == (const int *) keyB ) return 0;
else if( (const int *) keyA < (const int *) keyB ) return -1;
else if( (const int *) keyA > (const int *) keyB ) return 1;
}
----------------------------------------------
And the driver program is here:
test.c
---------
#include <stdio.h>
#include "mergesort.h"

int
main()
{
int idx,length;
int arr[] = { 2,21,1,48,15,31,26 };
length = sizeof arr/sizeof &arr[0];

printf("Before sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");

MergeSort(&arr,0,length,sizeof(int),IntegerComp);

printf("After sorting array:\n");
for (idx = 0;idx < length;idx++)
{
printf("%d ",arr[idx]);
}
printf("\n");


return 0;
}
----------------------------------------------------------
I compile the programs above as:

gcc -g -o mergesort mergesort.c test.c

The output is little surprising as the array looks unsorted after sort
algorithm is completed. I am not understanding what's going wrong here,
kindly help me.:
kalyan@proteus> mergesort
Before sorting array:
2 21 1 48 15 31 26
After sorting array:
2 21 1 48 15 31 26

Thank you.

Regards
Kalyan

 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      09-22-2006
rkk said:

> Hi,
>
> I have written a generic mergesort program which is as below:


I took a long hard look at it, and got rid of many obvious bugs, which left
a not-so-obvious bug that I couldn't dislodge.

My best advice to you would be:

1) remove all casts - I guessed they were *all* wrong, and my guess was
correct
2) use void *, not void *[]
3) in Merge, use an unsigned char * to point at the base of the array
4) do your own pointer arithmetic properly (your code currently ignores the
problem of object sizes)
5) protect against malloc failure (returning, say, 0 if all went well and 1
if a memory allocation failure occurred)
6) write your comparison routine so that it doesn't need casts
7) choose better identifier names, names that reflect what the identifier
represents (e.g. you might want to use left, mid, and right, rather than p,
q, and r)

Once you have fixed all that up, you'll still have a bug. I couldn't find
that one, and wasn't heavily motivated to try. After applying all the
obvious fixes (see above), I got an output of

1 2 15 21 26 26 26

which is in some ways better and in some ways worse than your output.
Clearly, it has done some sorting - which is good! - but equally clearly it
has smeared one of the values across part of the array - which is not good.

So at least one bug remains. If you would like me to make my changes
available to you, just yell - but, as you can see, more work is required.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
 
Reply With Quote
 
 
 
 
BRG
Guest
Posts: n/a
 
      09-22-2006
Richard Heathfield wrote:

[snip]

> Once you have fixed all that up, you'll still have a bug. I couldn't find
> that one, and wasn't heavily motivated to try.


In addition to the issues you found, the convention on the end index for
an array partition seems suspect. In some places it appears that the
index for the last array element is being used while in other places it
seems that this top index refers to one element beyond the last element.

For example the line:

while( j <= r ) out[k++] = array[j++];

uses the array[r] element whereas the following line:

for (i = p; i < r; i++)

excludes this element.

It's quite possible that this is correct since I have not studied the
code in any detail. But it looks suspicious to me.

Brian Gladman
 
Reply With Quote
 
Michael Mair
Guest
Posts: n/a
 
      09-22-2006
rkk schrieb:
> Hi,
>
> I have written a generic mergesort program which is as below:
> ---------------------------------------------------------
> mergesort.h
> -----------------------
>
> void
> MergeSort(void *array[],int p,int r,int elemSize,int(*Compare)(const
> void *keyA,const void *keyB));
> void
> Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
> void *keyA,const void *keyB));
> int
> IntegerComp(const void *keyA,const void *keyB);
>
> mergesort.c
> --------------------
> #include <stdio.h>
> #include <string.h>
> #include <stdlib.h>
> #include "mergesort.h"
>
>
> void
> MergeSort(void *array[],int p,int r,int elemSize,int(*Compare)(const
> void *keyA,const void *keyB))


Note: If you have an array of void*, then elemSize == sizeof (void*).
You probably want either an array of generic pointers which you
sort (an "index array") or an array of elements which you sort directly.
I will go for the latter even though it is not very efficient for
large elemSize.

> {
> int q;
> if(p < r) {
> q = (p + r)/2;
> MergeSort(array,p,q,elemSize,Compare);
> MergeSort(array,q + 1,r,elemSize,Compare);


This suggests that p and r are valid indices.

> Merge(array,p,q,r,elemSize,Compare);
> }
> }
>
> void
> Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
> void *keyA,const void *keyB))


Same as above.

> {
> void **out = (void **)malloc(elemSize * r);


No check whether this was successful.
You do not allocate the size you need which is
elemSize * (r- p + 1)

Note: One of the primary advantages of merge sort is that
you do not have to keep everything in memory. Allocating
a temp array leads that ad absurdum -- if a temp array is
allowed, then we can implement something more efficient...

> int i,k,j;
> i = k = p;


If you allocate only as much as you need, then k should start at 0.

> j = q + 1;
> while( i <= q && j <= r ) {
> if( Compare( &array[i * elemSize],&array[j * elemSize] ) <= 0 ) {


You cannot calculate the address of the array members like this.
(unsigned char *)array + i * elemSize
is the correct way to do this.

> out[k++] = array[i++];
> } else {
> out[k++] = array[j++];
> }
> }
> while( i <= q ) out[k++] = array[i++];
> while( j <= r ) out[k++] = array[j++];
>
> for (i = p;i < r; i++) {
> array[i] = out[i];
> }
> free(out);
> }
>
>
> int
> IntegerComp(const void *keyA,const void *keyB)
> {
> if( (const int *) keyA == (const int *) keyB ) return 0;
> else if( (const int *) keyA < (const int *) keyB ) return -1;
> else if( (const int *) keyA > (const int *) keyB ) return 1;
> }
> ----------------------------------------------
> And the driver program is here:
> test.c
> ---------
> #include <stdio.h>
> #include "mergesort.h"
>
> int
> main()
> {
> int idx,length;
> int arr[] = { 2,21,1,48,15,31,26 };
> length = sizeof arr/sizeof &arr[0];


sizeof arr / sizeof arr[0]

>
> printf("Before sorting array:\n");
> for (idx = 0;idx < length;idx++)
> {
> printf("%d ",arr[idx]);
> }
> printf("\n");
>
> MergeSort(&arr,0,length,sizeof(int),IntegerComp);


You have to pass "length - 1". If you write sizeof arr[0],
then you are on the safe side even if the type of arr changes.
>
> printf("After sorting array:\n");
> for (idx = 0;idx < length;idx++)
> {
> printf("%d ",arr[idx]);
> }
> printf("\n");
>
>
> return 0;
> }
> ----------------------------------------------------------
> I compile the programs above as:
>
> gcc -g -o mergesort mergesort.c test.c


gcc -std=c89 -pedantic -Wall -O test.c mergesort.c -o test

My changed version gives you some debug output; for this,
you need -DMY_DEBUG on the command line.

,-- mergesort.h --
#ifndef H_MERGE_SORT_H
#define H_MERGE_SORT_H

typedef int (*TCompareFcn) (const void *, const void *);

int
MergeSort (void *array,
int startIndex,
int endIndex,
int elemSize,
TCompareFcn Compare);

int
IntegerComp (const void *keyA,
const void *keyB);

#endif

`----
,-- test.c --
#include <stdio.h>
#include "mergesort.h"

int
main (void)
{
int idx, length;
int arr[] = { 2,21,1,48,15,31,26 };
length = sizeof arr / sizeof arr[0];

puts("Before sorting array:");
for (idx = 0; idx < length; idx++)
{
printf(" %d", arr[idx]);
}
putchar('\n');

if (!MergeSort(arr, 0, length - 1, sizeof arr[0], IntegerComp))
fputs("Merging not successful\n", stderr);

puts("After sorting array:");
for (idx = 0; idx < length; idx++)
{
printf(" %d", arr[idx]);
}
putchar('\n');


return 0;
}

`----
,-- mergesort.c --
#include "mergesort.h"

#include <string.h>
#include <stdlib.h>

#ifdef MY_DEBUG
# include <stdio.h>
# define DEBUG_PRINT(s) printf s
# define DEBUG_I_PRINT(s) printf("%*s", indent, " "), DEBUG_PRINT(s)
static int indent = 0;
# define DEBUG_ENTER indent += 3
# define DEBUG_EXIT indent -= 3
#else
# define DEBUG_PRINT(s)
# define DEBUG_I_PRINT(s)
# define DEBUG_ENTER
# define DEBUG_EXIT
#endif

static int
Merge (void *array,
int p,
int q,
int r,
int elemSize,
TCompareFcn Compare);

int
MergeSort (void *array,
int startIndex,
int endIndex,
int elemSize,
TCompareFcn Compare)
{
if (startIndex < endIndex) {
int splitIndex;
DEBUG_ENTER;
splitIndex = (startIndex + endIndex) / 2;

DEBUG_I_PRINT(("MergeSort: %d %d\n", startIndex, splitIndex));
if (!MergeSort(array,startIndex,splitIndex,elemSize,C ompare))
return 0;
DEBUG_I_PRINT(("MergeSort: %d %d\n", splitIndex+1, endIndex));
if (!MergeSort(array,splitIndex + 1,endIndex,elemSize,Compare))
return 0;

DEBUG_I_PRINT(("Merge: %d %d %d\n", startIndex, splitIndex, endIndex));
if (!Merge(array,startIndex,splitIndex,endIndex,elemS ize,Compare))
return 0;
DEBUG_EXIT;
}
return 1;
}

static int
Merge (void *array,
int startIndex,
int splitIndex,
int endIndex,
int elemSize,
TCompareFcn Compare)
{
int numElems = endIndex - startIndex + 1;
unsigned char *pTemp, *pCurrTemp;
unsigned char *pArrBase = array;
int lowerCurr = startIndex;
int upperCurr = splitIndex + 1;
const unsigned char *pArrLower = pArrBase + lowerCurr*elemSize;
const unsigned char *pArrUpper = pArrBase + upperCurr*elemSize;

pTemp = malloc(elemSize * numElems);
if (NULL == pTemp)
return 0;
pCurrTemp = pTemp;

DEBUG_ENTER;
while (lowerCurr <= splitIndex && upperCurr <= endIndex) {
DEBUG_I_PRINT(("[%d(%d) %d(%d) -> ", lowerCurr, *(int*)pArrLower,
upperCurr, *(int*)pArrUpper));
if ((*Compare)(pArrLower, pArrUpper) <= 0 ) {
DEBUG_PRINT(("%d]\n", lowerCurr));
memcpy(pCurrTemp, pArrLower, elemSize);
pArrLower += elemSize;
++lowerCurr;
} else {
DEBUG_PRINT(("%d]\n", upperCurr));
memcpy(pCurrTemp, pArrUpper, elemSize);
pArrUpper += elemSize;
++upperCurr;
}
pCurrTemp += elemSize;
}
while (lowerCurr <= splitIndex ) {
DEBUG_I_PRINT(("[%d(%d)]\n", lowerCurr, *(int*)pArrLower));
memcpy(pCurrTemp, pArrLower, elemSize);
pArrLower += elemSize;
++lowerCurr;
pCurrTemp += elemSize;
}
while (upperCurr <= endIndex) {
DEBUG_I_PRINT(("[%d(%d)]\n", upperCurr, *(int*)pArrUpper));
memcpy(pCurrTemp, pArrUpper, elemSize);
pArrUpper += elemSize;
++upperCurr;
pCurrTemp += elemSize;
}

memcpy(pArrBase + startIndex*elemSize, pTemp, elemSize * numElems);

free(pTemp);
DEBUG_EXIT;

return 1;
}


int
IntegerComp(const void *keyA, const void *keyB)
{
const int *pIntKeyA = keyA;
const int *pIntKeyB = keyB;

return (*pIntKeyA > *pIntKeyB) - (*pIntKeyA < *pIntKeyB);
}

`----

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      09-22-2006
BRG said:

<snip>

> For example the line:
>
> while( j <= r ) out[k++] = array[j++];
>
> uses the array[r] element whereas the following line:
>
> for (i = p; i < r; i++)
>
> excludes this element.


Ah, thank you, Brian. Good spot. Together with my other fixes, that is
sufficient that the OP's sample array is correctly sorted, as is a second
test array I tried.

All that remains is to see whether he is sufficiently interested in his own
problem to request me to post my fixes.


--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      09-23-2006
Michael Mair wrote:
> rkk schrieb:
>
>> I have written a generic mergesort program which is as below:
>>

.... snip ...
>
> Note: One of the primary advantages of merge sort is that
> you do not have to keep everything in memory. Allocating
> a temp array leads that ad absurdum -- if a temp array is
> allowed, then we can implement something more efficient...


Mergesort is primarily useful in dealing with linked lists or
monstrous files, where its stability and ability to handle
arbitrary length lists are very helpful.

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html



--
Posted via a free Usenet account from http://www.teranews.com

 
Reply With Quote
 
rkk
Guest
Posts: n/a
 
      09-24-2006
Sorry for late response.

I do understand the mistakes I did in my version of program. Shortly I
will post my own corrected version.

Also Thanks to Michael for his mergesort code. It is really helpful.
Much appreciated.

One doubt I have is that to calculate the mem address of array why it
has to be casted to unsigned char * why cant char* instead? Sorry to
ask this very silly question here.

Many thanks for all of your help.

Regards
Kalyan

Richard Heathfield wrote:
> BRG said:
>
> <snip>
>
> > For example the line:
> >
> > while( j <= r ) out[k++] = array[j++];
> >
> > uses the array[r] element whereas the following line:
> >
> > for (i = p; i < r; i++)
> >
> > excludes this element.

>
> Ah, thank you, Brian. Good spot. Together with my other fixes, that is
> sufficient that the OP's sample array is correctly sorted, as is a second
> test array I tried.
>
> All that remains is to see whether he is sufficiently interested in his own
> problem to request me to post my fixes.
>
>
> --
> Richard Heathfield
> "Usenet is a strange place" - dmr 29/7/1999
> http://www.cpax.org.uk
> email: rjh at above domain (but drop the www, obviously)


 
Reply With Quote
 
rkk
Guest
Posts: n/a
 
      09-24-2006
Michael, Many thanks for this piece of code.

Regards
Kalyan

Michael Mair wrote:
> rkk schrieb:
> > Hi,
> >
> > I have written a generic mergesort program which is as below:
> > ---------------------------------------------------------
> > mergesort.h
> > -----------------------
> >
> > void
> > MergeSort(void *array[],int p,int r,int elemSize,int(*Compare)(const
> > void *keyA,const void *keyB));
> > void
> > Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
> > void *keyA,const void *keyB));
> > int
> > IntegerComp(const void *keyA,const void *keyB);
> >
> > mergesort.c
> > --------------------
> > #include <stdio.h>
> > #include <string.h>
> > #include <stdlib.h>
> > #include "mergesort.h"
> >
> >
> > void
> > MergeSort(void *array[],int p,int r,int elemSize,int(*Compare)(const
> > void *keyA,const void *keyB))

>
> Note: If you have an array of void*, then elemSize == sizeof (void*).
> You probably want either an array of generic pointers which you
> sort (an "index array") or an array of elements which you sort directly.
> I will go for the latter even though it is not very efficient for
> large elemSize.
>
> > {
> > int q;
> > if(p < r) {
> > q = (p + r)/2;
> > MergeSort(array,p,q,elemSize,Compare);
> > MergeSort(array,q + 1,r,elemSize,Compare);

>
> This suggests that p and r are valid indices.
>
> > Merge(array,p,q,r,elemSize,Compare);
> > }
> > }
> >
> > void
> > Merge(void *array[],int p,int q, int r,int elemSize,int(*Compare)(const
> > void *keyA,const void *keyB))

>
> Same as above.
>
> > {
> > void **out = (void **)malloc(elemSize * r);

>
> No check whether this was successful.
> You do not allocate the size you need which is
> elemSize * (r- p + 1)
>
> Note: One of the primary advantages of merge sort is that
> you do not have to keep everything in memory. Allocating
> a temp array leads that ad absurdum -- if a temp array is
> allowed, then we can implement something more efficient...
>
> > int i,k,j;
> > i = k = p;

>
> If you allocate only as much as you need, then k should start at 0.
>
> > j = q + 1;
> > while( i <= q && j <= r ) {
> > if( Compare( &array[i * elemSize],&array[j * elemSize] ) <= 0 ) {

>
> You cannot calculate the address of the array members like this.
> (unsigned char *)array + i * elemSize
> is the correct way to do this.
>
> > out[k++] = array[i++];
> > } else {
> > out[k++] = array[j++];
> > }
> > }
> > while( i <= q ) out[k++] = array[i++];
> > while( j <= r ) out[k++] = array[j++];
> >
> > for (i = p;i < r; i++) {
> > array[i] = out[i];
> > }
> > free(out);
> > }
> >
> >
> > int
> > IntegerComp(const void *keyA,const void *keyB)
> > {
> > if( (const int *) keyA == (const int *) keyB ) return 0;
> > else if( (const int *) keyA < (const int *) keyB ) return -1;
> > else if( (const int *) keyA > (const int *) keyB ) return 1;
> > }
> > ----------------------------------------------
> > And the driver program is here:
> > test.c
> > ---------
> > #include <stdio.h>
> > #include "mergesort.h"
> >
> > int
> > main()
> > {
> > int idx,length;
> > int arr[] = { 2,21,1,48,15,31,26 };
> > length = sizeof arr/sizeof &arr[0];

>
> sizeof arr / sizeof arr[0]
>
> >
> > printf("Before sorting array:\n");
> > for (idx = 0;idx < length;idx++)
> > {
> > printf("%d ",arr[idx]);
> > }
> > printf("\n");
> >
> > MergeSort(&arr,0,length,sizeof(int),IntegerComp);

>
> You have to pass "length - 1". If you write sizeof arr[0],
> then you are on the safe side even if the type of arr changes.
> >
> > printf("After sorting array:\n");
> > for (idx = 0;idx < length;idx++)
> > {
> > printf("%d ",arr[idx]);
> > }
> > printf("\n");
> >
> >
> > return 0;
> > }
> > ----------------------------------------------------------
> > I compile the programs above as:
> >
> > gcc -g -o mergesort mergesort.c test.c

>
> gcc -std=c89 -pedantic -Wall -O test.c mergesort.c -o test
>
> My changed version gives you some debug output; for this,
> you need -DMY_DEBUG on the command line.
>
> ,-- mergesort.h --
> #ifndef H_MERGE_SORT_H
> #define H_MERGE_SORT_H
>
> typedef int (*TCompareFcn) (const void *, const void *);
>
> int
> MergeSort (void *array,
> int startIndex,
> int endIndex,
> int elemSize,
> TCompareFcn Compare);
>
> int
> IntegerComp (const void *keyA,
> const void *keyB);
>
> #endif
>
> `----
> ,-- test.c --
> #include <stdio.h>
> #include "mergesort.h"
>
> int
> main (void)
> {
> int idx, length;
> int arr[] = { 2,21,1,48,15,31,26 };
> length = sizeof arr / sizeof arr[0];
>
> puts("Before sorting array:");
> for (idx = 0; idx < length; idx++)
> {
> printf(" %d", arr[idx]);
> }
> putchar('\n');
>
> if (!MergeSort(arr, 0, length - 1, sizeof arr[0], IntegerComp))
> fputs("Merging not successful\n", stderr);
>
> puts("After sorting array:");
> for (idx = 0; idx < length; idx++)
> {
> printf(" %d", arr[idx]);
> }
> putchar('\n');
>
>
> return 0;
> }
>
> `----
> ,-- mergesort.c --
> #include "mergesort.h"
>
> #include <string.h>
> #include <stdlib.h>
>
> #ifdef MY_DEBUG
> # include <stdio.h>
> # define DEBUG_PRINT(s) printf s
> # define DEBUG_I_PRINT(s) printf("%*s", indent, " "), DEBUG_PRINT(s)
> static int indent = 0;
> # define DEBUG_ENTER indent += 3
> # define DEBUG_EXIT indent -= 3
> #else
> # define DEBUG_PRINT(s)
> # define DEBUG_I_PRINT(s)
> # define DEBUG_ENTER
> # define DEBUG_EXIT
> #endif
>
> static int
> Merge (void *array,
> int p,
> int q,
> int r,
> int elemSize,
> TCompareFcn Compare);
>
> int
> MergeSort (void *array,
> int startIndex,
> int endIndex,
> int elemSize,
> TCompareFcn Compare)
> {
> if (startIndex < endIndex) {
> int splitIndex;
> DEBUG_ENTER;
> splitIndex = (startIndex + endIndex) / 2;
>
> DEBUG_I_PRINT(("MergeSort: %d %d\n", startIndex, splitIndex));
> if (!MergeSort(array,startIndex,splitIndex,elemSize,C ompare))
> return 0;
> DEBUG_I_PRINT(("MergeSort: %d %d\n", splitIndex+1, endIndex));
> if (!MergeSort(array,splitIndex + 1,endIndex,elemSize,Compare))
> return 0;
>
> DEBUG_I_PRINT(("Merge: %d %d %d\n", startIndex, splitIndex, endIndex));
> if (!Merge(array,startIndex,splitIndex,endIndex,elemS ize,Compare))
> return 0;
> DEBUG_EXIT;
> }
> return 1;
> }
>
> static int
> Merge (void *array,
> int startIndex,
> int splitIndex,
> int endIndex,
> int elemSize,
> TCompareFcn Compare)
> {
> int numElems = endIndex - startIndex + 1;
> unsigned char *pTemp, *pCurrTemp;
> unsigned char *pArrBase = array;
> int lowerCurr = startIndex;
> int upperCurr = splitIndex + 1;
> const unsigned char *pArrLower = pArrBase + lowerCurr*elemSize;
> const unsigned char *pArrUpper = pArrBase + upperCurr*elemSize;
>
> pTemp = malloc(elemSize * numElems);
> if (NULL == pTemp)
> return 0;
> pCurrTemp = pTemp;
>
> DEBUG_ENTER;
> while (lowerCurr <= splitIndex && upperCurr <= endIndex) {
> DEBUG_I_PRINT(("[%d(%d) %d(%d) -> ", lowerCurr, *(int*)pArrLower,
> upperCurr, *(int*)pArrUpper));
> if ((*Compare)(pArrLower, pArrUpper) <= 0 ) {
> DEBUG_PRINT(("%d]\n", lowerCurr));
> memcpy(pCurrTemp, pArrLower, elemSize);
> pArrLower += elemSize;
> ++lowerCurr;
> } else {
> DEBUG_PRINT(("%d]\n", upperCurr));
> memcpy(pCurrTemp, pArrUpper, elemSize);
> pArrUpper += elemSize;
> ++upperCurr;
> }
> pCurrTemp += elemSize;
> }
> while (lowerCurr <= splitIndex ) {
> DEBUG_I_PRINT(("[%d(%d)]\n", lowerCurr, *(int*)pArrLower));
> memcpy(pCurrTemp, pArrLower, elemSize);
> pArrLower += elemSize;
> ++lowerCurr;
> pCurrTemp += elemSize;
> }
> while (upperCurr <= endIndex) {
> DEBUG_I_PRINT(("[%d(%d)]\n", upperCurr, *(int*)pArrUpper));
> memcpy(pCurrTemp, pArrUpper, elemSize);
> pArrUpper += elemSize;
> ++upperCurr;
> pCurrTemp += elemSize;
> }
>
> memcpy(pArrBase + startIndex*elemSize, pTemp, elemSize * numElems);
>
> free(pTemp);
> DEBUG_EXIT;
>
> return 1;
> }
>
>
> int
> IntegerComp(const void *keyA, const void *keyB)
> {
> const int *pIntKeyA = keyA;
> const int *pIntKeyB = keyB;
>
> return (*pIntKeyA > *pIntKeyB) - (*pIntKeyA < *pIntKeyB);
> }
>
> `----
>
> Cheers
> Michael
> --
> E-Mail: Mine is an /at/ gmx /dot/ de address.


 
Reply With Quote
 
Michael Mair
Guest
Posts: n/a
 
      09-24-2006
Please do not top-post.
Your reply belongs below (or interspersed with) the text you
are replying to; you of course can and should snip whatever
you find not useful for the parts you want to discuss further.

rkk schrieb:
> Richard Heathfield wrote:
>>BRG said:

<snip: inconsistent use of the top index (included/excluded)
>>
>>Ah, thank you, Brian. Good spot. Together with my other fixes, that is
>>sufficient that the OP's sample array is correctly sorted, as is a second
>>test array I tried.
>>
>>All that remains is to see whether he is sufficiently interested in his own
>>problem to request me to post my fixes.

>
> Sorry for late response.
>
> I do understand the mistakes I did in my version of program. Shortly I
> will post my own corrected version.
>
> Also Thanks to Michael for his mergesort code. It is really helpful.
> Much appreciated.


I am happy to hear that
Note that this was only an example implementation of one of the
two possible solutions and not the one I would actually implement.


> One doubt I have is that to calculate the mem address of array why it
> has to be casted to unsigned char * why cant char* instead? Sorry to
> ask this very silly question here.


Not a silly question at all.

Even though void * has the same representation and alignment
requirements as a pointer to any of the three types of char,
you cannot do pointer arithmetic with it.
[Three types of char? char is special in that there is a difference
between signed char and "plain" char which is a type distinct from
both signed char and unsigned char but has the characteristics of
one of these.]
unsigned char * is the only type with which you can guaranteedly
access the representation (i.e. the underlying bit pattern) of any
object:
myType foo;
void *pFoo = &foo;
unsigned char *bar = pFoo;
int i;

/* assign value to foo */
....

for (i = 0; i < sizeof foo; ++i) {
printf("%x\t", (unsigned int) bar[i]);
}
putchar('\n');
will give you the bytes of foo.
Neither char * nor signed char * guaranteedly can give you that.
Thus, you use "char" for characters and "unsigned char" if you
mean bytes and want to calculate addresses.

The comp.lang.c FAQ tells you a little bit more about that:
http://c-faq.com


Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      09-24-2006
rkk wrote:
>

.... snip ...
>
> One doubt I have is that to calculate the mem address of array why
> it has to be casted to unsigned char * why cant char* instead?
> Sorry to ask this very silly question here.


Please don't top-post. Your answer belongs after, or possibly
intermixed with, the material you quote, after snipping. See the
links in my sig. below.

You cast to unsigned char because your system may define char as
either signed or unsigned. Without the cast the code is not
portable. Many routines (e.g. toupper() etc.) require unsigned
chars.

--
Some informative links:
<news:news.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/>


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sony Completes First Full-Length Blu-ray Disc Allan DVD Video 33 11-28-2005 08:49 PM
how to disable a JButton while an op completes? supermail99@fastmail.fm Java 8 10-13-2005 04:38 AM
Using C# to redirect one form to another after a specific task completes Brian Gordaychik ASP .Net 6 12-06-2004 04:57 PM
Running program from diagnostics.process never completes. joeted ASP .Net 0 04-21-2004 07:09 AM
java input and output stream to the same file at the same time? Krick Java 1 08-15-2003 05:55 PM



Advertisments