Generic Sort

I'm passing an array into this function and it's taking the item at index 0 and replacing the rest of the array with it. Any idea where this is going wrong?

Code:

void generic_sort (void *arg, size_t num, size_t size, int (*cmpfnc) (const void *, const void *)) { for (int i = 1; i < (int)num; ++i) { int j = i; char *tmp_address = malloc (sizeof (arg)); tmp_address = (char *)arg + j * size; for (; j > 0; --j) { int cmp = cmpfnc (tmp_address, (char *)arg + (j - 1) * size); if (cmp > 0) break; memcpy ((char *)arg + j * size, (char *)arg + (j - 1) * size, size); } memcpy ((char *)arg + j * size, tmp_address, size); } }

Yes, delete line 4 (well the malloc part of it anyway).

You should only be casting void* to char* so you can do the pointer arithmetic on it.

> memcpy ((char *)arg + j * size, (char *)arg + (j - 1) * size, size);
What you might need to do however, is think about how you're SWAPPING two array elements, because at the moment, you're just trashing one element with another.

Quote:

Originally Posted by Salem

> memcpy ((char *)arg + j * size, (char *)arg + (j - 1) * size, size);
What you might need to do however, is think about how you're SWAPPING two array elements, because at the moment, you're just trashing one element with another.

Thank you for pointing that out! It's early morning here.. I completely forgot about the other item..

This code seems to switch the last two of the array..

Code:

for (int i = 1; i < (int)num; ++i) { int j = i; void *element = (char *)arg + j * size; void *tmp_address = malloc (sizeof (arg)); for (; j > 0; --j) { int cmp = cmpfnc (element, (char *)arg + (j - 1) * size); if (cmp > 0) break; memcpy (tmp_address, element, size); memcpy (element, (char *)arg + (j - 1) * size, size); memcpy ((char *)arg + (j - 1) * size, tmp_address, size); } memcpy (tmp_address, (char *)arg + j * size, size); memcpy ((char *)arg + j * size, element, size); memcpy (element, tmp_address, size); }

Are you asking us what does this code do? Or you have found a bug on it? It looks like a similar code with post number one, so get a look at Salem's post again.
There is qsort, which is already implemented in a generic way by stdlib.h (if you don't want to write your own code...)

Quote:

Originally Posted by std10093

Are you asking us what does this code do? Or you have found a bug on it? It looks like a similar code with post number one, so get a look at Salem's post again.
There is qsort, which is already implemented in a generic way by stdlib.h (if you don't want to write your own code...)

You often need your own sort. Both as a learning exercise, and because qsort is recursive, so unacceptable for some applications. Also sometimes you can beat qsort() is you know about a problem. Consider a football league. After each match day, the club positions need to be sorted. But each club can only move one or two positions at once, because you only get a maximum of three points for a game and you can only play one game a day. So the list is almost sorted, and qsort is a poor choice of algorithm.

> void *tmp_address = malloc (sizeof (arg));
Mmm, what about this then.

> memcpy (tmp_address, element, size);
Did you really allocate enough space?

Also, you need to free your temporary memory when you're done.

Quote:

Originally Posted by Malcolm McLean

You often need your own sort. Both as a learning exercise, and because qsort is recursive, so unacceptable for some applications. Also sometimes you can beat qsort() is you know about a problem. Consider a football league. After each match day, the club positions need to be sorted. But each club can only move one or two positions at once, because you only get a maximum of three points for a game and you can only play one game a day. So the list is almost sorted, and qsort is a poor choice of algorithm.

If you know a decision in our life that does not have a way of trade off let me know ;)

Quote:

Originally Posted by Salem

> void *tmp_address = malloc (sizeof (arg));
Mmm, what about this then.

> memcpy (tmp_address, element, size);
Did you really allocate enough space?

Ah. I was thinking for tmp_address I would just need a size of a pointer and not the size of the element being copied. The values I enter still aren't being sorted right and I can't find a pattern to how it's being sorted.

Here's how I'm sorting int

Code:

int intcmp (const void *this, const void *that) { int *thisint = (int*)this; int *thatint = (int*)that; if (*thisint < *thatint) { return -1; }else if (*thisint > *thatint) { return 1; }else { return 0; } }

Quote:

Originally Posted by Malcolm McLean

You often need your own sort. Both as a learning exercise, and because qsort is recursive, so unacceptable for some applications. Also sometimes you can beat qsort() is you know about a problem. Consider a football league. After each match day, the club positions need to be sorted. But each club can only move one or two positions at once, because you only get a maximum of three points for a game and you can only play one game a day. So the list is almost sorted, and qsort is a poor choice of algorithm.

Sounds perfect for Insertion sort.

@Auxfire:

When you boil down your code, you're doing this:

Code:

return(*thisint - *thatint);

Same as qsort() and strcmp(). All the if's and else if's and else's you can dump. Sometimes the best code you can write is with the delete key.

The way that Adak says is used be me too. What would happen with this, when you have unsigned integers? When the difference of the two unsigned integers would be more than 2^31, then you would probably receive a logical error. But for signed integers, I think it is very elegant and I use it.

Check the link on post #5 if you like, I have the both ways there with comments.

Quote:

Originally Posted by Adak

Sounds perfect for Insertion sort.

@Auxfire:

When you boil down your code, you're doing this:

Code:

return(*thisint - *thatint);

Same as qsort() and strcmp(). All the if's and else if's and else's you can dump. Sometimes the best code you can write is with the delete key.

Actually, I wouldn't.
The quick and dirty hack of returning (left - right) returns the wrong value in some cases. e.g. 2billion and -2billion.
When you subtract you get 4billion which of course is not representable as a signed 32-bit int, and instead becomes negative, placing them in the wrong order.
It can also fail for the same reason that abs(-2147483648) = -2147483648.

There is a branchless way of comparing them, but that isn't it. IIRC it's this, not that I suggest using it as it's clearly non-portable, relying on two-s complement representation etc:

Code:

return((unsigned(*thisint) ^ 0x80000000U) - (unsigned(*thatint) ^ 0x80000000U));

If my sorting routine is correct. Why is it not rearranging the elements correctly?

Your sort is very similar to a Substitution sort - with i and j "meeting in the middle" of the array.

This is roughly how your sort logic should be done - i and j can increment or decrement, as you wish.

Check your current logic against this and see what you think:

Code:

//in this example, A[] is a global array. void middle1(int lo, int hi) { int i,j,temp; for(i=hi-1;i>-1;i--) { //i goes down for(j=0;j<i;j++) { //j goes up if(A[j] > A[i]) { temp=A[j]; A[j]=A[i]; A[i]=temp; } } } }

And right away, you can see the difference. Your j variable is set to i, just before the inner for loop.

Which is ALMOST right for a normal Substitution sort, but it's not right for this "meet in the middle" version, you have here.

Set j to the side opposite of where it's heading (here, it's going up, so it starts at 0. If you want it to decrement as it loops, have it set for the highest index of your data.

It's fun to work with sorting algorithms, but they ARE tricky.