Velocity Reviews > Generic Sort

# Generic Sort

AB
Guest
Posts: n/a

 05-24-2006
Hello All,

I'm trying to replicate a general purpose sort function (think qsort)

void sort(void *arr, const int num, size_t size,
int (*cmp)(void *a, void *b))
{
int i = 0 ;
int j = 0 ;

for (i = (num - 1) ; i >= 0 ; i--)
{
for (j = 1 ; j <= i ; j++)
{
if(cmp((int *) &arr[j-1], (int *) &arr[j])) //Error
{
//swapping logic
}
}
}
}

MSVC 8 (2005) reports 2 errors when trying to call cmp:-

error C2036: 'void *' : unknown size
error C2036: 'void *' : unknown size

I've tried a few variations, but I can't seem to get it right. Can
anybody help?

Richard Heathfield
Guest
Posts: n/a

 05-24-2006
AB said:

> Hello All,
>
> I'm trying to replicate a general purpose sort function (think qsort)
>
> void sort(void *arr, const int num, size_t size,
> int (*cmp)(void *a, void *b))

Better:

void sort(const void *arr, size_t num, size_t size,
int (*cmp)(const void *a, const void *b))

> {
> int i = 0 ;
> int j = 0 ;
>
> for (i = (num - 1) ; i >= 0 ; i--)
> {
> for (j = 1 ; j <= i ; j++)
> {
> if(cmp((int *) &arr[j-1], (int *) &arr[j])) //Error

for(j = 1; j <= i; j++)
{
const unsigned char *left = arr;
const unsigned char *right;
left += (j - 1) * size;
right = left + size;
if((*cmp)(left, right) > 0)

--
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)

sandy
Guest
Posts: n/a

 05-24-2006

AB wrote:

> Hello All,
>
> I'm trying to replicate a general purpose sort function (think qsort)
>
> void sort(void *arr, const int num, size_t size,
> int (*cmp)(void *a, void *b))
> {
> int i = 0 ;
> int j = 0 ;
>
> for (i = (num - 1) ; i >= 0 ; i--)
> {
> for (j = 1 ; j <= i ; j++)
> {
> if(cmp((int *) &arr[j-1], (int *) &arr[j])) //Error
>

try if(cmp(int *)arr[j-1] , (int *) arr[j])))

> if(cmp((int *) &arr[j-1], (int *) &arr[j])) //Error

Why & for a variable which is already a pointer(according to your
logic)....In this does it makes sense. Check that part out again.
{
> //swapping logic
> }
> }
> }
> }
>
> MSVC 8 (2005) reports 2 errors when trying to call cmp:-
>
> error C2036: 'void *' : unknown size
> error C2036: 'void *' : unknown size
>
> I've tried a few variations, but I can't seem to get it right. Can
> anybody help?
>

pete
Guest
Posts: n/a

 05-24-2006
AB wrote:
>
> Hello All,
>
> I'm trying to replicate a general purpose sort function (think qsort)
>
> void sort(void *arr, const int num, size_t size,
> int (*cmp)(void *a, void *b))
> {
> int i = 0 ;
> int j = 0 ;
>
> for (i = (num - 1) ; i >= 0 ; i--)
> {
> for (j = 1 ; j <= i ; j++)
> {
> if(cmp((int *) &arr[j-1], (int *) &arr[j])) //Error
> {
> //swapping logic
> }
> }
> }
> }
>
> MSVC 8 (2005) reports 2 errors when trying to call cmp:-
>
> error C2036: 'void *' : unknown size
> error C2036: 'void *' : unknown size
>
> I've tried a few variations, but I can't seem to get it right. Can
> anybody help?

void sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *a, const void *b))
{
unsigned char *arr = base;
size_t i = nmemb ;
size_t j ;

while (i-- > 0) {
for (j = 0 ; i > j ; ++j) {
if (compar(arr + j * size, arr + (j + 1) * size) > 0) {
/* swapping logic */
}
}
}
}

--
pete

pete
Guest
Posts: n/a

 05-24-2006
sandy wrote:

> try if(cmp(int *)arr[j-1] , (int *) arr[j])))
>
> This might solve your problem.

Do you really think that swapping every pair
of elements that are unequal to each other,
is going to sort something?

What's the (int *) cast all about?
It looks like it's for a generic sort
that only sorts arrays of int.

--
pete

Tomás
Guest
Posts: n/a

 05-24-2006
AB posted:

> Hello All,
>
> I'm trying to replicate a general purpose sort function (think qsort)

I've tried this myself too. I'll just have a look through my code
directory... ah here we are:

(It was originally written in C++, so I translated it on-the-fly. I
didn't spend time optimizing it)

#include <stdlib.h>

typedef int T;

void SortArray( T* p_start, unsigned long const len )
{
const T * const p_last = p_start + (len - 1);

do
{
T* p_lowest_value = p_start;

for( T* p = p_start; p <= p_last; ++p)
{
if ( *p < *p_lowest_value ) p_lowest_value = p;
}

if ( p_start == p_lowest_value ) continue;

char temp[ sizeof(T) ];

memcpy( temp, p_start, sizeof(temp) );

memcpy( p_start, p_lowest_value, sizeof(temp) );

memcpy( p_lowest_value, temp, sizeof(temp) ) ;
}
while (++p_start != p_last);
}

-Tomás

pete
Guest
Posts: n/a

 05-24-2006
Tomás wrote:
>
> AB posted:
>
> > Hello All,
> >
> > I'm trying to replicate a general purpose sort function (think qsort)

>
> I've tried this myself too. I'll just have a look through my code
> directory... ah here we are:
>
> (It was originally written in C++, so I translated it on-the-fly. I
> didn't spend time optimizing it)
>
> #include <stdlib.h>
>
> typedef int T;
>
> void SortArray( T* p_start, unsigned long const len )
> {
> const T * const p_last = p_start + (len - 1);
>
> do
> {
> T* p_lowest_value = p_start;
>
> for( T* p = p_start; p <= p_last; ++p)
> {
> if ( *p < *p_lowest_value ) p_lowest_value = p;
> }
>
> if ( p_start == p_lowest_value ) continue;
>
> char temp[ sizeof(T) ];
>
> memcpy( temp, p_start, sizeof(temp) );
>
> memcpy( p_start, p_lowest_value, sizeof(temp) );
>
> memcpy( p_lowest_value, temp, sizeof(temp) ) ;
> }
> while (++p_start != p_last);
> }

That's not a general purpose sort function (think qsort)
It doesn't have a general pupose comparison.

It couldn't sort this array on any key:
char *array[] = {"one", "three", "two"};

--
pete

pete
Guest
Posts: n/a

 05-24-2006
pete wrote:

> void sort(void *base, size_t nmemb, size_t size,
> int (*compar)(const void *a, const void *b))

The a and b parameters shouldn't be in there.
They don't cause any real problems,
but they're meaningless.

void sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))

--
pete

pete
Guest
Posts: n/a

 05-24-2006
pete wrote:
>
> pete wrote:
>
> > void sort(void *base, size_t nmemb, size_t size,
> > int (*compar)(const void *a, const void *b))

>
> The a and b parameters
> shouldn't be in there.
> They don't cause any real problems,
> but they're meaningless.
>
> void sort(void *base, size_t nmemb, size_t size,
> int (*compar)(const void *, const void *))

The a and b parameter "names" shouldn't be in there.
The parameters themselves, do need to be there.

--
pete

AB
Guest
Posts: n/a

 05-25-2006
Thanks for your responses everyone. However I should make it clear that
I was not looking for advice on function declaration or optimization of
the sort procedure. The sort function itself is immaterial, what I
needed help on was passing the parameters to the comparison function.

For those unfamiliar with the CRT qsort should look it up. You can in
fact sort a sentence (for what it's worth) using a comparison function
that accepts two void pointers and returns an integer value. Look it up
on MSDN, that's the very example used to explain how qsort works, and
how to define a custom comparison function (operator) for it.

According to the documentation, the comparison function acceptable to
qsort (and what I'm trying to emulate) works something like this...

int compare(const void* a, const void *b)
{
if( ( *(type *) a < *(type *) b )
return -1 ;
else if( ( *(type *) a == *(type *) b )
return 0 ;
else if( ( *(type *) a > *(type *) b )
return 1 ;
return 0 ; /* default case, written here only to silence critics who
will say that "not all paths of the function return a value" */
}