게임 개발에서 데이터를 정렬(Sort)해야 하는 순간은 생각보다 자주 등장합니다. 몬스터를 거리 순으로 정렬하거나, 타겟 우선순위를 정렬하거나, UI 리스트를 특정 기준으로 재배치하는 경우가 대표적입니다.
그런데 정렬은 결과만 보면 단순합니다. 어떤 정렬을 쓰든 최종 결과는 “정렬된 상태”로 같아 보이기 때문입니다. 하지만 내부에서는 비교 횟수, 데이터 이동 횟수, 추가 메모리 사용 같은 비용이 크게 달라질 수 있습니다.
이 글은 특정 정렬 알고리즘(Bubble, Quick 등)을 구현하지 않습니다. Unity 개발 관점에서 정렬을 어떻게 바라봐야 하는지, 그리고 정렬이 왜 시간 복잡도(Big O)를 가장 직관적으로 체감시키는 작업인지에 초점을 둡니다.
1. 정렬(Sort)이란 무엇인가?
정렬(Sort)은 데이터를 특정 기준에 따라 재배치하는 작업입니다. 오름차순/내림차순 같은 단순 기준뿐 아니라, 게임에서는 거리/점수/시간/우선순위처럼 다양한 기준으로 정렬합니다.
정렬의 핵심은 “순서를 맞춘다”가 아니라, 데이터를 서로 비교해서 어떤 값이 앞에 와야 하는지를 결정하는 과정입니다. 이 과정에서 발생하는 비용이 정렬 성능을 결정합니다.
- 비교(Compare): 두 값 중 어떤 것이 앞인지 판단하는 작업
- 이동/교환(Move/Swap): 판단 결과에 따라 실제 데이터 위치를 바꾸는 작업
- 추가 메모리(Extra Memory): 임시 배열/버퍼 등을 사용하는 경우 발생하는 비용
2. 같은 정렬, 다른 비용
아래 입력은 어떤 정렬 알고리즘을 사용하든 결과는 같습니다.
[5, 3, 1, 4, 2]
→
[1, 2, 3, 4, 5]
하지만 내부적으로는 전혀 다른 일이 벌어질 수 있습니다. 정렬 알고리즘에 따라 비교 횟수, 데이터 이동 방식, 메모리 사용 여부, 그리고 최악의 경우 성능이 크게 달라지기 때문입니다.
1) 모든 원소를 반복적으로 비교하는 정렬
Bubble Sort나 Selection Sort처럼, 모든 원소를 서로 거의 빠짐없이 비교하는 방식의 정렬도 있습니다. 이 경우 원소 개수가 n개라면 비교 횟수는 대략 n²에 가까워지며, 데이터가 커질수록 비용이 빠르게 증가합니다.
예를 들어 몬스터가 10마리 정도일 때는 큰 문제가 없지만, 1,000마리 이상으로 늘어나면 정렬 자체만으로도 프레임 드랍이 체감될 수 있습니다.
이 유형의 정렬은 구조는 단순하고 직관적이지만, Big O(O(n²))의 차이를 가장 빨리 체감하게 만드는 정렬입니다.
2) 데이터를 나누는 방식으로 비교 횟수를 줄이는 정렬
Merge Sort나 Quick Sort는 모든 데이터를 한 번에 정렬하지 않고, 여러 부분으로 나눈 뒤 정리하는 구조를 사용합니다.
이 방식은 비교 횟수 자체를 구조적으로 줄이기 때문에, 데이터가 커져도 비교적 안정적인 O(n log n) 성능을 만들어 냅니다. 정렬 대상이 많아질수록 이러한 차이는 더욱 분명하게 드러납니다.
3) 추가 메모리를 사용하는 대신 성능을 예측할 수 있는 정렬
Merge Sort는 정렬 과정에서 임시 배열과 같은 추가 메모리를 사용합니다. 그만큼 메모리 사용량은 늘어나지만, 입력 데이터의 형태와 관계없이 항상 일정한 성능을 기대할 수 있다는 장점이 있습니다.
즉, 메모리를 비용으로 지불하는 대신 예측 가능한 시간 복잡도를 얻는 방식이라고 볼 수 있습니다.
4) 평균적으로 매우 빠르지만 최악의 경우가 존재하는 정렬
Quick Sort는 평균적으로 매우 빠른 성능을 보이기 때문에 실제로 널리 사용되는 정렬 알고리즘입니다.
하지만 입력 데이터의 형태에 따라서는 특정 상황에서 O(n²)까지 성능이 나빠질 수 있습니다. 즉, 대부분의 경우에는 빠르지만, 최악의 경우가 존재한다는 점을 이해하고 사용하는 것이 중요합니다.
결국 정렬 알고리즘의 차이는 “얼마나 똑똑하게 비교 횟수와 데이터 이동을 줄이느냐”, 그리고 그 과정에서 무엇을 비용으로 감수하느냐(메모리 사용, 최악 성능 등)의 차이라고 볼 수 있습니다.
3. 정렬과 시간 복잡도(Big O)
정렬은 시간 복잡도(Big O)를 가장 직관적으로 체감할 수 있는 작업입니다. 이유는 단순합니다. 정렬은 보통 “많은 비교”가 반복되고, 입력 크기(n)가 커질수록 그 반복이 급격히 늘어나기 때문입니다.
- O(n²) 계열 정렬: 데이터가 조금만 커져도 비용이 빠르게 증가합니다.
- O(n log n) 계열 정렬: 데이터가 커져도 비교적 증가 폭이 완만합니다.
예를 들어 입력 크기 n이 1,000 → 10,000으로 증가한다고 가정해 보겠습니다.
- O(n²)은 대략 (10배)²에 가까운 규모로 커지기 때문에 체감 성능이 급격히 나빠질 수 있습니다.
- O(n log n)은 10배 증가에 더해 log 항이 조금 늘어나는 정도이므로 증가 폭이 상대적으로 완만합니다.
정렬은 Big O를 “머리로 이해했다”에서 “몸으로 느꼈다”로 바꿔주는 대표적인 전환점이 됩니다.
4. 왜 정렬 알고리즘은 이렇게 많은가?
정렬 알고리즘이 많은 이유는 하나입니다. 모든 상황에서 완벽한 정렬은 없기 때문입니다. 어떤 정렬은 평균적으로 빠르고, 어떤 정렬은 최악의 경우 성능을 보장하며, 어떤 정렬은 메모리를 더 쓰는 대신 안정적인 결과를 제공합니다.
정렬을 선택할 때는 보통 아래 기준들이 서로 충돌합니다. 즉, 하나를 얻으면 다른 하나를 포기해야 하는 경우가 많습니다.
√ 평균 성능이 중요한가, 최악 성능 보장이 중요한가
어떤 정렬(예: Quick Sort)은 평균적으로 매우 빠르지만, 입력 데이터 형태에 따라 최악의 경우 O(n²)까지 느려질 수 있습니다. 반대로 어떤 정렬(예: Merge Sort)은 평균/최악 모두 O(n log n)을 보장해 성능이 예측 가능합니다.
예를 들어, 전투 중 타겟 후보를 정렬하는 로직이 특정 상황에서만 갑자기 느려지면 플레이어는 “가끔 프레임이 뚝 떨어진다”고 체감합니다. 이런 경우에는 평균이 빠른 선택보다 최악을 피하는 선택이 더 안전할 수 있습니다.
√ 추가 메모리 사용을 허용할 수 있는가
Merge Sort는 임시 배열 같은 추가 메모리를 사용합니다. 메모리를 더 쓰는 대신, 성능이 안정적이고 구현 관점에서도 일관된 흐름을 가질 수 있습니다. 반면, 어떤 정렬들은 추가 메모리를 거의 쓰지 않는 대신(제자리 정렬) 구현이 복잡해지거나, 특정 상황에서 성능 특성이 달라질 수 있습니다.
예를 들어, 대용량 데이터를 정렬해야 하는데 모바일 환경처럼 메모리가 빡빡한 상황이라면 “조금 느려도 메모리를 덜 쓰는 방식”이 현실적인 선택일 수 있습니다. 반대로 툴/서버처럼 메모리 여유가 있다면 메모리를 성능과 맞바꾸는 선택이 더 합리적일 수 있습니다.
√ 안정 정렬(Stable Sort)이 필요한가
안정 정렬은 “같은 값(키)”을 가진 항목들의 상대적 순서를 유지합니다. 예를 들어 (점수, 등록시간) 같은 복합 기준에서 “점수로 정렬하되, 점수가 같으면 원래 순서를 유지” 같은 요구가 있을 때 의미가 있습니다.
Unity에서 UI 리스트를 생각해 보면, 점수가 같은 유저들이 있을 때 정렬할 때마다 표시 순서가 매번 바뀌면 사용자는 “목록이 흔들린다”는 느낌을 받습니다. 이런 경우에는 안정 정렬이 더 자연스러운 결과를 줍니다. (대표적으로 Merge Sort는 안정 정렬로 알려져 있습니다.)
√ 입력이 이미 거의 정렬된 상태인지, 무작위인지
입력 데이터의 상태에 따라 어떤 정렬은 유리해지고, 어떤 정렬은 불리해집니다. 예를 들어 Insertion Sort는 데이터가 “거의 정렬된 상태”라면 매우 효율적으로 동작할 수 있습니다. 반대로 데이터가 완전히 무작위이고 크기도 크다면, 일반적으로 O(n log n) 계열 정렬이 더 유리합니다.
Unity에서 “거리순 타겟 리스트”를 매 프레임 업데이트한다고 가정하면, 실제로는 매 프레임마다 순서가 완전히 뒤집히기보다는 근처 일부만 조금씩 바뀌는 경우가 많습니다. 이런 경우에는 “거의 정렬된 입력에 강한 방식”이 생각보다 좋은 선택이 될 수 있습니다.
정리하면, 정렬 알고리즘이 다양한 이유는 서로 다른 비용(평균/최악 성능, 메모리 사용, 안정성, 입력 상태)에 대한 선택지가 필요하기 때문입니다. 결국 “정렬을 고르는 일”은 알고리즘 이름을 고르는 것이 아니라, 내 상황에서 무엇을 비용으로 감수할지 결정하는 일이라고 볼 수 있습니다.
5. 안정 정렬(Stable)과 불안정 정렬(Unstable)
정렬에는 “안정성(Stable)”이라는 기준이 있습니다. 정렬 결과가 같아 보이더라도, 같은 값(키)을 가진 항목들이 정렬 과정에서 어떤 순서로 남는지에 따라 사용자 경험과 디버깅 편의성이 크게 달라질 수 있습니다.
- 안정 정렬(Stable Sort): 같은 값(키)을 가진 항목들의 상대적 순서가 유지됩니다.
- 불안정 정렬(Unstable Sort): 같은 값(키)을 가진 항목들의 순서가 바뀔 수 있습니다.
말만 보면 차이가 작아 보이지만, 예시를 보면 바로 이해됩니다.
예시: “점수”로 정렬할 때, 같은 점수는 어떻게 될까?
아래는 (이름, 점수, 등록순서)로 구성된 리스트라고 가정해 보겠습니다. 리스트는 “등록된 순서”대로 들어온 상태입니다.
등록 순서:
A(점수 100)
B(점수 100)
C(점수 90)
D(점수 100)이제 “점수 내림차순”으로 정렬하면, 점수 100인 항목들이 맨 위로 모이는 것은 동일합니다. 차이는 점수 100끼리의 상대적 순서입니다.
- 안정 정렬이라면:
A → B → D처럼 원래 들어온 순서가 그대로 유지됩니다. - 불안정 정렬이라면:
B → D → A처럼 같은 점수끼리 순서가 뒤섞일 수 있습니다.
즉, 안정 정렬은 “같은 값이면 원래 순서를 존중한다”는 성질을 갖습니다.
5.1 Unity에서 안정성이 특히 의미 있는 대표 상황
√ UI 리스트가 “흔들리는” 문제
랭킹 UI나 인벤토리 UI에서 “점수/가격/거리”로 정렬했는데, 값이 같은 항목들이 매번 새로고침할 때마다 순서가 바뀌면 사용자는 목록이 불안정하게 흔들린다고 느낍니다.
이때 안정 정렬을 사용하면 “같은 점수는 등록된 순서대로 유지”되기 때문에 UI가 훨씬 자연스럽고 일관되게 보입니다.
√ 로그 / 리플레이 / 결과 화면의 일관성
예를 들어 “거리순 타겟 목록”을 정렬한 뒤 로그를 남기거나, 리플레이에서 같은 상황을 재현한다고 했을 때, 같은 거리(혹은 같은 우선순위)의 대상 순서가 매번 뒤섞이면 디버깅 시 비교가 어렵고 결과가 불안정해 보일 수 있습니다.
안정 정렬을 사용하면 “같은 값이면 이전 순서가 유지”되므로 로그와 재현 결과가 더 일관되게 유지됩니다.
√ 2단계 정렬(복합 기준)을 쉽게 만들고 싶을 때
안정 정렬은 실전에서 “정렬을 두 번” 하는 방식으로 복합 기준을 만들 때 특히 유용합니다. 예를 들어,
1) 먼저 “등록 시간(오래된 순)”으로 정렬한 뒤
2) 다시 “점수(높은 순)”으로 정렬하면
안정 정렬에서는 점수가 같은 항목들이 등록 시간 순서를 그대로 유지하므로 결과적으로 “점수 우선, 점수 같으면 등록 시간 우선” 같은 복합 기준이 자연스럽게 만들어집니다.
이 글에서는 안정/불안정을 깊게 파고들지는 않습니다. 다만 이후 개별 정렬 알고리즘을 볼 때, “이 정렬은 안정적인가?”를 판단하는 기준으로 활용하시면 됩니다.
6. Unity 개발 관점에서 정렬을 조심해야 하는 순간
Unity에서 정렬로 인한 성능 문제는, 대부분 “정렬 알고리즘이 느려서” 발생하지 않습니다. 실제 원인은 훨씬 단순한 경우가 많습니다. 정렬을 언제, 얼마나 자주 호출하느냐가 문제의 핵심입니다.
6.1 가장 흔한 실수: Update()에서 매 프레임 정렬
다음과 같은 패턴은 Unity 프로젝트에서 매우 자주 등장합니다.
- 타겟 목록을 거리순으로 매 프레임 정렬
- UI 리스트를 Update에서 계속 재정렬
- AI 우선순위 리스트를 매 프레임 전체 정렬
이때 문제가 되는 것은 정렬 자체보다, 정렬이 프레임 단위로 반복된다는 점입니다. 예를 들어 O(n log n) 정렬이라 하더라도, n이 커지고 이 작업이 매 프레임 반복되면 성능 비용은 곧바로 프레임 드랍으로 이어집니다.
많은 경우 정렬 대상은 “매 프레임 완전히 달라지는 데이터”가 아닙니다. 그럼에도 불구하고 전체를 다시 정렬하고 있다면, 불필요한 비용을 계속 지불하고 있는 셈입니다.
6.2 정렬이 정말 매번 필요한가?
정렬을 호출하기 전에, 다음 질문을 먼저 던져볼 필요가 있습니다.
- 정렬 기준이 실제로 변경되었는가?
- 데이터가 추가되거나 제거되었는가?
- 전체 순서가 아니라 일부만 달라졌는가?
이 질문에 대부분 “아니오”라면, 매 프레임 전체 정렬은 과한 선택일 가능성이 큽니다.
1) 변경이 있을 때만 정렬하기 (Dirty Flag)
가장 기본적이면서도 효과적인 방법은 “변경이 발생했을 때만 정렬”하는 구조입니다.
- 데이터 추가 / 삭제 시 플래그 설정
- 정렬 기준 값 변경 시 플래그 설정
- 플래그가 있을 때만 정렬 실행
이 방식만 적용해도 “Update에서 매 프레임 정렬” 문제의 대부분은 사라집니다.
2) 전체 정렬 대신 필요한 만큼만 처리하기
실제 게임 로직에서는 전체 순서가 아니라 상위 몇 개만 필요한 경우가 많습니다.
- 가장 가까운 타겟 1개
- 우선순위 상위 3~5개
- 화면에 표시할 일부 UI 항목
이런 경우 전체 리스트를 정렬하는 대신,
- 최소/최대 값만 탐색
- 부분 정렬
- 우선순위 큐(Priority Queue) 사용
같은 방식이 훨씬 합리적인 선택이 될 수 있습니다. 정렬은 “모든 순서가 필요할 때”만 사용하는 것이 좋습니다.
3) 거의 정렬된 상태를 유지하기
앞서 언급했듯, 실제 게임 데이터는 매 프레임 완전히 뒤섞이지 않는 경우가 많습니다. 예를 들어 거리 기반 타겟 리스트라면, 대부분의 프레임에서는 순서가 거의 유지되고 일부만 바뀌는 경우가 많습니다.
이런 상황에서는
- 기존 정렬 결과를 유지한 채
- 변화가 생긴 항목만 위치를 조정
하는 방식이 전체 정렬보다 훨씬 효율적일 수 있습니다.
6.3 비교 함수(IComparer)가 더 문제인 경우도 많다
정렬 비용은 단순히 정렬 알고리즘의 Big O만으로 결정되지 않습니다. 비교 함수 자체의 비용도 매우 중요합니다.
다음과 같은 비교는 생각보다 무겁습니다.
- Vector 거리 계산 (sqrt 포함)
- Component 접근(GetComponent)
- 계층 구조 탐색
이런 연산이 정렬 과정에서 수백~수천 번 반복되면, 정렬 알고리즘이 빠르더라도 전체 비용은 커질 수 있습니다. 따라서 Unity에서는 정렬 전에 비교에 필요한 값들을 미리 계산해 두는 구조가 성능 면에서 훨씬 유리한 경우가 많습니다.
6.4 정리
Unity에서 정렬을 사용할 때 가장 중요한 질문은 이것입니다.
- 이 정렬은 정말 지금, 이 프레임에, 전체가 필요한가?
정렬 알고리즘의 Big O도 물론 중요하지만, Unity 개발에서는 그보다 정렬 호출 빈도와 구조 설계가 성능에 더 큰 영향을 주는 경우가 많습니다. 정렬은 강력한 도구이지만, 아무 생각 없이 자주 사용하면 가장 먼저 성능 병목으로 드러나는 작업이기도 합니다.
마무리 및 다음 단계
이 글은 특정 정렬 알고리즘을 구현하거나 비교하는 문서가 아닙니다. 정렬을 사용할 때 반드시 함께 고려해야 할 기준들, 즉 비교 횟수, 데이터 이동, 안정성, 시간 복잡도, 그리고 Unity에서의 호출 빈도와 같은 공통 기준을 정리하기 위한 문서입니다.
정렬은 결과만 보면 단순해 보이지만, 내부에서는 알고리즘에 따라 전혀 다른 비용이 발생합니다. 특히 정렬은 시간 복잡도(Big O)의 차이가 실제 성능으로 가장 빠르게 드러나는 대표적인 작업입니다.
이 기준을 바탕으로 이후 글에서는 Bubble Sort, Insertion Sort, Merge Sort, Quick Sort와 같은 정렬 알고리즘을 하나씩 독립적으로 살펴보며, 각 정렬이 어떤 상황에 적합한 선택인지 정리해 나갈 예정입니다.
시간 복잡도를 이해했다면, 정렬은 그 차이를 “머리로 아는 것”에서 “실제로 체감하는 것”으로 바꿔주는 첫 번째 관문이라고 볼 수 있습니다.
※ 다음 글에서는 Bubble Sort를 살펴보며, 인접한 요소를 반복적으로 비교·교환하는 가장 단순한 정렬 알고리즘을 통해 정렬 알고리즘의 기본 동작 방식과 비용 구조를 이해해 봅니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Selection Sort(선택 정렬) 구현 (0) | 2026.01.14 |
|---|---|
| Unity 개발자를 위한 C# Bubble Sort(버블 정렬) 구현 (0) | 2026.01.14 |
| Unity 개발자를 위한 시간 복잡도(Big O) 개념 정리 (0) | 2026.01.13 |
| Unity 개발자를 위한 C# Red-Black Tree(레드 블랙 트리) 구현 (0) | 2025.12.27 |
| Unity 개발자를 위한 C# AVL(자기 균형 이진 탐색 트리) 구현 (0) | 2025.12.24 |
