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

Cho hai mảng A1 và A2. Sắp xếp A1 sao cho thứ tự tương đối giữa các phần tử giống với A2. Phần tử không có trong A2 sẽ được thêm vào cuối.

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

Kết quả: A1 = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}

Logic so sánh:

• Nếu cả num1 và num2 đều trong A2: số có chỉ số nhỏ hơn trong A2 được coi nhỏ hơn.
• Nếu chỉ num1 trong A2: num1 nhỏ hơn num2.
• Nếu cả hai đều không trong A2: dùng thứ tự tự nhiên.

Thuật toán

compare(num1, num2):
    Bắt đầu
        nếu cả num1 và num2 có trong A2, thì
            trả về chỉ_số(num1) - chỉ_số(num2)
        ngược lại nếu num1 không trong A2, thì
            trả về -1
        ngược lại nếu num2 không trong A1, thì
            trả về 1
        ngược lại
            num1 - num2
    Kết thúc

Ví dụ mã C++

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

int size = 5;
int A2[5];

int timChiSo(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 = timChiSo(*(int*)num1);
    int index2 = timChiSo(*(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);
}

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

Kết quả đầu ra

2 2 1 1 8 8 3 5 6 7 9