SORT Integer Array TAG a STRUCTURE Array (or two)

Question

So the idea is to sort a large STRUCTURE using an element of that structure, for arguments sake Zip Code.

To keep it simple lets pretend that there are two arrays, one integer containing the zip codes and two, a larger structure (3k Bytes) array.

Sorting the integer array is suitably fast with Quick Sort, but tagging the Structure array could be done a little better than simply swapping elements when the integer array swaps elements.

In testing a random 3000 element integer array required 12000 swaps to achieve a completed sort. Swapping the entire structure that many times would have a performance penalty esp if there are many elements.

Ideally I would just sort an array of pointers, but in this case I actually have to return a sorted structure array not an array of sorted pointers. If nothing else this is an exercise in sorting a tagged array.

One approach would be to tag a secondary integer array, and then use the order within it to shuffle the elements of the structure around, thus moving each element only once.

I am not finding much help on the web http://rosettacode.org/wiki/Sorting_an_Array_of_Integers#C

Suggestions for an elegant design would be appreciated.

Answer 1

In the above you should really be using std::vectors, not arrays. I can't imagine why you can't return a (const) vector of pointers, but if that is the case, work with a vector of pointers, sorting only the pointers and then when sorted, copy the resulting sorted structures into another vector and return that, which will mean only one copy per vector entry.

Answer 2

If you want to avoid swapping overhead, you could try Selection Sort. This sorting algorithm will find a value and immediatly put it into the right place performing only one swap, thus, I believe, doing the minimal number of swaps as possible.

Answer 3

You could put it into a std::list and then define the comparison function for the sort. It should only swap the pointers to each node and not the structures. Swaping of pointers is a quick 2 or 3 op function.