How Can I Sort Data in C While Maintaining Original Indices?

Sorting Data while Preserving Original Positions in C

In C , the need often arises to sort a collection of elements while preserving their original positions. This is crucial when external factors depend on these positions.

Consider the sample set A = [5, 2, 1, 4, 3]. Sorting this set using the standard sort function would produce B = [1,2,3,4,5]. However, we also want to track the original indexes of the sorted elements, resulting in set C = [2, 1, 4, 3, 0], which indicates the index of each element in B within the original A.

Solution using C 11 Lambdas

C 11 lambdas provide a convenient way to solve this problem:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

template <typename T>
vector<size_t> sort_indexes(const vector<T> &amp;v) {
  // Initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // Sort indexes based on comparing values in v
  stable_sort(idx.begin(), idx.end(),
       [&amp;v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

In this implementation, we first create a vector idx with the original indexes. We then sort the indexes using stable_sort, ensuring that elements with equal values retain their relative order. The resulting vector idx contains the sorted indexes.

Usage

To use this function, simply pass in your vector of values and iterate over the sorted indexes:

for (auto i: sort_indexes(v)) {
  cout << v[i] << endl;
}

Customizations

The sort_indexes function can be customized to meet your specific requirements. For instance, you can provide your own original index vector, supply a custom sort function or comparator, or reorder v during sorting using an additional vector.

The above is the detailed content of How Can I Sort Data in C While Maintaining Original Indices?. For more information, please follow other related articles on the PHP Chinese website!