알고리즘 — 정렬(Sorting): 퀵소트, 머지소트, 힙소트

개요 — 왜 정렬 알고리즘을 알아야 하는가

정렬(Sorting)은 컴퓨터 과학의 가장 오래된 문제 중 하나이자, 게임 개발에서 매 프레임 눈에 띄지 않게 실행되는 핵심 연산입니다.

• 렌더러가 반투명 오브젝트를 카메라에서 먼 순서(Back-to-Front)로 그리는 깊이 정렬(Depth Sorting)
• 매칭 시스템이 플레이어를 점수 기반으로 나열하는 리더보드 정렬
• AI가 가장 가까운 적을 빠르게 선택하는 타깃 우선순위 정렬
• Unreal의 FHitResult 배열을 거리 순으로 정렬하는 트레이스 결과 처리

단순히 std::sort를 호출하는 것과, 내부 동작을 이해하고 상황에 맞는 알고리즘을 선택하는 것은 런타임 성능에 큰 차이를 만듭니다. 이 글에서는 세 가지 핵심 정렬 알고리즘의 원리와 구현, 그리고 Unreal Engine에서의 실전 활용을 학습합니다.

---

1. 주요 정렬 알고리즘 비교

본격적인 학습에 앞서 대표적인 정렬 알고리즘들의 특성을 한눈에 비교합니다.

알고리즘	평균 시간복잡도	최악 시간복잡도	공간복잡도	안정 정렬	비고
버블 정렬(Bubble Sort)	O(n²)	O(n²)	O(1)	O	교육용, 실무 사용 안 함
선택 정렬(Selection Sort)	O(n²)	O(n²)	O(1)	X	교육용
삽입 정렬(Insertion Sort)	O(n²)	O(n²)	O(1)	O	소규모·거의 정렬된 데이터에 유리
퀵 정렬(Quick Sort)	O(n log n)	O(n²)	O(log n)	X	일반 목적 최고 성능, std::sort 기반
머지 정렬(Merge Sort)	O(n log n)	O(n log n)	O(n)	O	안정성 보장 필요 시 선택
힙 정렬(Heap Sort)	O(n log n)	O(n log n)	O(1)	X	제자리 정렬, 최악에도 O(n log n)

안정 정렬(Stable Sort)이란?

동일한 키(Key)를 가진 원소의 상대적 순서가 정렬 후에도 유지되는 성질입니다. 예를 들어 점수가 같은 플레이어를 입력 순서 그대로 유지해야 할 때 안정 정렬이 필요합니다.

입력: [(Alice, 100), (Bob, 100), (Charlie, 100)]
안정 정렬 결과: [(Alice, 100), (Bob, 100), (Charlie, 100)]  // 입력 순서 유지
불안정 정렬 결과: [(Bob, 100), (Alice, 100), (Charlie, 100)]  // 순서 보장 없음

---

2. 퀵소트 (Quick Sort)

2.1 핵심 아이디어: 분할 정복

퀵소트는 분할 정복(Divide and Conquer) 패러다임을 사용합니다. 배열에서 **피벗(Pivot)**을 하나 선택한 뒤, 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할(Partition)합니다. 이 과정을 재귀적으로 반복하면 배열이 정렬됩니다.

[3, 6, 8, 10, 1, 2, 5]   피벗 = 5 (마지막 원소)
 ↓ 파티션
[3, 1, 2] | 5 | [6, 8, 10]
 ↓ 재귀             ↓ 재귀
[1, 2, 3]        [6, 8, 10]
 ↓ 합치기
[1, 2, 3, 5, 6, 8, 10]

2.2 시간복잡도 분석

케이스	복잡도	발생 조건
평균	O(n log n)	피벗이 배열을 균등하게 분할할 때
최선	O(n log n)	피벗이 항상 중앙값일 때
최악	O(n²)	이미 정렬된 배열 + 첫 번째 원소를 피벗으로 선택할 때

최악 케이스 방지 전략: 랜덤 피벗(Random Pivot) 선택 또는 Median-of-Three(첫 번째·중간·마지막 원소의 중앙값을 피벗으로 선택)를 사용합니다. C++ 표준 라이브러리의 std::sort는 Introsort(퀵소트 + 힙소트 + 삽입소트 혼합)를 사용하여 최악 케이스를 O(n log n)으로 보장합니다.

2.3 C++ 구현

// Lomuto 파티션 방식 퀵소트
// 마지막 원소를 피벗으로 선택하는 단순한 구현

int32 Partition(TArray<int32>& Arr, int32 Low, int32 High)
{
    int32 Pivot     = Arr[High];  // 피벗: 마지막 원소
    int32 SmallIdx  = Low - 1;   // 피벗보다 작은 영역의 경계

    for (int32 i = Low; i < High; ++i)
    {
        if (Arr[i] <= Pivot)
        {
            ++SmallIdx;
            Swap(Arr[SmallIdx], Arr[i]);  // 작은 원소를 왼쪽 영역으로 이동
        }
    }

    // 피벗을 올바른 위치에 배치
    Swap(Arr[SmallIdx + 1], Arr[High]);
    return SmallIdx + 1;  // 피벗의 최종 인덱스 반환
}

void QuickSort(TArray<int32>& Arr, int32 Low, int32 High)
{
    if (Low >= High) { return; }  // 원소가 1개 이하면 종료 (기저 조건)

    int32 PivotIdx = Partition(Arr, Low, High);

    QuickSort(Arr, Low, PivotIdx - 1);   // 피벗 왼쪽 재귀 정렬
    QuickSort(Arr, PivotIdx + 1, High);  // 피벗 오른쪽 재귀 정렬
}

// 사용 예시
void ExampleQuickSort()
{
    TArray<int32> Numbers = {3, 6, 8, 10, 1, 2, 5};
    QuickSort(Numbers, 0, Numbers.Num() - 1);
    // 결과: [1, 2, 3, 5, 6, 8, 10]
}

Median-of-Three 피벗 선택 (개선 버전):

// 첫 번째, 중간, 마지막 원소 중 중앙값을 피벗으로 선택
// 이미 정렬된 배열에서의 O(n²) 최악 케이스를 실질적으로 방지
int32 MedianOfThree(TArray<int32>& Arr, int32 Low, int32 High)
{
    int32 Mid = Low + (High - Low) / 2;

    // 세 원소를 정렬하여 중앙값을 Mid 위치에 배치
    if (Arr[Low] > Arr[Mid])   { Swap(Arr[Low],  Arr[Mid]);  }
    if (Arr[Low] > Arr[High])  { Swap(Arr[Low],  Arr[High]); }
    if (Arr[Mid] > Arr[High])  { Swap(Arr[Mid],  Arr[High]); }

    // 중앙값(Mid)을 High 위치로 이동 → Partition이 Arr[High]를 피벗으로 읽으므로
    Swap(Arr[Mid], Arr[High]);
    return Arr[High];  // 중앙값이 피벗
}

2.4 공간복잡도

퀵소트는 추가 배열 없이 원본 배열 내에서 정렬하는 **제자리 정렬(In-place Sort)**입니다. 다만 재귀 호출 스택이 평균 O(log n), 최악 O(n) 깊이만큼 쌓입니다.

---

3. 머지소트 (Merge Sort)

3.1 핵심 아이디어: 안정적인 분할 정복

머지소트도 분할 정복을 사용하지만, 퀵소트와 달리 배열을 항상 절반으로 균등하게 분할합니다. 분할된 부분 배열을 각각 정렬한 뒤, **두 정렬된 배열을 병합(Merge)**하여 최종 결과를 만듭니다.

[38, 27, 43, 3, 9, 82, 10]
 ↓ 분할
[38, 27, 43]       [3, 9, 82, 10]
 ↓ 분할              ↓ 분할
[38] [27, 43]     [3, 9] [82, 10]
      ↓ 병합         ↓ 병합   ↓ 병합
     [27, 43]       [3, 9]  [10, 82]
 ↓ 병합               ↓ 병합
[27, 38, 43]         [3, 9, 10, 82]
          ↓ 최종 병합
      [3, 9, 10, 27, 38, 43, 82]

3.2 시간·공간복잡도 분석

케이스	시간복잡도	비고
평균	O(n log n)	분할 깊이 log n × 각 레벨 병합 O(n)
최선	O(n log n)	항상 동일
최악	O(n log n)	퀵소트와 달리 최악 케이스 없음

• 공간복잡도: O(n) — 병합 단계에서 임시 배열이 필요합니다. 추가 메모리를 허용할 수 없는 환경에서는 힙소트를 고려해야 합니다.

머지소트의 핵심 장점: 최악 케이스에서도 O(n log n)을 보장하며, **안정 정렬(Stable Sort)**입니다. 연결 리스트(Linked List) 정렬에도 적합합니다(배열 인덱스 접근이 필요 없음).

3.3 C++ 구현

// 두 정렬된 부분 배열을 병합하는 핵심 함수
void Merge(TArray<int32>& Arr, int32 Left, int32 Mid, int32 Right)
{
    // 임시 배열로 왼쪽·오른쪽 부분 복사
    TArray<int32> LeftArr  (Arr.GetData() + Left, Mid - Left + 1);
    TArray<int32> RightArr (Arr.GetData() + Mid + 1, Right - Mid);

    int32 i = 0;          // LeftArr 인덱스
    int32 j = 0;          // RightArr 인덱스
    int32 k = Left;       // 병합 결과를 쓸 Arr 인덱스

    // 두 배열을 비교하며 작은 원소부터 Arr에 기록
    while (i < LeftArr.Num() && j < RightArr.Num())
    {
        // 안정 정렬: 같은 값이면 왼쪽 배열 원소를 먼저 선택
        if (LeftArr[i] <= RightArr[j])
        {
            Arr[k++] = LeftArr[i++];
        }
        else
        {
            Arr[k++] = RightArr[j++];
        }
    }

    // 남은 원소 처리
    while (i < LeftArr.Num())  { Arr[k++] = LeftArr[i++];  }
    while (j < RightArr.Num()) { Arr[k++] = RightArr[j++]; }
}

void MergeSort(TArray<int32>& Arr, int32 Left, int32 Right)
{
    if (Left >= Right) { return; }  // 원소 1개: 기저 조건

    int32 Mid = Left + (Right - Left) / 2;  // 오버플로우 방지용 중간점 계산

    MergeSort(Arr, Left, Mid);       // 왼쪽 절반 재귀 정렬
    MergeSort(Arr, Mid + 1, Right);  // 오른쪽 절반 재귀 정렬
    Merge(Arr, Left, Mid, Right);    // 두 정렬된 절반 병합
}

// 사용 예시
void ExampleMergeSort()
{
    TArray<int32> Numbers = {38, 27, 43, 3, 9, 82, 10};
    MergeSort(Numbers, 0, Numbers.Num() - 1);
    // 결과: [3, 9, 10, 27, 38, 43, 82]
}

병합 단계에서 안정성이 보장되는 이유:

LeftArr[i] <= RightArr[j] 조건에서 같은 값일 때 왼쪽 배열(원래 앞에 있던 원소)을 먼저 선택하기 때문입니다. 이로써 동일 키를 가진 원소의 원래 순서가 유지됩니다.

---

4. 힙소트 (Heap Sort)

4.1 핵심 아이디어: 힙 자료구조 활용

힙소트는 최대 힙(Max Heap) 자료구조를 배열 내부에서 구성하여 정렬합니다. 최대 힙이란 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 완전 이진 트리(Complete Binary Tree)입니다.

배열로 표현한 최대 힙:
         10
        /  \
       9    8
      / \  / \
     7   6 5  4

배열: [10, 9, 8, 7, 6, 5, 4]
인덱스:  0  1  2  3  4  5  6

자식 인덱스 공식: 부모 i의 왼쪽 자식 = 2*i+1, 오른쪽 자식 = 2*i+2
부모 인덱스 공식: 자식 i의 부모 = (i-1)/2

4.2 동작 과정

1. 힙 구성(Build Heap): 배열을 최대 힙으로 변환합니다. O(n)에 완료됩니다.
2. 정렬(Extract): 최대 힙의 루트(최댓값)를 배열 끝으로 이동시킨 뒤, 힙 크기를 1 줄이고 Heapify로 힙 성질을 복원합니다. 이를 n-1번 반복합니다.

초기 최대 힙: [10, 9, 8, 7, 6, 5, 4]

Step 1: 루트(10)를 끝으로 이동 → [9, 7, 8, 4, 6, 5, | 10]
Step 2: 루트(9)를 끝으로 이동  → [8, 7, 5, 4, 6, | 9, 10]
Step 3: 루트(8)를 끝으로 이동  → [7, 6, 5, 4, | 8, 9, 10]
...
최종: [4, 5, 6, 7, 8, 9, 10]  → 오름차순 정렬 완료

4.3 시간·공간복잡도 분석

케이스	시간복잡도	비고
평균	O(n log n)	힙 구성 O(n) + n회 Extract O(log n)
최선	O(n log n)	항상 동일
최악	O(n log n)	퀵소트와 달리 최악 케이스 없음

• 공간복잡도: O(1) — 추가 배열 없이 원본 배열 내부에서 힙을 구성하는 **제자리 정렬(In-place Sort)**입니다.

힙소트의 위치: 최악에도 O(n log n), 추가 메모리 O(1)이라는 이론적 최적 조합이지만, 캐시 비친화적인 접근 패턴으로 인해 실제 성능은 퀵소트보다 느린 경우가 많습니다. std::sort의 Introsort는 재귀 깊이가 임계값을 초과할 때만 힙소트로 전환합니다.

4.4 C++ 구현

// 부분 힙(인덱스 RootIdx)에서 최대 힙 성질을 복원하는 함수
// HeapSize: 현재 힙으로 관리되는 배열 범위
void Heapify(TArray<int32>& Arr, int32 HeapSize, int32 RootIdx)
{
    int32 Largest  = RootIdx;          // 루트를 최댓값 후보로 초기화
    int32 LeftIdx  = 2 * RootIdx + 1;  // 왼쪽 자식 인덱스
    int32 RightIdx = 2 * RootIdx + 2;  // 오른쪽 자식 인덱스

    // 왼쪽 자식이 루트보다 크면 최댓값 후보 갱신
    if (LeftIdx < HeapSize && Arr[LeftIdx] > Arr[Largest])
    {
        Largest = LeftIdx;
    }

    // 오른쪽 자식이 현재 최댓값 후보보다 크면 갱신
    if (RightIdx < HeapSize && Arr[RightIdx] > Arr[Largest])
    {
        Largest = RightIdx;
    }

    // 최댓값이 루트가 아니면 교환 후 하위 트리 재귀 Heapify
    if (Largest != RootIdx)
    {
        Swap(Arr[RootIdx], Arr[Largest]);
        Heapify(Arr, HeapSize, Largest);  // 교환된 위치에서 힙 성질 복원
    }
}

void HeapSort(TArray<int32>& Arr)
{
    const int32 N = Arr.Num();

    // 1단계: 최대 힙 구성 (마지막 비-리프 노드부터 역순으로 Heapify)
    // 마지막 비-리프 노드 인덱스 = N/2 - 1
    for (int32 i = N / 2 - 1; i >= 0; --i)
    {
        Heapify(Arr, N, i);
    }

    // 2단계: 루트(최댓값)를 배열 끝으로 이동, 힙 크기 감소, 힙 복원 반복
    for (int32 i = N - 1; i > 0; --i)
    {
        Swap(Arr[0], Arr[i]);    // 현재 최댓값(루트)을 현재 배열 끝으로 이동
        Heapify(Arr, i, 0);     // 줄어든 힙에서 루트 Heapify
    }
}

// 사용 예시
void ExampleHeapSort()
{
    TArray<int32> Numbers = {12, 11, 13, 5, 6, 7};
    HeapSort(Numbers);
    // 결과: [5, 6, 7, 11, 12, 13]
}

---

5. Unreal Engine TArray 정렬 API

Unreal Engine은 TArray에 세 가지 정렬 메서드를 제공합니다. 상황에 맞는 API를 선택하면 위에서 학습한 알고리즘의 특성을 그대로 활용할 수 있습니다.

5.1 TArray::Sort — 빠른 불안정 정렬

내부적으로 Introsort(퀵소트 기반)를 사용합니다. 일반 목적 정렬에서 가장 빠른 선택입니다.

// 기본 오름차순 정렬 (operator< 사용)
TArray<int32> Scores = {85, 42, 97, 66, 33};
Scores.Sort();
// 결과: [33, 42, 66, 85, 97]

// 람다 비교 함수로 내림차순 정렬
Scores.Sort([](const int32& A, const int32& B)
{
    return A > B;
});
// 결과: [97, 85, 66, 42, 33]

// 구조체 배열을 특정 필드 기준으로 정렬
USTRUCT()
struct FEnemyInfo
{
    GENERATED_BODY()
    UPROPERTY() float Distance = 0.0f;
    UPROPERTY() int32  Priority = 0;
};

TArray<FEnemyInfo> Enemies;
// 거리 기준 오름차순 정렬 (가장 가까운 적 우선)
Enemies.Sort([](const FEnemyInfo& A, const FEnemyInfo& B)
{
    return A.Distance < B.Distance;
});

5.2 TArray::StableSort — 안정 정렬

내부적으로 머지소트 기반을 사용하며, 동일 키 원소의 입력 순서를 보장합니다. 동점자 처리나 복합 정렬 기준이 필요한 경우에 선택합니다.

USTRUCT()
struct FPlayerScore
{
    GENERATED_BODY()
    FString PlayerName;
    int32   Score = 0;

    FPlayerScore() = default;
    FPlayerScore(const FString& InName, int32 InScore)
        : PlayerName(InName), Score(InScore) {}
};

TArray<FPlayerScore> Leaderboard;
Leaderboard.Add(FPlayerScore(TEXT("Alice"),   1500));
Leaderboard.Add(FPlayerScore(TEXT("Bob"),     1200));
Leaderboard.Add(FPlayerScore(TEXT("Charlie"), 1500));  // Alice와 동점

// StableSort: 점수 내림차순. 동점(Alice, Charlie)은 입력 순서(Alice → Charlie) 유지
Leaderboard.StableSort([](const FPlayerScore& A, const FPlayerScore& B)
{
    return A.Score > B.Score;
});
// 결과: [Alice(1500), Charlie(1500), Bob(1200)]
// Alice가 Charlie보다 먼저 나온 입력 순서 유지됨

5.3 TArray::HeapSort — 명시적 힙소트

제자리 정렬이 필요하거나 힙 자료구조를 직접 활용하는 경우에 사용합니다.

TArray<int32> Values = {12, 11, 13, 5, 6, 7};
Values.HeapSort([](const int32& A, const int32& B)
{
    return A < B;  // 오름차순
});
// 결과: [5, 6, 7, 11, 12, 13]

5.4 TArray 힙 조작 API

TArray는 힙을 동적으로 관리하는 추가 API도 제공합니다. 우선순위 큐(Priority Queue) 패턴 구현에 유용합니다.

// AI 타깃 우선순위 큐 예시 (거리가 짧을수록 우선순위 높음)
TArray<FEnemyInfo> TargetHeap;

// Heapify: 배열을 힙으로 변환 (초기화 시 1회 호출)
TargetHeap.Heapify([](const FEnemyInfo& A, const FEnemyInfo& B)
{
    return A.Distance < B.Distance;  // 최소 힙 (거리 짧은 적 루트)
});

// HeapPush: 힙 성질을 유지하며 원소 삽입 O(log n)
FEnemyInfo NewEnemy;
NewEnemy.Distance = 150.0f;
TargetHeap.HeapPush(NewEnemy, [](const FEnemyInfo& A, const FEnemyInfo& B)
{
    return A.Distance < B.Distance;
});

// HeapPop: 루트(최우선 원소)를 꺼내고 힙 성질 복원 O(log n)
FEnemyInfo NearestTarget;
TargetHeap.HeapPop(NearestTarget, [](const FEnemyInfo& A, const FEnemyInfo& B)
{
    return A.Distance < B.Distance;
});

// HeapTop: 루트를 꺼내지 않고 참조만 O(1)
const FEnemyInfo& TopTarget = TargetHeap.HeapTop();

5.5 정렬 API 선택 기준

상황	권장 API
일반 목적, 최고 속도	Sort()
동일 키 원소 순서 보장 필요	StableSort()
명시적 힙소트 필요	HeapSort()
동적 최솟값·최댓값 관리 (우선순위 큐)	Heapify() + HeapPush() + HeapPop()

---

6. 게임 개발 실전 활용

6.1 렌더링 우선순위 — 반투명 오브젝트 깊이 정렬

반투명(Translucent) 오브젝트는 카메라에서 **먼 순서(Back-to-Front)**로 렌더링해야 올바른 블렌딩이 이루어집니다. 이를 Painter’s Algorithm이라고 합니다.

USTRUCT()
struct FTranslucentObject
{
    GENERATED_BODY()

    UPROPERTY()
    TObjectPtr<UPrimitiveComponent> Component;

    float DistanceToCamera = 0.0f;
};

UCLASS()
class UTransparencySortComponent : public UActorComponent
{
    GENERATED_BODY()

public:
    // 매 프레임 렌더 전 호출하여 반투명 오브젝트를 깊이 정렬
    void SortForRendering(const FVector& CameraLocation)
    {
        // 거리 갱신
        for (FTranslucentObject& Obj : TranslucentObjects)
        {
            if (Obj.Component)
            {
                Obj.DistanceToCamera = FVector::Dist(
                    Obj.Component->GetComponentLocation(), CameraLocation);
            }
        }

        // Back-to-Front 정렬 (먼 것부터 그려야 함)
        // 동일 거리 오브젝트의 순서가 중요하지 않으므로 Sort() 사용
        TranslucentObjects.Sort([](const FTranslucentObject& A, const FTranslucentObject& B)
        {
            return A.DistanceToCamera > B.DistanceToCamera;  // 내림차순
        });
    }

private:
    UPROPERTY()
    TArray<FTranslucentObject> TranslucentObjects;
};

6.2 점수판(Leaderboard) — 안정 정렬 활용

멀티플레이어 점수판은 점수 내림차순으로 정렬하되, 동점 시 먼저 달성한 플레이어를 우선해야 합니다. 이는 안정 정렬의 전형적인 활용 사례입니다.

USTRUCT(BlueprintType)
struct FLeaderboardEntry
{
    GENERATED_BODY()

    UPROPERTY(BlueprintReadOnly) FString  PlayerName;
    UPROPERTY(BlueprintReadOnly) int32    Score       = 0;
    UPROPERTY(BlueprintReadOnly) FDateTime AchievedAt; // 점수 달성 시각
};

UCLASS()
class ULeaderboardSubsystem : public UGameInstanceSubsystem
{
    GENERATED_BODY()

public:
    void UpdateLeaderboard(const FLeaderboardEntry& NewEntry)
    {
        // 기존 항목 갱신 또는 신규 추가
        FLeaderboardEntry* Existing = Entries.FindByPredicate(
            [&](const FLeaderboardEntry& E) { return E.PlayerName == NewEntry.PlayerName; });

        if (Existing)
        {
            *Existing = NewEntry;
        }
        else
        {
            Entries.Add(NewEntry);
        }

        SortLeaderboard();
    }

    const TArray<FLeaderboardEntry>& GetEntries() const { return Entries; }

private:
    UPROPERTY()
    TArray<FLeaderboardEntry> Entries;

    void SortLeaderboard()
    {
        // StableSort: 점수 내림차순
        // 동점 시 입력 순서(먼저 달성한 플레이어) 유지
        Entries.StableSort([](const FLeaderboardEntry& A, const FLeaderboardEntry& B)
        {
            return A.Score > B.Score;
        });
    }
};

6.3 AI 타깃 우선순위 — 복합 정렬 기준

AI가 여러 적 중 위협도 순으로 타깃을 선택하는 시스템입니다. 위협도는 거리, 체력, 플레이어 여부 등 복합 기준으로 계산됩니다.

USTRUCT()
struct FAITarget
{
    GENERATED_BODY()

    UPROPERTY()
    TObjectPtr<AActor> Actor;

    float Distance       = 0.0f;
    float HealthRatio    = 1.0f;  // 0~1: 낮을수록 위험
    bool  bIsPlayer      = false;
};

UCLASS()
class UAITargetingComponent : public UActorComponent
{
    GENERATED_BODY()

public:
    AActor* SelectPrimaryTarget(const FVector& AILocation)
    {
        if (PotentialTargets.IsEmpty()) { return nullptr; }

        // 위협도 점수 계산: 거리 짧음 + 체력 낮음 + 플레이어 우선
        auto CalcThreat = [](const FAITarget& T) -> float
        {
            float ThreatScore = 0.0f;
            ThreatScore += (1000.0f - FMath::Clamp(T.Distance, 0.0f, 1000.0f));  // 거리 기여
            ThreatScore += (1.0f - T.HealthRatio) * 300.0f;                        // 체력 기여
            ThreatScore += T.bIsPlayer ? 500.0f : 0.0f;                            // 플레이어 보너스
            return ThreatScore;
        };

        // 거리 갱신 후 위협도 기준 내림차순 정렬
        for (FAITarget& Target : PotentialTargets)
        {
            if (Target.Actor)
            {
                Target.Distance = FVector::Dist(Target.Actor->GetActorLocation(), AILocation);
            }
        }

        PotentialTargets.Sort([&CalcThreat](const FAITarget& A, const FAITarget& B)
        {
            return CalcThreat(A) > CalcThreat(B);  // 위협도 높은 순
        });

        return PotentialTargets[0].Actor;  // 최고 위협도 타깃 반환
    }

private:
    UPROPERTY()
    TArray<FAITarget> PotentialTargets;
};

성능 고려사항: 수백 개의 타깃을 매 프레임 정렬하는 것은 비효율적입니다. 실전에서는 다음 전략을 병행합니다.

• Tick 간격 조절: 타깃 정렬을 매 프레임이 아닌 0.1초 간격(SetTimer)으로 실행
• 부분 업데이트: 새 타깃이 추가될 때만 HeapPush로 힙을 갱신, 전체 재정렬 회피
• 거리 기반 컬링: 정렬 전 일정 반경 밖 타깃을 먼저 제거하여 정렬 대상 수 최소화

---

7. 정리 — 알고리즘 선택 기준

상황	권장 알고리즘	이유
일반 목적, 최고 평균 성능	퀵소트 (TArray::Sort)	평균 O(n log n), 캐시 친화적
동일 키 순서 보장 필수	머지소트 (TArray::StableSort)	안정 정렬 보장
추가 메모리 사용 불가	힙소트 (TArray::HeapSort)	O(1) 추가 공간, O(n log n) 최악 보장
이미 거의 정렬된 소규모 데이터	삽입 정렬	O(n) 최선, 오버헤드 낮음
동적 최솟값·최댓값 반복 조회	힙 자료구조 (TArray::Heapify + HeapPush/Pop)	삽입·추출 각 O(log n)
최악 케이스까지 O(n log n) 보장 + 제자리	힙소트	퀵소트 최악 O(n²) 회피 필요 시

핵심 요약:

• 퀵소트: 실전 최강자. 불안정하지만 평균 성능이 가장 우수. std::sort와 TArray::Sort의 내부 구현.
• 머지소트: 안정성과 최악 케이스 보장이 필요할 때. O(n) 추가 메모리가 단점.
• 힙소트: 최악도 O(n log n), 추가 메모리 O(1). 캐시 비효율로 실전 속도는 퀵소트보다 느림.

Unreal Engine에서는 TArray::Sort, TArray::StableSort, TArray::HeapSort 중 요구 조건에 맞는 API를 선택하고, 람다 비교 함수로 커스텀 정렬 기준을 간결하게 표현하는 패턴을 익혀두면 대부분의 게임 개발 정렬 시나리오를 커버할 수 있습니다.