October 25th, 2013, 01:52 AM
Qsort struct with (pointer) permutation vector
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 =)
October 25th, 2013, 08:58 AM
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] are essential for python code and Makefiles!