Re: Sorting elements *and* knowing where each one has been put
On Fri, Jan 29, 2010 at 6:08 PM, Merciadri Luca
<Luca.Merciadri@student.ulg.ac.be> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi,
>
> I have some numerical values, i.e. something like
>
> ==
> value_1
> value_2
> .
> .
> .
> value_n
> ==
>
> There are many ways to sort them, but the `sort' command is clearly
> appropriate.
>
> The problem is that I need to know where value_i is, before, and
> after, the sorting. It can be found easily by keeping in memory where
> value_i is before the sorting (for every i, 1<=i<=n), and finding
> where value_i is after the sorting, by looking in the sorted numbers
> and finding value_i. However, this solution, despite being simple, is
> clearly bad on an algorithmic point of view. The best way is
> consequently to use the sorting function (which could be, e.g. a
> Heapsort, or simply the `sort' command) to know where value_i is
> displaced once it has been transformed by the sorting function.
>
> However, I do not know how I can do this with the `sort' function. Is
> it even possible? (I considered 1<=i<=n through the whole message.)
In the discussion above you persist in mixing the sort function with
the sort command. They are not the same, so please be more careful in
your descriptions of what it is you want to accomplish.
To sort with a function, such as is found in many programming
languages, you should create a data structure containing the value to
be sorted (the "key") and any audit/trance information you need about
the position of each item prior to the sort. After sorting such data
structures with the language's sort() function you will be able to
identify where each value started and ended.
To sort with a command, such as is found in many command-line
envoronments, you should create lines of text, each containing the
value to be sorted (the "key") and followed by any audit/trace
information you need about the position of each item prior to the
sort. After sorting the text lines with the command-line
environment's text sorting utility you will be able to identify where
each value started and ended.
The above descriptions answer the question you asked. But it appears
to me that the answer you need is related to a different question.
What do you need to do with the values after they are sorted? If you
have both the initially ordered list and the sorted list, why do you
care where things started as long as they are where they need to be
when you are done?
-- Lee
Reply to: