どうも。初投稿のなので生暖かい目で見てください。
競プロで必要になったので、自分でぐぐったりしつつ一番自分的に簡単だと思った方法をメモも兼ねて書いておきます。
インデックスソートとは？
専門用語として正しい使い方なのかはわかりませんが、とりあえずここで言う「インデックスソート」の定義を書いておきます。
一言で言えば、「配列をソートしたとき、ソート後の配列に対応する（元の配列の）インデックスの並びを得る操作」となります。
...はい、意味分かりませんね。説明下手で申し訳ありません。
具体例で見るのが早いですね。例えば、次のような配列(文字列)を考えます。
char str[] = "bcad";
// str[0] = b
// str[1] = c
// str[2] = a
// str[3] = d
これを昇順にソートすると、"abcd"が得られます。このとき、各要素のインデックスも同時に並び替えるとどうなるか考えます。
つまり、各要素の上にインデックスを書いて
0123
bcad
とします。ここで下の文字列をソートする際、上に書いてあるインデックスもセットで移動させると、ソート後は
2013
abcd
となります。ここで上の行に現れた"2013"が、「"bcad"をインデックスソートして得られた（インデックスの）配列」となります。
どんなときに使うの？
例えば、元の配列に破壊的変更を及ぼさずにソートしたいときに使えます。C++のsort()関数は配列そのものを変更してしまいますからね。
尤も上記のケースは、配列のコピーを行えば済む話です。しかしもっと本質的に、「ソート後の配列に対応する（元の配列の）インデックスの配列が必要」（そのまんまｗ）な場合もあります。
これは何というか説明が面倒くさいので、例えば下の問題なんかで必要になります（雑）
https://atcoder.jp/contests/abc009/tasks/abc009_3
どうやるか？
比較関数の定義
ぐぐると結構色々なやり方が出てきますが、「比較関数をうまく自作する」という基本的なところは一致しています。
ただ、見るとどれもファンクタとか物々しい道具を使っていて、僕みたいな雑魚は「(´Д｀)ウヘァ」となってしまうので、ラムダ式とテンプレート関数だけでサクッと書く方法を考えてみました。
template<class T>
auto comp_idx(T* ptr){
return [ptr](int l_idx, int r_idx){
return ptr[l_idx] < ptr[r_idx];
};
}
解説します。まず注意して頂きたいのは、これは「比較関数」そのものではなく、「比較関数を返す関数」であるということです。
引数としては、ソート対象の配列（の先頭要素へのポインタ）を渡します。これはテンプレート関数なので、配列の要素の型はコンパイラが型推論してくれます。
後でまた述べますが、sort()関数の第三引数に渡すのは、この関数そのものではなく、この関数が返す比較関数です。
比較関数の部分はラムダ式で書かれています。この比較関数が引数に取るのは、配列のインデックスです。
この比較関数は、受け取った配列へのポインタを使って配列の要素にアクセスし、要素同士を比較した結果を返します。
使い方
例えば、次のように使います（先程の例に対応しています）。
#include<cstdio>
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
using namespace std;
//比較関数（を返す関数）
template<class T>
auto comp_idx(T* ptr){
return [ptr](int l_idx, int r_idx){
return ptr[l_idx] < ptr[r_idx];
};
}
int main(){
char str[] = "bcad";
int l = strlen(str);
//インデックスの配列を準備
int idx[l];
REP(i,l){
idx[i] = i;
}
//ソート前
cout << "before:" << endl;
REP(i,l){
cout << idx[i];
}
cout << endl;
REP(i,l){
cout << str[idx[i]];
}
cout << endl << endl;
//インデックスソート
sort(idx, idx+l, comp_idx(str));
//ソート後
cout << "after:" << endl;
REP(i,l){
cout << idx[i];
}
cout << endl;
REP(i,l){
cout << str[idx[i]];
}
cout << endl << endl;
//元の配列
cout << "original:" << endl;
cout << str << endl;
return 0;
}
結果は以下のようになります。
before:
0123
bcad
after:
2013
abcd
original:
bcad
元の配列は変更されず、インデックスの配列だけがソートされていることが分かります。