複雑なソートをしたい場合はインデックスだけで管理した方がいいかも

A = [3, 1, 4, 5]
B = [2, 7, 1, 8]

　これを、$A$ が昇順になるように $B$ も一緒に並べ替えたいというときはあります。平面走査 をするときなどが代表的です。

ソート後のイメージ

A = [1, 3, 4, 5]
B = [7, 2, 1, 8]

　一番簡単な方法は、ペアにしてソートすることです。

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

int main() {
    // 初期データ
    std::vector<int> a = {3, 1, 4, 5};
    std::vector<int> b = {2, 7, 1, 8};

    // 対応する a[i] と b[i] をペアにして vector に格納
    std::vector<std::pair<int, int>> pairs;
    for (std::size_t i = 0; i < a.size(); ++i) {
        pairs.emplace_back(a[i], b[i]);
    }

    // a をキーとして昇順にソート（pair の first に基づいてソートされる）
    std::sort(pairs.begin(), pairs.end());

    // 結果の表示
    for (const auto& [ai, bi] : pairs) {
        std::cout << "(" << ai << ", " << bi << ") ";
    }
    std::cout << std::endl; 
    // (1, 7) (3, 2) (4, 1) (5, 8) 
    
    return 0;
}

　インデックス番号を持たせたっていい（けんた食堂風）。

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

int main() {
   std::vector<int> a = {3, 1, 4, 5};
   std::vector<int> b = {2, 7, 1, 8};

   // a, b, インデックスをまとめてタプル化
   std::vector<std::tuple<int, int, int>> t;
   for (int i = 0; i < static_cast<int>(a.size()); ++i) {
       t.emplace_back(a[i], b[i], i);
   }

   // タプルをソート（a[i] 昇順 → b[i], i の順で辞書式にソートされる）
   std::sort(t.begin(), t.end());

   // 出力
   for (const auto& [ai, bi, idx] : t) {
       std::cout << "idx" << idx+1 << ":" << "(" << ai << ", " << bi << ") ";
   }
   std::cout << std::endl;
   // idx2:(1, 7) idx1:(3, 2) idx3:(4, 1) idx4:(5, 8) 

   return 0;
}

　しかし、この記事では、ペア配列やタプル配列を作るよりも、インデックス配列を別に用意した方が、場合によっては利点が多い という話をします。

　おおまかな利点として、

• インデックス番号を保持できる
• 大きなデータ構造の配列を作らなくていい
• 元の配列をいじらないのでなんとなく安心

　という点があります。

　実装例。

c++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // iota のために必要

int main() {
    // 配列 a, b を用意（a をキーにして並び替えたい）
    std::vector<int> a = {3, 1, 4, 5};
    std::vector<int> b = {2, 7, 1, 8};

    // 0, 1, 2, 3 のインデックスを生成
    std::vector<int> indices(a.size());
    std::iota(indices.begin(), indices.end(), 0); // indices = {0, 1, 2, 3}

    // a[i] が昇順になるように indices を並べ替える
    std::sort(indices.begin(), indices.end(), [&](int i, int j) {
        return a[i] < a[j];
    });

    // ソート後のインデックスの表示（確認用）
    std::cout << "ソートされたインデックス: ";
    for (int i : indices) {
        std::cout << i << " ";
    }
    std::cout << std::endl; // 1 0 2 3

    // a[i] を indices に従って並べ替えた結果の表示
    std::cout << "並べ替え後の a: ";
    for (int i : indices) {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl; // 1 3 4 5

    // b[i] を indices に従って並べ替えた結果の表示
    std::cout << "並べ替え後の b: ";
    for (int i : indices) {
        std::cout << b[i] << " ";
    }
    std::cout << std::endl; // 7 2 1 8

    return 0;
}

　Python も。

python

def main():
    # 配列 a, b を用意（a をキーにして並び替えたい）
    a = [3, 1, 4, 5]
    b = [2, 7, 1, 8]

    # 0, 1, 2, 3 のインデックスを生成
    indices = list(range(len(a)))  # [0, 1, 2, 3]

    # a[i] が昇順になるように indices を並べ替える
    indices.sort(key=lambda i: a[i])

    # ソート後のインデックスの表示（確認用）
    print("ソートされたインデックス:", indices)  # [1, 0, 2, 3]

    # a[i] を indices に従って並べ替えた結果の表示
    print([a[i] for i in indices]) # [1, 3, 4, 5]

    # b[i] を indices に従って並べ替えた結果の表示
    print([b[i] for i in indices]) # [7, 2, 1, 8]


if __name__ == "__main__":
    main()

活用例

要点：$(x,y)$ 平面上で与えられた点を単調増加になるように並べてあとは除外したときに、残る点のインデックス番号を答えよ

1. 片方の配列でソートする
2. 必要な処理を行う
3. ソート前のインデックス番号を復元する

　という手順が必要になります。とくに、3 番目の インデックス番号の復元 が手間で、これをひとつの配列で行うには vector<tuple<int,int,int>> などの全部載せ配列が必要になります。

　インデックス配列を別に持つと、ここら辺の問題をいい感じに解決できます。

// 俺流マクロ増し増し
 int main(){
    int n;
    cin >> n;
    vector<int> a(n),c(n);
    rep(i,n){
        cin >> a[i] >> c[i];
    }
    vector<int> indices(n);
    iota(all(indices),0);
    auto f=[&](int i,int j){
        return a[i]<a[j];
    };
    sort(all(indices),f);
    vector<int> st;
    for(int idx:indices){
        while(st.size() && c[st.back()-1]>c[idx]){
            st.pop_back();
        }
        st.push_back(idx+1);
    }
    sort(all(st));
    cout << st.size() << endl;
    cout << st << endl;
}

　ポイントとしては、スタックにいれるのは 「値そのもの」ではなく「値を参照するインデックス」 になっているという点です。これにより、値を比較するという目的と、インデックスを保つという目的を同時に達成することができます。

　また、持つデータ構造も vector<int> といったかたちで、限りなくシンプルにすることができます。これについては、見た目がシンプルになるというメリットが主で、高速になったり総合的なメモリを節約できたりはしない点に注意が必要ですが。（インデックス経由になるので、「シンプル」ではなくなると感じる人も多いかもしれません）

トリッキーなソートができる

　$(a,b)$ をソートするとき、$a$ は昇順で、$b$ は降順でやりたいという場合はあります。その場合、pair ソートする場合は $(a,-b)$ でソートすることでも実現可能ですが、元データをいじるのでなんとなく気持ち悪いです。

　また、$(a,b)$ が重複なし（distinct）でない場合は、その場合の処理も考慮する必要があります。問題の設定によっては、番号が若い方を優先したい場合もあれば、その逆もありえます。これも、$( \pm a, \pm b, \pm i)$（複号は同順とは限らない）のタプルを利用するなどして対策可能ですが、どんどんデータが肥大化していくきらいは否めません。

　しかし、こういった状況でも、ソート関数をカスタマイズすれば、元データを改変しない状態で、トリッキーなソートに対応できます。特に、distinct が保証されない状況では昇順、降順を厳密に考えないといけないことが多いので、ソート関数の段階でそれらを調整できるのは、慣れてくれば大きなメリットになります。

　以下のような比較関数を使います。

    auto f=[&](int i,int j){
        if(x[i]!=x[j]){
            return x[i]<x[j];
        }else if(y[i]!=y[j]){
            return y[i]<y[j];
        }else{
            return i<j;
        }
    };

　これも、広い意味では「オリジナルのインデックスを保存している」ことのメリットのひとつと言えます。

おまけ：順列である場合

　入力が順列（$1,2,3,...,N$ の並び替え）である場合は、わざわざソート関数をつくるまでもないです。

　その場合は、逆関数がそのままソート済インデックスとなります。

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

int main() {
    int n;
    std::cin >> n;

    std::vector<int> p(n);     // 長さ n の順列 p（0-indexed に変換して格納）
    std::vector<int> inv(n);   // inv[i] = p[i] = j ならば inv[j] = i を満たす逆写像

    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
        p[i]--;            // 入力が 1-indexed の場合に備え、0-indexed に補正
        inv[p[i]] = i;     // 値 p[i] が現れるインデックス i を記録
    }

    std::vector<int> idx(n);    // インデックスのリスト [0, 1, ..., n-1]
    std::iota(idx.begin(), idx.end(), 0); // idx = [0, 1, ..., n-1]

    // 比較関数：p の値が小さい順にインデックスを並び替える
    auto compare = [&](int i, int j) {
        return p[i] < p[j];
    };

    std::sort(idx.begin(), idx.end(), compare);

    // 並び替えたインデックス idx が inv と一致することを確認
    assert(idx == inv);
}