Thread: Sorting: Getting permutation index array

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    Fairbanks, Alaska
    Posts
    2

    Question 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?

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

  3. #3
    Registered User
    Join Date
    Sep 2006
    Location
    Fairbanks, Alaska
    Posts
    2

    D'oh!

    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 03-31-2009, 12:34 PM
  2. 20q game problems
    By Nexus-ZERO in forum C Programming
    Replies: 24
    Last Post: 12-17-2008, 05:48 PM
  3. Sorting Array
    By dmkanz07 in forum C Programming
    Replies: 14
    Last Post: 04-24-2007, 10:12 AM
  4. Array Index: A simple question?
    By logicwonder in forum C Programming
    Replies: 18
    Last Post: 01-06-2006, 03:26 AM
  5. index array
    By kurz7 in forum C Programming
    Replies: 9
    Last Post: 04-24-2003, 08:57 AM