By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,812 Members | 1,288 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,812 IT Pros & Developers. It's quick & easy.

Generic Sort

P: n/a
AB
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?

Thanks in advance.

May 24 '06 #1
Share this Question
Share on Google+
22 Replies


P: n/a
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)
May 24 '06 #2

P: n/a

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

This might solve your problem.
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?

Thanks in advance.


May 24 '06 #3

P: n/a
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
May 24 '06 #4

P: n/a
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
May 24 '06 #5

P: n/a
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
May 24 '06 #6

P: n/a
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
May 24 '06 #7

P: n/a
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
May 24 '06 #8

P: n/a
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
May 24 '06 #9

P: n/a
AB
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" */
}

May 25 '06 #10

P: n/a
AB wrote:
what I
needed help on was passing the parameters to the comparison function.


That's what I posted.

You had this line:

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

Compare that to this line:

if (compar(arr + j * size, arr + (j + 1) * size) > 0) {

For one thing,
you have no relational operator in your comparison line.
It swaps elements whenever they are unequal.

The other problem, is that in your posted code
you have
void *arr
which means that you can't have
arr[j]
I order to be able to write that, and make it have meaning
the declaration of arr would have to be
int *arr
which means that you function would only be able to arrays
of type int.
Notice that your function doesn't use the size parameter.

This would work,
if you only ever used it with arrays of type int:

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

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

However, since a sort that only sorts arrays of type int
isn't your assignment, it should be more like this:

void sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
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 */
}
}
}
}

Try not to be distracted by the difference in the loops.
That's not your code anymore, that's my code;
that's why it looks like that.
I tested it before I posted it the first time.

The original order of the array is:
4.000000 3.500000 1.000000 2.000000

The sorted order of the array is:
1.000000 2.000000 3.500000 4.000000

/* BEGIN new.c */

#include <stdio.h>

#define E_TYPE double

#define BYTE_SWAP(A, B) \
{ \
p1 = (A); \
p2 = (B); \
end = p2 + size; \
do { \
swap = *p1; \
*p1++ = *p2; \
*p2++ = swap; \
} while (p2 != end); \
}

typedef E_TYPE e_type;

int comparison(const void *arg1, const void *arg2);
void sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
e_type array[] = {(4), (3.5), (1), (2)};
size_t x;

puts("The original order of the array is:");
for (x = 0; x != sizeof array / sizeof *array; ++x) {
printf("%f ", array[x]);
}
puts("\n");
sort(array, sizeof array / sizeof *array,
sizeof *array, comparison);
puts("The sorted order of the array is:");
for (x = 0; x != sizeof array / sizeof *array; ++x) {
printf("%f ", array[x]);
}
putchar('\n');
return 0;
}

int comparison(const void *arg1, const void *arg2)
{
return *(e_type*)arg2 > *(e_type*)arg1 ? -1
: *(e_type*)arg2 != *(e_type*)arg1;
}

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 ;
unsigned char *p1, *p2, *end, swap;

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

/* END new.c */

--
pete
May 25 '06 #11

P: n/a
"AB" <ab*****@gmail.com> writes:
For those unfamiliar with the CRT qsort should look it up.
"CRT" isn't a common abbreviation here. I assume you mean "C
runtime".
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.
It would be better to use a C reference manual instead of MSDN,
which describes Microsoft's implementation, not the standard.
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" */
}


A better way:

int compare (const void *a_, const void *b_)
{
const int *a = a_;
const int *b = b_;
return *a < *b ? -1 : *a > *b;
}
--
"...deficient support can be a virtue.
It keeps the amateurs off."
--Bjarne Stroustrup
May 25 '06 #12

P: n/a
Ben Pfaff wrote:

"AB" <ab*****@gmail.com> writes:
For those unfamiliar with the CRT qsort should look it up.
"CRT" isn't a common abbreviation here. I assume you mean "C
runtime".


I had no idea what it meant.
int compare (const void *a_, const void *b_)
{
const int *a = a_;
const int *b = b_;
return *a < *b ? -1 : *a > *b;
}


I've read of coding standards which reserve verb style names
for functions that have side effects,
suggesting that "comparison",
or perhaps even a nonword like "comp"
might be a better choice for the name of the function.

Any thoughts on that?

--
pete
May 25 '06 #13

P: n/a
pete <pf*****@mindspring.com> writes:
I've read of coding standards which reserve verb style names
for functions that have side effects,
suggesting that "comparison",
or perhaps even a nonword like "comp"
might be a better choice for the name of the function.

Any thoughts on that?


I haven't heard of a coding standard that specifies that before.
It sounds to me like an interesting idea. If anyone here has
experience with such a coding standard, then I'd like to hear
about how it works out in practice.
--
"IMO, Perl is an excellent language to break your teeth on"
--Micah Cowan
May 25 '06 #14

P: n/a
AB wrote:
.... snip ...
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" */
}


So far, fine. The point is that YOU know the actual types of the
data to be compared, and how to do the comparison. The void*
pointers are to allow qsort to manipulate them without knowing
anything about their types. So the easiest thing to do is first
control the types, and you don't need any casts to do so If the
types to be compared are T, then:

int compare(const void* a, const void *b)
{
const T *ap = a;
const T *bp = b;

and now you can write the rest of the routine using ap and bp, with
all the type checking of which C is capable. For integers the rest
of the code might then be:

if (*ap < *bp) return 1;
else if (*ap > *bp) return -1;
return 0;
}

You can let the optimizer decide if it really needs to create
locals for ap and bp. Meanwhile the actual code becomes crystal
clear. BTW, the default case is absolutely necessary.

For ints, another way to write the function body is:

return (*ap < *bp) - (*ap > *bp);

which has advantages on some architectures. Remember that logical
expressions evaluate to either 0 or 1.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
May 25 '06 #15

P: n/a
pete schrieb:
Ben Pfaff wrote:
int compare (const void *a_, const void *b_)
{
const int *a = a_;
const int *b = b_;
return *a < *b ? -1 : *a > *b;
}


I've read of coding standards which reserve verb style names
for functions that have side effects,
suggesting that "comparison",
or perhaps even a nonword like "comp"
might be a better choice for the name of the function.

Any thoughts on that?


The only similar thing I know in coding standards are rules that
predicates should always be side effect free, i.e. if the function
starts with is, has, contains etc., then it returns a Boolean value
(of some integer type) and is side effect free.
Possible extensions:
- Comparisons; here, you have some fixed part of the function
identifier, e.g. "starts with compare" or cmp, which indicates "no
side effects"
- constant get...() functions are side effect free
However, all other function identifiers are verb style names, too.

These are IMO more useful rules as the other rule may make it much
harder to create "good" identifiers for arbitrary projects.
In addition, if you decide to change what happens under the hood,
you would have to change function names -- due to the more
restrictive rule this would happen much more often than you need
to change from "is...()" to "obtain...State()".

Another aspect which should be clear beforehand: What do you see
as "side effect free" or "pure"? It may be perfectly reasonable to
separate changing debug and tracing information from changing
other information when making this distinction.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
May 25 '06 #16

P: n/a
AB
Thanks to all those who replied to my post. I'd like to clear that this
wasn't an assignment..it was just something that was on my todo list
for a while. I've always been partial to C++ and so a generic sort was
easy to implement with templates. However, when I thought about a port
to C, this problem arose.

Anyways, I've solved the problem and for those who're interested...

typedef unsigned char byte ;

//for sorting int in ascending order
int cmp_int_asc(const void* a, const void* b)
{
if(*(int *)a < *(int *)b)
return -1 ;
else if(*(int *)a == *(int *)b)
return 0 ;
else if(*(int *)a > *(int *)b)
return 1 ;
}

void sort(void *base, int num, size_t size, int(*cmp)(const void* a,
const void* b))
{
byte temp,
*ptr2a,
*ptr2b,
*ptr2base;

ptr2base = (byte *)base ;

for(int i = num - 1; i >= 0; i--)
{
for(int j = 1; j <= i; j++)
{
ptr2a = (byte*) (ptr2base + size * (j - 1)) ;
ptr2b = (byte*) (ptr2base + size * j) ;

if(cmp(ptr2a, ptr2b) > 0)
swap_bytes(ptr2a, ptr2b, size) ;
}
}
}

void swap_bytes(byte *a, byte *b, size_t size)
{
byte temp ;

for(int i = 0; i < size; i++)
{
temp = *(a + i) ;
*(a + i) = *(b + i) ;
*(b + i) = temp ;
}
}

May 26 '06 #17

P: n/a
On Thu, 25 May 2006 15:02:29 GMT,
pete <pf*****@mindspring.com> wrote
in Msg. <44***********@mindspring.com>
I've read of coding standards which reserve verb style names
for functions that have side effects,
suggesting that "comparison",
or perhaps even a nonword like "comp"
might be a better choice for the name of the function.


It depends on how you want to use the function. I once wrote a database
application that would sort arrays of structs by different fields, so
all my comparison functions started in "by_", resulting in beautiful
functions calls like:

qsort(record, ..., by_name);

This also reflects my tendency to use the singular for array names
because I prefer

record[i].name
over
records[i].name

robert
May 26 '06 #18

P: n/a
On 26 May 2006 00:15:30 -0700, "AB" <ab*****@gmail.com> wrote:
Thanks to all those who replied to my post. I'd like to clear that this
wasn't an assignment..it was just something that was on my todo list
for a while. I've always been partial to C++ and so a generic sort was
easy to implement with templates. However, when I thought about a port
to C, this problem arose.

Anyways, I've solved the problem and for those who're interested...

typedef unsigned char byte ;

//for sorting int in ascending order
int cmp_int_asc(const void* a, const void* b)
{
if(*(int *)a < *(int *)b)
Everywhere else you were careful to keep your code independent of the
sizeof an array element. Why here do you forsake that and insist on
int?
return -1 ;
else if(*(int *)a == *(int *)b)
return 0 ;
else if(*(int *)a > *(int *)b)
return 1 ;
}

void sort(void *base, int num, size_t size, int(*cmp)(const void* a,
const void* b))
{
byte temp,
*ptr2a,
*ptr2b,
*ptr2base;

ptr2base = (byte *)base ;
You don't need to cast a void* to assign it to another pointer.

for(int i = num - 1; i >= 0; i--)
{
for(int j = 1; j <= i; j++)
{
ptr2a = (byte*) (ptr2base + size * (j - 1)) ;
ptr2b = (byte*) (ptr2base + size * j) ;

if(cmp(ptr2a, ptr2b) > 0)
swap_bytes(ptr2a, ptr2b, size) ;
}
}
}

void swap_bytes(byte *a, byte *b, size_t size)
{
byte temp ;

for(int i = 0; i < size; i++)
{
temp = *(a + i) ;
*(a + i) = *(b + i) ;
*(b + i) = temp ;
}
}

Remove del for email
May 27 '06 #19

P: n/a
Barry Schwarz wrote:

On 26 May 2006 00:15:30 -0700, "AB" <ab*****@gmail.com> wrote:

//for sorting int in ascending order
int cmp_int_asc(const void* a, const void* b)
{
if(*(int *)a < *(int *)b)


Everywhere else you were careful to keep your code independent of the
sizeof an array element. Why here do you forsake that and insist on
int?


That's just a sample comparison function.
Those are written for specific data types.

--
pete
May 27 '06 #20

P: n/a
AB
cmp_int_asc is an example function as Pete pointed out. You could write
your own comparison function for a datatype of your choice.
ptr2base = (byte *)base ;


I compiled the code using a C++ compiler, which is why I had to
explicitly typecast it to a byte*

May 27 '06 #21

P: n/a
AB said:
cmp_int_asc is an example function as Pete pointed out. You could write
your own comparison function for a datatype of your choice.
ptr2base = (byte *)base ;
I compiled the code using a C++ compiler,


Please understand that C and C++ are different languages, with distinct
rules. Advice given in comp.lang.c that is correct for C may, and quite
often will, not be suitable for programs compiled under C++ rules,
irrespective of whether those programs are also legal C programs.
which is why I had to explicitly typecast it to a byte*


A minor case in point.

--
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)
May 27 '06 #22

P: n/a
AB wrote:
I compiled the code using a C++ compiler, which is why I had to
explicitly typecast it to a byte*


The word is "cast".
"Typecast" is a concept in performing arts.

http://dictionary.reference.com/search?q=typecast&db=*

--
pete
May 27 '06 #23

This discussion thread is closed

Replies have been disabled for this discussion.