C++で別の配列の順序に従って配列を並べ替える方法

問題の概要

この記事では、少し変わったソートの問題を取り上げます。2つの配列 A1 と A2 が与えられたとき、A1 を「A2 で定義された相対的な順序」に従って並べ替えます。A2 に存在しない要素は、並べ替えられた要素の後ろに続けて配置します。

たとえば、次のような配列を考えてみましょう。

A1 = {2, 1, 2, 1, 7, 5, 9, 3, 8, 6, 8}
A2 = {2, 1, 8, 3}

ソート後、A1 は次のようになります。

A1 = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}

A2 に含まれる要素（2, 1, 8, 3）は A2 の出現順に並び、それ以外の要素（5, 6, 7, 9）は昇順で後ろに追加されているのがわかります。

比較関数の設計方針

この問題を解くには、標準の大小比較の代わりに独自の比較関数を用意します。比較のルールは次のとおりです。

• num1 と num2 がどちらも A2 に存在する場合：A2 におけるインデックスが小さい方を「小さい」値として扱います。
• 片方だけが A2 に存在する場合：A2 に存在する方を「小さい」値として扱います。
• どちらも A2 に存在しない場合：通常の数値の大小関係（昇順）で比較します。

アルゴリズム

compare(num1, num2):
開始
　　もし num1 と num2 の両方が A2 に存在するなら
　　　　return num1 のインデックス − num2 のインデックス
　　そうでなく num1 だけが A2 に存在するなら
　　　　return -1
　　そうでなく num2 だけが A2 に存在するなら
　　　　return 1
　　それ以外（どちらも A2 に存在しない）
　　　　return num1 − num2
終了

C++による実装例

比較関数の中から A2 を参照できるよう、A2 をグローバル変数として定義しています。qsort にこの比較関数を渡すことで、目的の順序で並べ替えが行われます。

#include<iostream>
#include<algorithm>
using namespace std;

const int MAX_SIZE = 100;
int A2[MAX_SIZE]; // 比較関数内で参照するグローバル配列
int a2Size = 0;

// key が A2 の何番目にあるかを返す（見つからなければ -1）
int searchIndex(int key){
　　for(int i = 0; i < a2Size; i++){
　　　　if(A2[i] == key)
　　　　　　return i;
　　}
　　return -1;
}

// カスタム比較関数
int compare(const void *num1, const void *num2){
　　int index1 = searchIndex(*(int*)num1);
　　int index2 = searchIndex(*(int*)num2);
　　if(index1 != -1 && index2 != -1)
　　　　return index1 - index2;              // 両方ある場合は A2 のインデックス順
　　else if(index1 != -1)
　　　　return -1;                           // num1 だけ A2 にあるなら num1 を先に
　　else if(index2 != -1)
　　　　return 1;                            // num2 だけ A2 にあるなら num2 を先に
　　else
　　　　return (*(int*)num1 - *(int*)num2);  // どちらもなければ昇順
}

int main(){
　　int data[] = {2, 1, 2, 1, 7, 5, 9, 3, 8, 6, 8};
　　int n = sizeof(data)/sizeof(data[0]);
　　int a2[] = {2, 1, 8, 3};
　　a2Size = sizeof(a2)/sizeof(a2[0]);

　　for(int i = 0; i < a2Size; i++){
　　　　A2[i] = a2[i];
　　}

　　qsort(data, n, sizeof(int), compare);

　　for(int i = 0; i < n; i++){
　　　　cout << data[i] << " ";
　　}
　　return 0;
}

実行結果

2 2 1 1 8 8 3 5 6 7 9

計算量と改良のポイント

qsort によるソートの計算量は O(n log n) ですが、この実装では比較のたびに A2 を線形探索（O(m)）しているため、全体の計算量は O(n・m・log n) になります。A2 の要素とインデックスをあらかじめ unordered_map などのハッシュマップに登録しておけば、探索を O(1) に抑えられ、全体で O(n log n) まで高速化できます。要素数が多いデータを扱う場合は、この改良を検討するとよいでしょう。