CODEWITHSUNDEEP
c++arraysalgorithmsorting
user98235
user98235

Reputation: 896

Keeping the order of the array in check in C++

There are a lot of algorithms that do sorting in an efficient way, and I was wondering if there are efficient ways of outputting the order of the array after sorting.

For instance, let's say we have

a[5]= {1, 7, 5, 4, 10}

so a[0]=1, a[1]=7, a[2]=5, a[3]=4, a[4]=10

then after sorting it becomes

{1, 4, 5, 7, 10}, but instead of {1, 4, 5, 7, 10} being the output,

let's assume we want {0, 3, 2, 1, 4} as the output

(as {1=a[0], 4=a[3], 5=a[2], 7=a[1], 10=a[4]} )

Is there an efficient way of doing it when the array is really large?

(or some data structure that helps doing it?)

Any help would be greatly appreciated.

Upvotes: 2

Views: 1228

Answers (4)

Apriori
Apriori

Reputation: 2306

You could make a seperate array of indices as you suggest. Initialize it to b[] = {0, 1, 2, 3, 4}. Then sort it. Except define your sort order as comparing the values of whatever is indexed. For instance comparing elements i and j would consist of a[b[i]] < a[b[j]]. When it's all done, b is "sorted" and a is unmodified. So you're only sorting one array, not two. You can do this by calling any standard sort algorithm and passing in your own compare function that does the "right thing" in your case, it can be a function-object if you need to hide a pointer to a in it.

For instance here is a simple implementation using lambdas in C++11:

  #include <algorithm>
  ...
  const unsigned a[] = { 1, 7, 5, 4, 10 };
  const unsigned s   = sizeof a / sizeof *a;

  unsigned b[s];
  std::for_each(b, b + s, [&](unsigned &n){ n = &n - b; });
  std::sort(b, b + s, [&](unsigned lhs, unsigned rhs){return a[lhs] < a[rhs]; });

After the call: b[] = {0, 3, 2, 1, 4} and a is unmodified.

Upvotes: 0

wallyk
wallyk

Reputation: 57774

Decades ago I produced a revised qsort() to:
1. take a swap function parameter (in addition to the compare function parameter)
2. modified both parameter function parameters to take indexes (of the array) rather than pointers

With these modifications, it is easy to handle an array of indexes which, when the sort is done, is exactly the result you want:

int data[N];  // the data to reorder
int indices[N];
for (int j = 0;  j < N;  ++j)  indices [j] = j;

int cmp_f (int j1, int j2)
{
     return data [indices[j1]] - data [indices[j2]];
}

void swap_f (int j1, int j2)
{
     int t = indices [j1];
     indices [j1] = indices [j2];
     indices [j2] = t;
}

Upvotes: 1

Baum mit Augen
Baum mit Augen

Reputation: 50053

It can easily be done with an vector of std::pairs:

std::vector<std::pair<int,std::size_t>> toSort = {{value1,0},{value2,1}};
std::sort(toSort.begin(),toSort.end());

Then you can just output toSort[i].second for all elements of the vector. Note that std::pair overloads operator< on a sensible way which is why you do not need to provide a custom compare function. This is just as efficient as a stable sort, and elements of the same value will keep their original order.

Upvotes: 3

kraskevich
kraskevich

Reputation: 18556

You can sort an array of pairs(value, initial index).

Upvotes: 1

Related Questions