C++에서 다른 배열에 의해 정의된 순서에 따라 배열 정렬

이 섹션에서 우리는 또 다른 정렬 문제를 볼 것입니다. 두 개의 배열 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