Is there any unsorting algorithm. Given a multiset U =
{a1,a2,a3,...,an} that are randomly ordered. Applying a sorting
algorithm we would get a sorted multiset S = {b1,b2,b3,...,bn} where
b1 >= b2, b2 >= b3 ... So my question is can I get back to U from S by
storing minimum information about U.

-- Nitin

Hi, njm!

As a computer programmer who was forced to study all kinds of
algorithms in school, I feel that I am able to address your question.

There is no "unsorting algorithm" as such, if the original sequence of
items was truly random.

An "undo" or "backout" algorithm could be employed to achieve the
results you describe. However, such an algorithm would require that
some kind of "snapshot" or pointer history of the randomly-ordered
elements be saved before your original sort was commenced, in order to
be able to revert to the original random order.

A "randomizing" algorithm could be employed to re-scramble the
elements, but the odds of getting the same original random order would
range from small (for a limited group of items) to infinitesimal (for
a very large group of items).

Before Rating my Answer, if you have questions or need additional
information, please post a Request for Clarification, and I will be
glad to see what I can do for you.

I hope this information has provided you with exactly what you needed!

aceresearcher

---

Clarification of Answer by aceresearcher-ga on 31 Oct 2002 10:28 PST

njm,

Having re-read my answer, I would like to clarify it:

You do not specify what you would consider "minimum information" about
the original sequence needed to restore it. However, any kind of
backout snapshot or pointer history would essentially have to store
the order of EVERY element in some way, if the original sequence is
truly random. So I would have to say "no", you cannot get back to U
from S using only minimal information; you would have to store quite
explicit information about its original order.

Before Rating my Answer, if you have questions or need additional
information, please post a Request for Clarification, and I will be
glad to see what I can do for you.
 
aceresearcher

perhaps you could say that sorting is a "lossy" process with respect
to the indexing information of the original set.  unless you know
something special about how they were ordered, their ordering
information is lost and you would have to store it explicitly.

are you getting at the fact that if you go from a nearly sorted list
to a fully sorted list, there are few moves, and therefore the reverse
mapping information might be stored with less information than a full
list of indexes?  interesting question...

Hi,
  If you have a requirement such that you need to go back after
sorting, add an addtional field with original data which can be called
say SL.No and will contain the serial no of original data item.
SlNo   Data
1       a1
2       a2
3       a3
......etc
When you want to sort, do sorting on data field. when you want to go
back(undo sort) do sort on the SL no field which will bring data to
original sequence.

Hope it helps.

RAC

Some thoughts. A previous commenter noted that you could store the
original order. For example unsorted dog, ape, and cat would be 1 2
and 3 respectively.  If an ape, cat and dog walked into the room (in
alphabetic order) and you were asked to "unsort" them, you would need
to know dog=1 ape=2 and cat=3. Essentually one stored "where they came
from".  It seems that it may use less information to store "where they
go" instead of "where they came from". Using "where they go" rather
than "where they came form" would only need to store the values 2,3
and 1 in an "unsort" list without any reference to the animal itself.
The unsort algorithm would be to take the first entry in the sorted
list(ape) and place it into the position indicated by the first value
in the unsort list(ape goes to unsorted spot 2)  The next sorted entry
(cat) would be put back into the unsorted position indicated by the
second value in the unsort list, etc. It would take a bit more work to
prepare such an unsort list, but once prepared, such a list would
simplify the unsort process itself.

Store Multiset U in a hashtable with indexing information originating
from the elements e.g. a(i) = 32 --> store at 32nd location OR
a(i)="Something" --> store at pointer pointing from an object
containing string "Something". If collisions occur, use link list to
store multiple similar elements at the same location, but the best way
is to use Hashtable object in java.util package.

OK, now once you sort the elements, if you want to unsort, just put
elements back to their places by indexing from the information that
comes from the element itself.

E.G.
Hashtable hash = new Hashtable();
hash.put(new String("32"), new Integer(32));
hash.put(new String("24"), new Integer(24));
hash.put(new String("27"), new Integer(27));
hash.put(new String("26"), new Integer(26));

sortAlgo(hash);
//hash --> 32,27,26,24

//unsort
Enumeration enum = hash.elements();
while(enum.hasMoreElements())
{
Integer next = (Integer)enum.nextElement();
hash.put(new String(String.valueOf(next.intValue())), next);
}