sort indices

[Marc Schellens]

I want to get the sort indices of an valarray<type>
ie.
for type int and array

valarray<int> a( 0, 4);
a[0] = 7,
a[1] = 2,
a[2] = 9,
a[3] = 4,
I want to get as output a valarray<long> res
with:
res[0] == 1 // index of '2' first el
res[1] == 3 // 4 2nd el
res[2] == 0 // 7 3rd el
res[3] == 2 // 9 last el

All the sort* algorithms sort the array itsef, how
to get those indices most easily?
Speed is an issue.

Thanks,
Marc

[Karl Heinz Buchegger]

Marc Schellens wrote:

I want to get the sort indices of an valarray<type>
ie.
for type int and array

valarray<int> a( 0, 4);
a[0] = 7,
a[1] = 2,
a[2] = 9,
a[3] = 4,

I want to get as output a valarray<long> res
with:
res[0] == 1 // index of '2' first el
res[1] == 3 // 4 2nd el
res[2] == 0 // 7 3rd el
res[3] == 2 // 9 last el

All the sort* algorithms sort the array itsef, how
to get those indices most easily?

By modifying the sort criterium to take this
indirection into account.

You start with an res array of
res[0] = 0;
res[1] = 1;
res[2] = 2;
res[3] = 3;

and sort that. But when the sort algorithm compares comes
to the part when the comparison of array entries is done,
you don't compare res[i] with res[j], but instead
you compare a[res[i]] with a[res[j]]

That's all. It's really very simple.

--
Karl Heinz Buchegger
kb******@gascad.at

[Marc Schellens]

Karl Heinz Buchegger wrote:

Marc Schellens wrote:

I want to get the sort indices of an valarray<type>
ie.
for type int and array

valarray<int> a( 0, 4);
a[0] = 7,
a[1] = 2,
a[2] = 9,
a[3] = 4,

I want to get as output a valarray<long> res
with:
res[0] == 1 // index of '2' first el
res[1] == 3 // 4 2nd el
res[2] == 0 // 7 3rd el
res[3] == 2 // 9 last el

All the sort* algorithms sort the array itsef, how
to get those indices most easily?

By modifying the sort criterium to take this
indirection into account.

You start with an res array of
res[0] = 0;
res[1] = 1;
res[2] = 2;
res[3] = 3;

and sort that. But when the sort algorithm compares comes
to the part when the comparison of array entries is done,
you don't compare res[i] with res[j], but instead
you compare a[res[i]] with a[res[j]]

That's all. It's really very simple.

Well, ahem...
thanks,
Marc

[tom_usenet]

On Wed, 11 Aug 2004 18:07:07 +0900, Marc Schellens
<m_*********@hotmail.com> wrote:

I want to get the sort indices of an valarray<type>
ie.
for type int and array

valarray<int> a( 0, 4);
a[0] = 7,
a[1] = 2,
a[2] = 9,
a[3] = 4,
I want to get as output a valarray<long> res
with:
res[0] == 1 // index of '2' first el
res[1] == 3 // 4 2nd el
res[2] == 0 // 7 3rd el
res[3] == 2 // 9 last el

All the sort* algorithms sort the array itsef, how
to get those indices most easily?
Speed is an issue.

An alternative to Karl's suggestion is to use a valarray<int*> (where
each element is the address of the equivalent element in the original
valarray), sort that using a comparator that dereferences the values
before comparing them, and then copy the resulting array into your
result, with the index of an element being
res[i] = sorted[i] - &a[0];

Tom