[자료구조] 대표적인 정렬 알고리즘

정렬(Sorting)은 컴퓨터 과학에서 데이터를 특정 기준(오름차순 또는 내림차순)에 따라 재배열하는 가장 기초적이면서도 핵심적인 연산입니다. 실무와 현대 프로그래밍 언어 환경에서는 고도화된 내장 라이브러리를 통해 한 줄의 코드로 정렬을 수행할 수 있지만, 각 알고리즘이 내포한 내부 동작 원리와 복잡도의 상충 관계(Trade-off)를 이해하는 것은 시스템 엔지니어링 및 문제 해결 역량의 필수 요건입니다.

본 글에서는 비교 기반 정렬의 기초가 되는 $O(N^2)$ 알고리즘부터 분할 정복 기반의 $O(N \log N)$ 알고리즘, 그리고 비교 연산을 수행하지 않는 특수 정렬까지 대표적인 7가지 정렬 알고리즘을 이론적 관점에서 정리합니다.

---

0. 정렬 알고리즘 평가의 핵심 기준

각 알고리즘을 분석하기에 앞서 성능과 동작 특성을 평가하는 핵심 기준인 시간 복잡도, 공간 복잡도, 안정성(Stability), 제자리성(In-place)을 정의합니다.

안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort)

• 안정 정렬: 동일한 키(Key) 값을 가진 원소들이 정렬된 후에도 정렬 전의 상대적 순서를 그대로 유지하는 방식입니다. 다중 조건 정렬(예: 학년 순 정렬 후 이름 순 정렬)에서 이전 정렬 상태를 보존해야 할 때 필수적입니다.
  • 대표 알고리즘: 삽입 정렬, 병합 정렬, 버블 정렬
• 불안정 정렬: 동일한 키 값을 가진 원소 간의 상대적 순서가 정렬 과정에서 왜곡될 수 있는 방식입니다.
  • 대표 알고리즘: 선택 정렬, 퀵 정렬, 힙 정렬

제자리 정렬(In-place Sort)

입력받은 배열 외에 추가적으로 요구되는 메모리 공간이 $O(1)$ 또는 재귀 호출 스택 수준($O(\log N)$)에 불과하여, 데이터 규모가 커져도 메모리 할당 오버헤드가 극히 적은 알고리즘을 의미합니다.

---

1. 버블 정렬 (Bubble Sort)

동작 메커니즘

버블 정렬은 인접한 두 원소를 비교하여 정렬 기준에 맞지 않을 경우 서로 위치를 교환(Swap)하는 방식을 취합니다.

1. 배열의 첫 번째 원소부터 인접한 다음 원소와 크기를 비교합니다.
2. 선행 원소가 후행 원소보다 크다면 두 원소의 위치를 맞바꿉니다.
3. 배열의 끝까지 이 과정을 반복하면, 배열 내 가장 큰 원소가 맨 마지막 위치에 확정 배치됩니다.
4. 정렬이 확정된 마지막 영역을 제외하고 위 과정을 $N-1$번 반복 수행합니다.

복잡도 및 특성 분석

• 시간 복잡도:
  • 최선: $O(N)$ (단 한 번의 교환도 발생하지 않은 경우 조기 종료하는 최적화 적용 시)
  • 평균 및 최악: $O(N^2)$
• 공간 복잡도: $O(1)$ (제자리 정렬)
• 안정성: 안정 정렬 (인접 원소가 같을 때는 교환을 수행하지 않음)
• 평가: 원소의 이동 방식이 단순하고 직관적이나, 불필요한 데이터 교환(Swap) 연산이 매 비교마다 발생하므로 연산 비용이 매우 높습니다. 따라서 실제 시스템 환경에서는 교육적 목적 외에 거의 채택되지 않습니다.

---

2. 선택 정렬 (Selection Sort)

동작 메커니즘

선택 정렬은 해당 자리에 위치할 원소를 직접 '선택'하여 배치하는 방식입니다.

1. 정렬되지 않은 전체 구간을 순회하여 최솟값을 탐색합니다.
2. 탐색된 최솟값을 현재 정렬되지 않은 구간의 첫 번째 원소와 맞바꿉니다.
3. 기준 위치를 오른쪽으로 한 칸 이동시키고, 나머지 미정렬 구간에 대해 동일한 탐색 및 교환 과정을 반복합니다.

복잡도 및 특성 분석

• 시간 복잡도:
  • 최선, 평균, 최악: 모두 $O(N^2)$
• 공간 복잡도: $O(1)$ (제자리 정렬)
• 안정성: 불안정 정렬
• 평가: 입력 데이터의 정렬 상태와 무관하게 항상 $\frac{N(N-1)}{2}$회의 비교를 수행하므로 비효율적입니다. 다만, 실제 원소 간 교환(Swap) 횟수는 최대 $N-1$회로 고정되므로, 쓰기(Write) 연산의 비용이 읽기(Read) 연산보다 극단적으로 높은 메모리 환경(예: 플래시 메모리 일부 영역)에서는 제한적으로 고려될 수 있습니다.

---

3. 삽입 정렬 (Insertion Sort)

동작 메커니즘

삽입 정렬은 정렬된 부분 배열을 점진적으로 확장하며, 새로 검토하는 원소를 이미 정렬된 부분 배열 내의 올바른 위치에 '삽입'하는 구조를 갖습니다.

1. 두 번째 원소부터 시작하여 해당 원소를 임시 변수(Key)에 저장합니다.
2. Key 값보다 앞서 존재하는 정렬 영역의 원소들을 역순으로 탐색합니다.
3. Key보다 큰 값을 가진 원소들을 오른쪽으로 한 칸씩 이동(Shift)시킵니다.
4. Key보다 작거나 같은 원소를 마주치거나 배열의 시작에 도달하면, 비워진 위치에 Key를 삽입합니다.

복잡도 및 특성 분석

• 시간 복잡도:
  • 최선: $O(N)$ (데이터가 이미 정렬되어 있는 경우)
  • 평균 및 최악: $O(N^2)$ (역순 정렬된 경우)
• 공간 복잡도: $O(1)$ (제자리 정렬)
• 안정성: 안정 정렬
• 평가: 삽입 정렬은 교환(Swap)이 아닌 원소 이동(Shift)을 사용하여 연산 오버헤드를 낮추었으며, 데이터가 대부분 정렬되어 있는 준정렬 상태(Nearly Sorted)에서는 퀵 정렬을 상회하는 $O(N)$의 성능을 발휘합니다. 이러한 특성 때문에 현대의 고성능 하이브리드 정렬(TimSort 등)에서 작은 단위의 블록을 정렬하는 서브루틴으로 적극 활용됩니다.

---

4. 병합 정렬 (Merge Sort)

동작 메커니즘

존 폰 노이만(John von Neumann)이 고안한 알고리즘으로, 대표적인 분할 정복(Divide and Conquer) 설계 기법을 적용합니다.

1. 분할(Divide): 정렬할 배열의 크기가 1 이하가 될 때까지 균등하게 절반으로 분할합니다.
2. 정복(Conquer): 더 이상 쪼갤 수 없는 부분 배열을 시작으로, 인접한 두 배열을 정렬된 단일 배열로 병합합니다.
3. 병합(Merge): 두 부분 배열의 선두 포인터를 비교하여 더 작은 원소를 임시 배열에 순차적으로 적재한 뒤, 잔여 원소를 이어붙입니다.

복잡도 및 특성 분석

• 시간 복잡도:
  • 최선, 평균, 최악: 모두 $O(N \log N)$ 보장
• 공간 복잡도: $O(N)$ (병합 결과를 수용할 추가 메모리 필수)
• 안정성: 안정 정렬
• 평가: 데이터의 분포나 초기 상태에 영향을 받지 않고 최악의 상황에서도 $O(N \log N)$의 수행 시간을 엄격히 보장합니다. 다만 배열을 기반으로 구현할 경우 임시 공간 $O(N)$이 필수적으로 요구되어 메모리 제약이 심한 환경에서는 단점이 됩니다. 반면, 노드 포인터만 재연결하면 되는 연결 리스트(Linked List) 정렬 시에는 추가 공간 없이 적용이 가능하여 매우 우수한 적합성을 보입니다.

---

5. 퀵 정렬 (Quick Sort)

동작 메커니즘

토니 호어(C. A. R. Hoare)가 제안한 분할 정복 알고리즘으로, 특정 기준 원소인 피벗(Pivot)을 선정하여 배열을 두 부분으로 파티셔닝(Partitioning)하는 방식으로 동작합니다.

1. 배열 내에서 하나의 피벗을 설정합니다.
2. 피벗을 기준으로 좌측에는 피벗보다 작은 값을, 우측에는 피벗보다 큰 값을 배치하도록 양방향 포인터를 이동시키며 원소를 교환합니다.
3. 분할이 완료되면 피벗은 최종 정렬된 위치에 고정됩니다.
4. 피벗을 제외한 좌측 및 우측 부분 배열에 대해 재귀적으로 동일한 과정을 적용합니다.

복잡도 및 특성 분석

• 시간 복잡도:
  • 최선 및 평균: $O(N \log N)$
  • 최악: $O(N^2)$ (이미 정렬된 배열에서 최솟값 또는 최댓값을 지속적으로 피벗으로 택하는 경우)
• 공간 복잡도: $O(\log N)$ (재귀 호출 호출 스택 메모리)
• 안정성: 불안정 정렬
• 평가: 최악의 경우 시간 복잡도가 $O(N^2)$로 퇴화할 수 있는 이론적 결함이 존재하지만, 일반적인 환경에서는 다른 $O(N \log N)$ 알고리즘보다 현저히 빠른 실행 속도를 보입니다. 내부 루프가 단순하고, 메모리를 순차적으로 순회하므로 참조 지역성(Locality of Reference)이 뛰어나 CPU 캐시 적중률이 극대화되기 때문입니다. 최악의 경우는 피벗을 무작위로 선택하거나 세 값의 중앙값(Median of Three)을 취하는 기법, 또는 임계 깊이 초과 시 힙 정렬로 전환하는 인트로소트(Introsort) 기법을 통해 회피할 수 있습니다.

---

6. 힙 정렬 (Heap Sort)

동작 메커니즘

완전 이진 트리(Complete Binary Tree) 기반의 자료구조인 힙(Heap)의 특성을 활용한 정렬 알고리즘입니다.

1. 입력 배열을 부모 노드가 자식 노드보다 항상 큰 최대 힙(Max Heap) 구조로 재구성합니다(Heapify).
2. 최대 힙의 루트 노드(배열의 최댓값)를 미정렬 영역의 마지막 원소와 교환합니다.
3. 힙의 크기를 1 감소시킨 후, 손상된 루트 위치에 대해 하향식 Heapify를 수행하여 힙 성질을 복원합니다.
4. 힙의 크기가 1이 될 때까지 위 과정을 반복하여 오름차순 정렬을 완성합니다.

복잡도 및 특성 분석

• 시간 복잡도:
  • 최선, 평균, 최악: 모두 $O(N \log N)$ 보장
• 공간 복잡도: $O(1)$ (제자리 정렬)
• 안정성: 불안정 정렬
• 평가: 병합 정렬처럼 최악의 경우에도 $O(N \log N)$의 성능을 보장하면서도, 추가 메모리를 전혀 사용하지 않는($O(1)$) 완전한 제자리 정렬이라는 점이 가장 큰 강점입니다. 그러나 인덱스 상에서 원소 간 점프 폭이 커 캐시 지역성이 떨어지므로, 실제 평균 실행 시간은 퀵 정렬에 비해 유의미하게 뒤처지는 경향이 있습니다.

---

7. 계수 정렬 (Counting Sort)

동작 메커니즘

원소 간의 대소 비교를 수행하지 않고, 각 원소의 출현 빈도수(Count)를 측정하여 정렬을 완료하는 비비교 기반 정렬(Non-comparison Sort)입니다.

1. 데이터 내 최댓값($K$)과 최솟값을 확인하여 값의 범위를 포괄하는 크기의 카운트 배열을 생성합니다.
2. 입력 배열을 1회 순회하며 각 원소의 등장 횟수를 카운트 배열의 해당 인덱스에 기록합니다.
3. 카운트 배열의 원소들을 누적 합 형태로 변환하여 각 값의 최종 출력 위치를 계산합니다.
4. 입력 배열을 역순으로 순회하며 누적 카운트 값을 참조해 정렬된 출력 배열의 제자리에 값을 배치합니다.

복잡도 및 특성 분석

• 시간 복잡도:
  • 최선, 평균, 최악: 모두 $O(N + K)$ ($K$는 데이터의 범위 크기)
• 공간 복잡도: $O(N + K)$ (카운트 배열 및 출력 배열 필요)
• 안정성: 안정 정렬 (역순 배치 로직 적용 시)
• 평가: 비교 연산을 수행하지 않기 때문에 비교 기반 정렬의 이론적 하한선인 $\Omega(N \log N)$을 돌파하여 선형 시간($O(N)$)에 정렬을 마칠 수 있습니다. 그러나 데이터의 범위($K$)가 매우 큰 경우 불필요한 메모리 할당이 폭증하여 비효율적이며, 데이터가 정수형으로 매핑 가능할 때만 적용할 수 있다는 한계가 있습니다.

---

8. 알고리즘 종합 비교 및 엔지니어링 관점의 결론

핵심 지표 비교 요약

알고리즘	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도	안정성 (Stable)	제자리 정렬 (In-place)
버블 정렬	$O(N^2)$	$O(N^2)$	$O(1)$	O	O
선택 정렬	$O(N^2)$	$O(N^2)$	$O(1)$	X	O
삽입 정렬	$O(N^2)$	$O(N^2)$	$O(1)$	O	O
병합 정렬	$O(N \log N)$	$O(N \log N)$	$O(N)$	O	X
퀵 정렬	$O(N \log N)$	$O(N^2)$	$O(\log N)$	X	O
힙 정렬	$O(N \log N)$	$O(N \log N)$	$O(1)$	X	O
계수 정렬	$O(N + K)$	$O(N + K)$	$O(N + K)$	O	X

실무와 시스템 엔지니어링에서의 시사점

1. 상수 계수와 캐시 친화성의 중요성
   이론적인 점근적 표기법(Big-O)에서는 $O(N \log N)$으로 분류되는 퀵 정렬, 병합 정렬, 힙 정렬이지만, 실제 실행 속도는 CPU의 캐시 메모리 구조와 공간 지역성에 의해 퀵 정렬이 대체로 압도적인 성능을 보입니다. 알고리즘 선택 시 단순 복잡도뿐만 아니라 하드웨어 아키텍처와의 상호작용을 고려해야 합니다.

2. 하이브리드 정렬 알고리즘의 보편화
   현대 프로그래밍 언어의 표준 런타임 환경은 단일 정렬 알고리즘에 의존하지 않습니다.

   • TimSort (Python, Java Objects, Swift 등): 병합 정렬의 안정성과 삽입 정렬의 준정렬 데이터 처리 효율성을 결합하여, 실제 세계의 정형화된 데이터에서 최적의 성능을 도출합니다.
   • Introsort (C++ std::sort 등): 퀵 정렬로 시작하되, 재귀 깊이가 깊어지면 힙 정렬로 전환하여 $O(N^2)$ 위험을 원천 차단하고, 분할 영역 크기가 작아지면 삽입 정렬로 마무리하는 하이브리드 방식을 취합니다.

결과적으로 최적의 정렬 알고리즘이란 절대적인 것이 아니며, 데이터의 크기, 기정렬 상태, 메모리 가용 한계, 안정성 요구 여부에 따른 트레이드오프 분석을 바탕으로 결정됩니다.