C++の別の配列で定義された順序に従って配列を並べ替えます

このセクションでは、別のソートの問題が発生します。 2つの配列A1とA2があるとします。要素間の相対的な順序がA2の場合と同じになるように、A1を並べ替える必要があります。一部の要素がA2に存在しない場合、それらはソートされた要素の後に追加されます。 A1と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}

この問題を解決するために、カスタム比較メソッドを作成します。このメソッドは、要素を比較して配列に配置します。比較ロジックは以下のようになります-

• num1とnum2の両方がA2にある場合、A2のインデックスが低い数値は、他の数値よりも小さいものとして扱われます。
• num1またはnum2のいずれかがA2に存在する場合、その数は、A2には存在しないもう一方よりも小さいものとして扱われます。
• 両方がA2に存在しない場合は、自然順序付けが使用されます。

アルゴリズム

compare(num1, num2):
Begin
   if both num1 and num2 are present in A2, then
      return index of num1 – index of num2
   else if num1 is not in A2, then
      return -1
   else if num2 is not in A1, then
      return 1
   else
      num1 – num2
End

例

#include<iostream>
#include<algorithm>
using namespace std;
int size = 5;
int A2[5]; //global A2 will be used in compare function
int search_index(int key){
   int index = 0;
   for(int i = 0; i < size; i++){
      if(A2[i] == key)
      return i;
   }
   return -1;
}
int compare(const void *num1, const void *num2){
   int index1 = search_index(*(int*)num1);
   int index2 = search_index(*(int*)num2);
   if (index1 != -1 && index2 != -1)
   return index1 - index2;
   else if (index1 != -1)
      return -1;
   else if (index2 != -1)
      return 1;
   else
      return (*(int*)num1 - *(int*)num2);
}
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};
   int n2 = sizeof(a2)/sizeof(a2[0]);
   for(int i = 0; i<n2; i++){
      A2[i] = a2[i];
   }
   qsort(data, n, sizeof(int), compare);
   for(int i = 0; i<n; i++){
      cout << data[i] << " ";
   }
}

出力

2 2 1 1 8 8 3 5 6 7 9