By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,190 Members | 802 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,190 IT Pros & Developers. It's quick & easy.

Sort in descending order with index

P: n/a
Hello,

I use this algorithm to sort an array "v" in the descending order.

void quickSort(float v[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0;
if (lo >= hi) return;
float mid = v[(lo + hi) / 2];

while (lo < hi)
{
while (lo<hi && v[lo] > mid) lo++;
while (lo<hi && v[hi] < mid) hi--;
if (lo < hi) swap(v,lo, hi);
}

if (hi < lo) swap(v, hi, lo);

quickSort(v, lo0, lo);
quickSort(v, lo == lo0 ? lo+1 : lo, hi0);
}

I would like to have an array "index" to order another array "z".

Example:
v = [ 5, 9, 7 ]
index = [ 1, 2, 0 ]
z = [ 1, 2, 3 ]

so...
for (i = 0; i<=2; i++)
cout<<z[index[i]];
Output: [ 2, 3, 1 ]

I would like to have index = [ 1, 2, 0 ]. How?
Thanks to everybody.

Luigi Napolitano
Jul 22 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a
Luigi Napolitano wrote:

[...]
I would like to have an array "index" to order another array "z".

Example:
v = [ 5, 9, 7 ]
index = [ 1, 2, 0 ]
z = [ 1, 2, 3 ]

so...
for (i = 0; i<=2; i++)
cout<<z[index[i]];
Output: [ 2, 3, 1 ]

I would like to have index = [ 1, 2, 0 ]. How?


// greater_indexed_t class template:
// a function object that compares indices according
// to the '>'-ordering of the indexed elements.

template <typename RAIterator>
struct greater_indexed_t
{
greater_indexed_t (RAIterator begin)
: _begin (begin) { }

template <typename Index>
bool operator () (Index i, Index j)
{
return _begin [i] > _begin [j];
}

private:
RAIterator _begin;
};

// greater_indexed function template:
// template parameter deduction simplifies usage.

template <typename RAIterator>
greater_indexed_t <RAIterator>
greater_indexed (RAIterator begin)
{
return greater_indexed_t <RAIterator> (begin);
}

// Test it:

#include <algorithm>
#include <ostream>
#include <iostream>

int main ()
{
int v [] = { 5, 9, 7, };
int index [] = { 0, 1, 2, };

std::sort (index, index + 3, greater_indexed (v));

for (unsigned i (0); i != 3; ++ i) std::cout << index [i] << ' ';
std::cout << '\n';
}
Jul 22 '05 #2

P: n/a
"Buster" <no**@none.com> ha scritto nel messaggio
news:cp**********@newsg3.svr.pol.co.uk...
// Test it:

#include <algorithm>
#include <ostream>
#include <iostream>

int main ()
{
int v [] = { 5, 9, 7, };
int index [] = { 0, 1, 2, };

std::sort (index, index + 3, greater_indexed (v));

for (unsigned i (0); i != 3; ++ i) std::cout << index [i] << ' ';
std::cout << '\n';
}


Thanks for your reply, but it was very simple...

int main()
{
int v[] = { 5, 9, 7 };
int index[] = { 0, 1, 2 };

for (int i = 0; i < v.length; i++)
index[i] = i;

quickSort(v, index, 0, v.length-1);
}

void quickSort(float v[], int index[], int lo0, int hi0)
{
...
swap(v, index, hi, lo);
...
}

void swap(float v[], int index[], int i, int j)
{
...
int t;
t = index[i];
index[i] = index[j];
index[j] = t;
}

So, I have index[] = { 1, 2, 0 }.
Jul 22 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.