Sắp xếp một mảng theo thứ tự được xác định bởi một mảng khác trong C ++

Trong phần này chúng ta sẽ thấy một vấn đề sắp xếp khác. Giả sử chúng ta có hai mảng A1 và A2. Chúng ta phải sắp xếp A1 theo cách sao cho thứ tự tương đối giữa các phần tử sẽ giống như thứ tự trong A2. Nếu một số phần tử không có trong A2, thì chúng sẽ được thêm vào sau các phần tử đã được sắp xếp. Giả sử A1 và A2 như sau -

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

Sau khi phân loại A1 sẽ như dưới đây -

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

Để giải quyết vấn đề này, chúng tôi sẽ tạo phương pháp so sánh tùy chỉnh của chúng tôi. Phương thức đó sẽ so sánh và đặt các phần tử trong mảng. Logic so sánh sẽ như dưới đây -

• nếu cả num1 và num2 đều ở A2, thì số có chỉ số thấp hơn trong A2 sẽ được coi là nhỏ hơn số còn lại
• Nếu num1 hoặc num2 có trong A2, thì số đó sẽ được coi là nhỏ hơn số còn lại không có trong A2.
• Nếu cả hai đều không có trong A2, thì thứ tự tự nhiên sẽ được sử dụng.

Thuật toán

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

Ví dụ

#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] << " ";
   }
}

Đầu ra

2 2 1 1 8 8 3 5 6 7 9