C++에서 다른 배열이 정의한 순서대로 배열 정렬하기

이번 글에서는 또 다른 형태의 정렬 문제를 살펴보겠습니다. 두 개의 배열 A1과 A2가 있다고 가정해 봅시다. 우리는 A1을 정렬하되, 요소들 간의 상대적인 순서가 A2에 나타난 순서와 동일하도록 만들어야 합니다. 그리고 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}

문제 해결 접근 방식

이 문제를 해결하려면 사용자 정의 비교 함수(custom compare)를 만들어야 합니다. 이 함수는 두 요소를 비교하여 배열 내에서의 위치를 결정합니다. 비교 로직은 다음과 같습니다.

• num1과 num2가 모두 A2에 존재하는 경우, A2에서 인덱스가 더 낮은 숫자를 더 작은 값으로 간주합니다.
• num1 또는 num2 중 하나만 A2에 존재하는 경우, A2에 있는 숫자를 A2에 없는 숫자보다 작은 값으로 간주합니다.
• 두 숫자 모두 A2에 존재하지 않는 경우, 일반적인 자연 순서(오름차순)를 따릅니다.

알고리즘

compare(num1, num2):
Begin
    if num1과 num2가 모두 A2에 존재하면
        return num1의 인덱스 – num2의 인덱스
    else if num1이 A2에 없으면
        return -1
    else if num2가 A2에 없으면
        return 1
    else
        return num1 – num2
End

C++ 구현 예제

#include<iostream>
#include<algorithm>
using namespace std;
int size = 5;
int A2[5]; // 비교 함수에서 사용할 전역 배열 A2
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

위 코드에서 search_index() 함수는 특정 값이 A2 내에서 몇 번째 위치에 있는지 찾아주며, 존재하지 않으면 -1을 반환합니다. compare() 함수는 앞서 설명한 비교 규칙에 따라 두 값을 비교하고, 최종적으로 C 표준 라이브러리의 qsort() 함수와 함께 사용되어 원하는 순서대로 배열을 정렬합니다.