On Friday 29 January 2010 17:08:00 Merciadri Luca wrote: > 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.)
nl values | sort -k2 | nl | grep value_i The first column is the new location, 1-based. The second column is the old location, 1-based. If your values are numbers, you might use (awk '$3 == value_i') instead of the grep. nl = O(n) sort = O(n lg n) grep = O(n) The whole pipeline is therefore O(n lg n). -- Boyd Stephen Smith Jr. ,= ,-_-. =. b...@iguanasuicide.net ((_/)o o(\_)) ICQ: 514984 YM/AIM: DaTwinkDaddy `-'(. .)`-' http://iguanasuicide.net/ \_/
signature.asc
Description: This is a digitally signed message part.
