Showing the original index of an element in a vector after bubblesort

Question

I'm new to c++ and i'm having a problem with my code. I need to show the original indexes of a vector before it was sorted, after sorted. I tried it like this:

#include <vector>
using namespace std;

void bubblesort(vector<int> &a, int n) {
    for (int j = 0; j < n - 1; j++) {
        for (int i = n - 1; i > j; i--) {
            if (a.at(i) < a.at(i-1)) {
                int aux = a.at(i);
                a.at(i) = a.at(i-1);
                a.at(i-1) = aux;
            }
        }
    }

}

int main()
{
    int n;
    cout << "Digite o tamanho do vetor: ";
    cin >> n;
    vector<int> v;
    vector<int> vold;
    vector<int> pos;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
        vold.push_back(a);
    }

    bubblesort(v, n);

    for (int i = 0; i < n; i++) {
        if (vold.at(i) == v.at(i)) {
            pos.push_back(i);
        }
        else {
            for (int j = i+1; j < n - 1; j++) {
                if (vold.at(i) == v.at(j)) {
                    pos.at(j) = i;
                    break;
                }
                
            }
            
        }
    }

    for (const int& i : pos) {
        cout << i << "  ";
    }

    

    system("pause>0");
}

But it didn't worked, if someone could help me to see what I'm doing wrong I would be glad, thanks in advance.

Answer 1

If your goal is to show the indices of the sorted vector, then another approach is to not sort the original vector, but instead to sort a vector of index values based on the original vector.

The index vector would be initialized to 0, 1, 2, etc. up until the vector's size, minus 1.

Here is an example:

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

void bubblesort(std::vector<int> &a, std::vector<int>& index) 
{
    // Make sure the index vector is the same size as
    // the original
    index.resize(a.size());

    if ( a.size() <= 1 )
       return;

    // This is just a shortcut way of setting the values to 0,1,2,etc.
    std::iota(index.begin(), index.end(), 0);

    size_t n = a.size();

    // Here is your sort, but with one difference...
    for (size_t j = 0; j < n - 1; j++) 
    {
        for (size_t i = n - 1; i > j; i--) 
        {
            // Look at the comparison being done here using the index array
            if (a.at(index[i]) < a.at(index[i-1])) 
            {
                 // We swap the index values, not the values
                 // in the vector
                 int aux = index.at(i);
                 index.at(i) = index.at(i-1);
                 index.at(i-1) = aux;
            }
        }
    }
}

int main()
{
    std::vector<int> v = {3, 1, 65, 23, 4};
    std::vector<int> index;
    bubblesort(v, index);

    // Display the index values of the sorted items     
    for (const int& i : index) 
        std::cout << i << "  ";
}

Output:

1  0  4  3  2  

Note that the bubblesort function takes a vector of indices, and not n. There is no need to pass n, since a vector already knows its own size by utilizing the size() function.

The output shows the original index of each of the sorted items.