Sorting application difficulty

Question

Currently I am reading a book on algorithms and found this usage of sorting.

Reconstructing the original order - How can we restore the original arrangment of a set of items after we permute them for some application? Add an extra field to the data record for the item, such that i-th record sets this field to i. Carry this field along whenever you move the record, and later sort on it when you want the initial order back.

I ve been trying hard to understand what does it mean. And I failed miserably. Pls somebody help?

Answer 1

Well, basically it's saying that you need some sort of thingy to keep track of the original order (which is destroyed by the permutation). One option would be to simply reverse the permutation (check out Steve Jessop's infrmative answer here).

Another option to invert the permutation would require fewer processing steps, but more memory. More specifically, each node in your input set would have an extra ID field, and all the elements in this input set are sorted based on this field. Once you apply the permutation, it's obvious that the IDs are no longer in a sorted order. If you wish to invert the permutation, all you have to do is sort the list again based on this field.

Answer 2

Suppose you have list of items in random order:

itemC, itemB, itemA, itemD

you sorted them up:

itemA, itemB, itemC, itemD

and you didn't have enough memory to store them in a separate location, so original sequence is lost. Moreover, original order is random and it will be problematic/impossible to restore it.

This article gives a solution to this problem.

Add an extra field to the data record for the item, such that i-th record sets this field to i

So, we add an extra field for each of the items:

(itemC,1), (itemB,2), (itemA,3), (itemD, 4)

And after sort we have:

(itemA,3), (itemB,2), (itemC,1), (itemD, 4)

So we can easily restore initial order sorting by additional field

Answer 3

Let's say you have the data in an array, because it's the simplest structure that I can use to exemplify.

So, your node (i.e., element of the array) may look like this:

 (some data type) data

The algorithm is suggesting you to add an integer field, so it looks like this:

 (some data type) data,
 int              position

And then, you fill the positions with the actual index. Something like this pseudocode:

for current: 0 to lastElement
  array[current].position = current

(that's not written in any language I know of, but it should be readable)

After doing that, you shuffle it (resort it) for whatever you need to.

When you want to restore the original ordering, all you need to do is sort by the position field.