c++ - ソート後のインデックス順列を取得する方法

Question

配列arr = {5, 16, 4, 7}を指定すると、それを並べ替えることができますsort(arr, arr+sizeof(arr)/sizeof(arr[0]))。したがって、配列arr = {4, 5, 7, 16}と並べ替えられた配列の順列インデックスは です{2, 0, 3, 1}。つまり、arr[2]元の配列の は、ソートされた配列の中で最小の要素になりました0。

順列インデックスを取得できる効率的な方法はありますか?

ありがとうございました

Answer 1

インデックスの配列を作成し、0..N-1 の数字で埋め、カスタム コンパレータを使用して並べ替えます。lhsコンパレータは、元の配列のインデックスとのアイテムを比較する必要がありますrhs。この方法でインデックスの配列をソートすると、順列として並べ替えられます。

vector<int> data = {5, 16, 4, 7};   
vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
    index[i] = i;
}
sort(index.begin(), index.end(),
    [&](const int& a, const int& b) {
        return (data[a] < data[b]);
    }
);
for (int i = 0 ; i != index.size() ; i++) {
    cout << index[i] << endl;
}

これは印刷します2, 0, 3, 1

これはideoneのデモです。

注: を使用して、ソートされた順序でindex取得できます。data

for (int i = 0 ; i != index.size() ; i++) {
    cout << data[index[i]] << endl;
}

Answer 2

C++ では、ペア データ型を使用してこれを簡単に行うことができます。以下のサンプルコード。

arr = {5, 16, 4, 7};
vector<pair<int,int> >V;
for(int i=0;i<4;i++){
    pair<int,int>P=make_pair(arr[i],i);
    V.push_back(P);
}

sort(V.begin(),V.end());

したがって、V[i].first は i 番目の値で、V[i].second は i 番目のインデックスです。したがって、ソートされた配列のインデックスを出力します。

for(int i=0;i<4;i++)cout<<V[i].second<<endl;

ペア項目の配列 (またはベクトル) をソートする際、配列は最初の値に基づいて最初にソートされることに注意してください。2 つのペアの最初の値が同じ場合、2 番目の値に基づいて並べ替えられます。