[알고리즘] 효율적인 '분할 정복' 정렬(N log₂N): 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)

 

1. 퀵 정렬(Quick Sort)

기준값(pivot)을 선정해 그 값보다 작은 데이터와 큰 데이터로 분할하고, 이를 재귀적으로 반복하는 정렬 알고리즘.

 

1-1. 피벗 값 선정 전략

선정 방식
첫/마지막 원소 선택	이미 정렬된 입력, 역순 입력에서 최악 O(N²) 발생
임의(random) 원소 선택	평균적으로 좋은 성능 (랜덤 퀵 정렬)
세 값의 중앙값(Median-of-Three)	처음, 중간, 끝 중 중앙값을 피벗으로 선택 → 정렬/역순 입력에도 안전
정확한 중앙값(Median-of-N)	최적이지만 중앙값 계산에 O(N) 필요 → 잘 쓰이지 않음

 

1-2. 시간 복잡도

• 평균 / 최선: O(N log₂ N)

분할 정복 구조

• • log₂N번 분할 × 매 단계 N개 처리
    • log₂N : 문제 크기를 절반씩 나눔 → 몇 번 나눌까?
      • N → N/2 → N/4 → … → 1
      • 나눌 수 있는 횟수 = log₂N
    • 따라서 총 작업량 = (각 단계에서 N) × (단계 수 log₂N)

 

• 최악: O(N²)

피벗이 항상 최소/최대값으로 선택되어,  큰값 작은값 분류 없음 (분할이 불균형해질 때)

• • 바깥 루프 N번 × 안쪽 루프 N번 → 총 N×N = N²
    • 예: 버블 정렬, 삽입 정렬 최악 경우

 

1-3. 분류(Partition) 방식

1-3-1. Lomuto Partition (단방향)

 

• 포인터 2개
  • i : 작은 원소 구간의 끝
  • j : 현재 스캔 원소
• 과정
  • j를 왼→오 스캔
  • pivot보다 작으면 i++, swap(arr[i], arr[j])
  • 마지막에 pivot과 arr[i+1] swap
• 특징: 구현이 단순하지만 swap이 많음

 

 

1-3-2. Hoare Partition (양방향)

 

• 포인터 2개
  • i: 왼쪽 → 오른쪽, pivot보다 큰 원소에서 멈춤
  • j: 오른쪽 → 왼쪽, pivot보다 작은 원소에서 멈춤
• 과정
  • i, j가 pivot 기준 위배 원소에서 멈춤
  • i < j이면 swap, i ≥ j면 종료
• 특징: swap 횟수 적고 평균적으로 더 효율적

 

단방향 (Lomuto)	한쪽에서 끝까지 쭉 훑으면서 피벗보다 작은 건 앞으로 몰아넣고, 마지막에 피벗을 자기 자리로 옮김.
양방향 (Hoare)	양쪽에서 동시에 안쪽으로 들어오면서 잘못된 순서(왼쪽에 큰 값, 오른쪽에 작은 값)를 발견하면 서로 바꿔줌.

 

단방향 (Lomuto) 는 구현 편하게 pivot을 보통 끝에 두지만, 앞에 둬도 가능
양방향 (Hoare) 는 보통 pivot을 앞에 두지만, 다른 데서 가져와도 swap해서 앞에 두면 됨

 

즉, 핵심 차이 = 피벗 위치가 아니라 스캔 방식(포인터 운용 방식)

 

 

 

1-4. 퀵 정렬 장단점

1-4-1. 장점

장점
평균적으로 매우 빠름 (O(N log N))	캐시 친화적(CPU cache locality) → 같은 O(N log N) 정렬 중에서도 속도가 빠른 편  실제로 std::sort 등 라이브러리에서 채택
제자리 정렬	추가 메모리 거의 없음 (재귀 스택만 필요)
분할 정복 구조	병렬화 가능
기본 구조가 단순	구현용이

 

1-4-2. 단점

단점
최악의 경우 O(N²)	정렬/역순 입력에서 첫/마지막 원소를 피벗으로 선택 시
안정 정렬이 아님	동일 값의 상대적 순서가 보존되지 않음
재귀 깊이 문제	최악의 경우 깊이가 N → 스택 오버플로우 위험 tail recursion 제거, introsort로 보완 가능

 

 

 

 

2. 스택 프레임 (Stack Frame)

스택 영역 = 함수 호출 시 매개변수, 지역변수, 반환 주소 저장

• 함수 호출마다 새로운 스택 프레임 생성
• 함수 종료 시 스택 프레임 소멸
• 덕분에 함수 호출이 끝나면 이전 상태로 되돌아갈 수 있음

 

 

 

3. 병합 정렬(Merge Sort)

재귀적으로 배열을 절반으로 나누어 각각 정렬 후 병합. 

mergeSort(arr, start, end) 
{
    if (start < end) 
    {
        int mid = (start + end) / 2;
        mergeSort(arr, start, mid);     // 왼쪽 구간
        mergeSort(arr, mid+1, end);     // 오른쪽 구간
        merge(arr, start, mid, end);    // 병합
    }
}

 

 

3-1. 병합 정렬 장단점 

3-1-1. 장점

장점
항상 O(N log N) 보장	입력 상태와 무관하게 일정 성능
안정 정렬(Stable Sort)	동일 값의 상대적 순서 보존 → DB, 다단계 정렬에서 유리
큰 데이터(특히 외부 메모리) 처리에 유리	병합 정렬은 순차 접근(sequential access) 기반이라서, 외부 저장 장치(HDD, SSD)에서 데이터를 불러와 정렬하는 “외부 정렬(External Sort)”에 자주 사용 메모리에 전부 안 들어가는 초대형 데이터셋 정렬에 적합. 외부저장 장치는 순차접근이 빠름 (퀵 정렬은 swap방식이라 랜덤 접근 사용)
링크드 리스트 정렬에 최적	배열 기반은 메모리 복사가 많아 부담이 있지만, 연결 리스트(linked list)는 병합 정렬에서 “병합 단계”가 포인터 변경만으로 해결
병렬화 용이 (좌/우 독립 정렬)	멀티스레드/병렬 처리 구현이 쉽다
스택 오버플로우 위험 적음	재귀 깊이가 log₂N 수준

*외부 정렬 : 데이터의 크기가 주기억장치보다 커, 정렬 할 데이터들을 주기억장치에 온전히 넣을 수 없는 경우 사용되는 정렬 방법.

 

3-1-1. 단점 

단점
추가 메모리 O(N) 필요	배열 기반 구현에서는 단점
캐시 효율성이 퀵 정렬보다 떨어질 수 있음

 

 

 

4. std::sort (Introsort)

퀵 정렬 + 힙 정렬 + 삽입 정렬 혼합한 하이브리드 정렬

 

흐름 요약

 

1. 기본은 퀵 정렬로 시작
2. 재귀 깊이(분할 횟수)를 하나씩 증가시키면서 진행 
3. 깊이가 2 * log₂N을 초과하면 해당 부분의 배열을 힙 정렬로 전환 (즉, 정렬 도중 "이 부분 위험하다" 싶으면 방법을 바꿔버림)
4. 배열 크기가 충분히 작아지면 퀵 정렬 → 삽입 정렬 사용

 

 

 

5. 요약

구분	퀵 정렬 (Quick Sort)	병합 정렬 (Merge Sort)
알고리즘 방식	피벗을 기준으로 분할 (Partition)	배열을 절반으로 나눠 정렬 후 병합
시간 복잡도	평균/최선: O(N log N)최악: O(N²)	항상 O(N log N) 보장
공간 복잡도	O(log N) (재귀 스택만 사용, 제자리 정렬)	O(N) (추가 메모리 필요)
안정 정렬 여부	불안정 (같은 값의 상대 순서 보존 X)	안정 정렬 (같은 값의 상대 순서 보존 O)
캐시 효율성	높음 (랜덤 접근, locality 우수)	낮음 (병합 과정에서 메모리 이동 많음)
최악 성능	피벗 선택이 계속 치우치면 O(N²)	항상 O(N log N) (입력 상태 무관)
적합한 경우	평균적으로 가장 빠른 정렬이 필요할 때 메모리 절약이 중요한 경우	안정성이 필요한 경우 대용량 외부 정렬 / 링크드 리스트 정렬

 

• 퀵 정렬 → 빠르고 메모리 효율적, 하지만 최악 상황과 안정성에 취약
• 병합 정렬 → 항상 일정한 성능과 안정성, 하지만 메모리 소모가 큼 

 

 

퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)은 

정렬해야 할 배열을 작은 부분 문제로 나누어(Divide), 각각을 정렬한 뒤 결합(Conquer + Combine) 해서
전체 정렬을 완성하는 "분할 정복 정렬" 방식을 사용한다. 

 

---

 

다음 글에서는 "자료구조를 기반 정렬" 방식을 사용하는 힙 정렬(Heap Sort)에 대해 알아보고자 한다.