Thread: Generic Sort

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    11

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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    11
    Quote Originally Posted by Salem View Post
    > 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..

  4. #4
    Registered User
    Join Date
    Feb 2013
    Posts
    11
    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);
       }

  5. #5
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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...)
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  6. #6
    Registered User
    Join Date
    May 2012
    Posts
    505
    Quote Originally Posted by std10093 View Post
    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.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by Malcolm McLean View Post
    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
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  9. #9
    Registered User
    Join Date
    Feb 2013
    Posts
    11
    Quote Originally Posted by Salem View Post
    > 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;
       }
    }

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Malcolm McLean View Post
    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.

  11. #11
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Adak View Post
    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));
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Feb 2013
    Posts
    11
    If my sorting routine is correct. Why is it not rearranging the elements correctly?

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. generic insertion sort
    By edishuman in forum C Programming
    Replies: 1
    Last Post: 11-23-2011, 10:19 PM
  2. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  3. Replies: 1
    Last Post: 01-26-2010, 09:02 AM
  4. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM