C++で配列のソート後にソート前のインデックスを返すには

Question

int v[5] = {3,2,5,7,1}
//sort後
v[5] = {1,2,3,5,7}

この時，配列の中身ではなくソート前の添字の値がほしいです．上の例だと求めている答えは{4,1,0,2,3}です．自分で調べてみましたが記事などからは理解することが出来なかったので，C++初心者にもわかるように教えていただけたら幸いです．よろしくお願いします．

Answer 1

ソート結果を配列のインデックスで得るのは、argsort といったりします。
インデックスを保持する配列を作成し、その配列を値の配列に基づき、ソートすることで、実現できます。

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

int main()
{
    std::vector<int> array = {3, 2, 5, 7, 1};

    // 配列のインデックス indiecs = {0, 1, 2, 3, 4} を作成する。
    std::vector<size_t> indices(array.size());
    std::iota(indices.begin(), indices.end(), 0);

    // ソートする。
    std::sort(indices.begin(), indices.end(), [&array](size_t i1, size_t i2) {
        return array[i1] < array[i2];
    });

    for (auto v : indices)
        std::cout << v << " ";
    std::cout << std::endl;
}

4 1 0 2 3 

Answer 2

私もy_waiwaiさんに賛成。

私なら

(元の)要素番号 と データをひとまとめにした構造体 ( クラスでもいいけど。 )を用意する。

struct Data{
       int ex_pos; // 元の位置
       int num; // 実際のデータ
};

この構造体の配列を用意。

Data d[5];

この構造体配列 d にセットしていく。

// 最初はex_posにセット
for( int i = 0; i < 5; i++ ){
      d[i].ex_pos = i; // 1,2,3,...となるようにする
}

// 実際のデータを入れていく
d[0].num = 5;
d[1].num = 4;
d[2].num = 0;
... // 配列の末尾まで行う

で、バブルソートだったり、C++の STLの std::sortだっけ? あれでソートする。(d::num を基準として。)

すると

d[0] : 2, 0
d[1] : 3, 1
d[2] : 4, 2
...

のような感じで元の位置の番号を保持したまま動かせる。

仕様によってはクラスが保持することもあるし、一括で

int n[] = { 1, 2, 3, 4, 5 };

のやつみたいにする場合もあるが、ロジックに関しての質問なので適当。

Answer 3

ソートをしてしまうとソート前の情報は失われるので、
ソート前の配列を残しておく、
あるいはソート前のインデックスを含めた構造体の配列として構成してそれをソートする
などの手段が必要となります