Sorting: Getting permutation index array

Instead of actually sorting an array, how would you go about obtaining the permutation index array, mapping the original array to the sorted? E.g. if the array to be sorted is

{ 12, 8, 3, 17, 10 }

the desired permutation index would be

{ 2, 1, 4, 0, 3 }

The solution I have seen (http://www.freshsources.com/199300F2.HTM#00F2_007D) declares the array to be sorted globally at the top, creates a compare function that compares elements in this array and hands it to qsort (with an index array). This works in the hypothetical case that you know the array you want to sort before you write your code, but what is the workaround when the array is found at run time?

Quote:

---

Originally Posted by flyvholm

Instead of actually sorting an array, how would you go about obtaining the permutation index array, mapping the original array to the sorted? E.g. if the array to be sorted is

{ 12, 8, 3, 17, 10 }

the desired permutation index would be

{ 2, 1, 4, 0, 3 }

The solution I have seen (http://www.freshsources.com/199300F2.HTM#00F2_007D) declares the array to be sorted globally at the top, creates a compare function that compares elements in this array and hands it to qsort (with an index array). This works in the hypothetical case that you know the array you want to sort before you write your code, but what is the workaround when the array is found at run time?

---

No real differences I see from your description. How you "find" the array and whether it's local or global, doesn't matter.

Your source was right, you compare the elements of the array, just like you were going to sort them, but instead of sorting the elements, you sort the index elements you made just before starting the comparisons.

Code:

---

for (i = 0; i < arraysize; i++)
  index[i] = i;

---

Sets the index array up.

When you go to print up the "sorted" array, remember to print it out THROUGH the index array.

Why don't you post up your specific code that's causing you problems. I'm not sure at all that I've got my head wrapped around what the real problem is that you're having.

Adak

No wonder you can't tell what my mind is tripping over. What I failed to realize is that I only have to DECLARE the array globally whereas I can fill in values locally. Sorry, I'm a noob! :)