undo sorting of nsarray

Question

Here is a example of what I want to do with NSArray contains NSNumber.

1. This is the NSArray "score" I want to edit.
   score[0]=30,
   score[1]=10,
   score[2]=20
   score[3]=0
   

2. Sort the Array in ascending-order
   score[0]=30 //[0]This number shows the index before sorting the array
   score[1]=20 //[2]
   score[2]=10 //[1]
   score[3]=0 //[3]
   

3. Edit the Array(In this case,4th gives 1st 10 points,and 3rd gives 2nd 5points)
   score[0]=40 //[0]
   score[1]=25 //[2]
   score[2]=5 //[1]
   score[3]=-10 //[3]
   

4. And sort the array back they were.
   score[0]=40
   score[1]=5
   score[2]=25
   score[3]=-10
   

   I have a problem with no.4 method in the list.Can someone give me some idea with this?
   Thanks in advance.

Answer 1

[Code will be typed in, check it!]

I assume your score array is actually mutable as you intend to alter it:

NSMutableArray *score = ...;

Create another array the same size and initialized to 0..n:

NSMutableArray *indices = [NSMutableArray arrayWithCapacity:[score count]];
// add the numbers 0..[score count] to indices

Now sort the indices array using a custom comparator which looks up the score array:

[indices sortUsingComparator:(NSComparator)^(NSNumber *a, NSNumber *b)
 {
    return [((NSNumber *)[[score objectAtIndex:[a integerValue]])
            compare:[[score objectAtIndex:[b integerValue]]
           ];
 }
]

Now you can modify your original array via the indices array, e.g. to modify the "4th" element after the source:

[score replaceObjectAtIndex:[[indices objectAtIndex:3] integerValue] withObject:...];

Now you don't need to "unsort" score at all, your step 4 is "do nothing".

Answer 2

You don't actually need to swap the values themselves, you can set up an extra level of indirection and use that.

Before the sort, you have the indexes initialised to point to the corresponding scores:

index[0] = 0      score[0] = 30
index[1] = 1      score[1] = 10
index[2] = 2      score[2] = 20
index[3] = 3      score[3] =  0

When you sort, you actually sort the indexes based on the scores they point to rather than the scores themselves. So, instead of the following comparison in your sort:

if score[i] > score[i+1] then swap score[i], score[i+1]

you instead use:

if score[index[i]] > score[index[i+1]] then swap index[i], index[i+1]

Following the sort, you then have:

index[0] = 0      score[0] = 30
index[1] = 2      score[1] = 10   \ These two indexes have been swapped
index[2] = 1      score[2] = 20   /   but NOT the scores.
index[3] = 3      score[3] =  0

Then, to move points, you use the indirect indexes rather than the direct values:

score[index[0]] += 10; score[index[3]] -= 10;
score[index[1]] +=  5; score[index[2]] -=  5;

Then you throw away the indexes altogether, the original array doesn't need restoration to its original order, simply because its order was never changed.

Answer 3

Make an additional array initialized as such:

index[0] = 0
index[1] = 1
index[2] = 2
:

And every time your sorting algorithm swaps two indices in score, you also swap the same indices in index.

In case your sorting algorithm is built-in, so that you have no control over it, you will have to replace each score with a tuple (an object, a two-element array, whichever is easier in objective-c), where on element is the score, and the other element is its original index. When you sort, you would pass a custom comparator to the sorting function, so that only the score is used for comparison. That would sort your score-index tuples, so that you can use the index to restore them to original order.