0

My attempt is rather cumbersome, and is basically just a modification of another sorting function

void heapify(vector<int> &v, vector<int> &indx, int n, int i) {
    int x{ i };
    int l{ 1 + (2 * i) };
    int r{ 2 + (2 * i) };

    if (n > l&& v[l] > v[x])
        x = l;
    if (n > r&& v[r] > v[x])
        x = r;
    if (x != i) {
        swap(v[i], v[x]);
        //keep track of indexes
        swap(indx[i], indx[x]);
        heapify(v, indx, n, x);
    }
}

void heapsort(vector<int> &v, vector<int> &indx, int n) {
    for (int i{ n / 2 - 1 }; i >= 0; --i)
        heapify(v, indx, n, i);
    for (int i{ n - 1 }; i >= 0; --i) {
        swap(v[0], v[i]);
        //keep track of indexes
        swap(indx[0], indx[i]);
        heapify(v, indx, i, 0);
    }
}

So, my question is, how does one modify standard std::sort() and saves all the indexes?

Recovery Email
  • 3
  • 3
  • Does this answer your question? [C++ sorting and keeping track of indexes](https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes) – MT756 Mar 10 '20 at 20:42
  • You shouldn't need to touch the original vector if you're sorting the indices. You then access the vector in a sorted fashion using `v[index[0]]`, for example, to get the first sorted item in vector `v`. – PaulMcKenzie Mar 10 '20 at 20:42

0 Answers0