1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Rep Power

    Qsort struct with (pointer) permutation vector

    Hey guys,

    I'm stucking in c, because I have to sort a struct without changing it and found nothing with google, so I hope to get some help right here:

    My program contains three struct: Book, Author & Publisher and I have to output the top 20 Authors and Publisher with the most books (book_count is available in both structs), but the origin struct cannot be sorted because in the book struct there are pointer to author and publisher ... My only idea is to copy the struct, sort it and try to make the permutation vektor with the indexes, but I guess that's not really performant / efficient ... Does everybody has an idea please?

    Im quite thanksful for every helpful or nice mented reply, thank you very much in advance =)
  2. #2
  3. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Rep Power

    Save us time

    Please post code of the struct and vector (array) of the structs so we can see rather than reinvent what we think you're explaining.

    Sorting involves comparing, not altering individual items.
    Sorting the entire list by book count then reporting the top 20 with qsort would be a good approach.

    qsort works in place so yes, you might need to duplicate the list of books then sort that.

    Of course, since you need only the top 20 there are faster algorithms than rearranging the entire list. Well, I was familiar with them at the end of spring (northern hemisphere). One way that should work is to use a partial quick sort---there might be tricks to finding best pivot.

    Using an "out of place" method is another option. You'd sort the data into another array (of dimension 20). There might be a radix sort method that could just crush this problem. Radix sort is possible in place but easier to program as an "out of place" method.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo