[C++] 코딩테스트에서의 정렬

1개요

정렬은 사용자가 정의한 순서대로 데이터를 나열하는 연산이다. 오름차순·내림차순이 일반적이지만, 임의 조건도 가능하다. 정렬이 필요한 이유는 크게 두 가지다. 첫째, 데이터가 정렬되어 있으면 중앙값·최댓값을 훨씬 빠르게 구할 수 있다. 둘째, 이진 탐색처럼 정렬을 전제 조건으로 삼는 알고리즘이 존재한다.

이번 챕터에서는 삽입 정렬, 병합 정렬, 계수 정렬, 힙 정렬 네 가지를 다룬다. 각 알고리즘의 동작 원리와 시간 복잡도를 비교하며 어떤 상황에 무엇을 써야 하는지 판단 기준을 세우는 것이 목표다.

---

2삽입 정렬 (Insertion Sort)

정렬되지 않은 원소를 이미 정렬된 부분 배열의 적절한 위치에 삽입하며 전체를 정렬하는 알고리즘이다. 첫 번째 원소는 이미 정렬된 것으로 간주하고 두 번째 원소부터 처리한다.

1

key 설정: 현재 인덱스 j의 값을 key로 저장하고 i = j - 1로 초기화한다.

2

밀어내기: A[i] > key인 동안 A[i+1] = A[i]로 원소를 한 칸씩 뒤로 밀고, i--한다.

3

삽입: 루프 종료 후 A[i+1] = key로 알맞은 자리에 넣는다.

C++ · 삽입 정렬

for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;

    // key보다 큰 요소를 한 칸씩 뒤로 이동
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}

삽입 정렬의 시간 복잡도 — 최악 vs 최선

경우	시간 복잡도	조건	이유
최악	O(N²)	역순 정렬 데이터	매 단계 전체 원소를 밀어야 함. 비교 횟수 = N(N-1)/2
최선	O(N)	이미 정렬된 데이터	각 원소마다 1번 비교 후 즉시 종료

💡 거의 정렬된 데이터에서 삽입 정렬은 O(N)에 가까워진다. 이 특성 때문에 실무의 하이브리드 정렬(Timsort 등)에서 소규모 구간에 삽입 정렬을 활용한다.

---

3병합 정렬 (Merge Sort)

분할 정복(Divide & Conquer) 기법을 활용한 정렬이다. 배열을 계속 반으로 나눈 뒤 가장 작은 단위부터 정렬하며 합쳐 올라간다. 크게 세 단계로 이루어진다.

1

분할 (Divide): 중간 지점 mid = left + (right - left) / 2 기준으로 배열을 두 하위 배열로 나눈다.

2

정복 (Conquer): 각 하위 배열을 재귀적으로 mergeSort() 호출해 정렬한다. 원소가 1개가 될 때까지 반복한다.

3

결합 (Combine): 두 정렬된 배열의 맨 앞 원소를 포인터로 비교해 작은 값을 먼저 임시 배열에 추가한다. 모두 소진되면 임시 배열을 원본에 복사한다.

C++ · 병합 정렬

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // (left+right)/2는 오버플로우 위험
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// merge() 핵심 — 두 포인터 비교
while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) temp[k++] = arr[i++];
    else                  temp[k++] = arr[j++];
}

분할 트리의 높이는 log N층이고, 각 층에서 모든 원소를 한 번씩 병합하므로 한 층당 O(N)이 걸린다. 따라서 전체 시간 복잡도는 O(N log N)이며 최선·평균·최악 모두 동일하다. 단, 병합 과정에서 임시 배열이 필요해 추가 메모리 O(N)이 사용된다.

---

4계수 정렬 (Counting Sort)

데이터값 자체를 인덱스로 사용하는 방식이다. 각 값의 등장 횟수를 count[] 배열에 기록한 뒤, 인덱스 순서대로 횟수만큼 꺼내면 정렬 결과가 된다. 비교 연산을 전혀 하지 않기 때문에 조건만 맞으면 매우 빠르다.

C++ · 계수 정렬

// 1. 최댓값 K 탐색
int maxVal = *max_element(arr, arr + n);

// 2. count 배열 생성 및 빈도수 기록 — O(K) + O(N)
int* count = new int[maxVal + 1]{};
for (int i = 0; i < n; ++i)
    count[arr[i]]++;

// 3. 인덱스 순으로 빈도수만큼 결과 생성 — O(N)
int idx = 0;
for (int i = 0; i <= maxVal; ++i)
    while (count[i]--) arr[idx++] = i;

delete[] count;
// 입출력: {4,2,2,8,3,3,1} → {1,2,2,3,3,4,8}

N은 입력 배열 크기, K는 최댓값이라 할 때 시간 복잡도는 O(N + K)다. K가 충분히 작으면 비교 기반 정렬보다 훨씬 빠르다. 단, 아래 두 가지 경우에는 사용할 수 없다.

⚠️ 계수 정렬을 쓰면 안 되는 경우
① 음수 값이 포함된 경우 — 배열의 인덱스로 음수를 쓸 수 없다.
② 값의 범위(K)가 매우 큰 경우 — 데이터가 500과 10억이라면 10억 크기의 배열이 필요해 메모리가 폭발한다.

---

5힙 정렬 (Heap Sort)

힙(Heap)이라는 자료구조를 활용한 정렬이다. 힙은 조건을 만족하는 완전 이진 트리로, 최대 힙(Max-Heap)은 모든 부모 노드의 값이 자식 노드 이상이고, 최소 힙(Min-Heap)은 그 반대다. 힙을 배열로 표현할 때 인덱스 규칙(0-based)은 다음과 같다.

관계	인덱스 수식
왼쪽 자식	2 * i + 1
오른쪽 자식	2 * i + 2
부모	(i - 1) / 2

힙 정렬 동작 순서

1

최대 힙 구축 — build_max_heap(): 인덱스 n/2 - 1부터 0까지 역순으로 heapify()를 호출한다. 리프 노드는 자식이 없어 heapify가 불필요하므로 절반부터 시작한다.

2

루트 추출 & 교환: 루트 arr[0](최댓값)과 배열 마지막 원소를 교환해 최댓값을 배열 뒤에 정착시킨다.

3

힙 크기 축소 & 반복: 힙 범위를 1 줄이고, 루트에 대해 다시 heapify()를 수행한다. heap_size = 1이 될 때까지 반복하면 오름차순 정렬이 완료된다.

C++ · 힙 정렬

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left  = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  < n && arr[left]  > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // 재귀 — 교환된 위치 재정비
    }
}

void heapSort(int arr[], int n) {
    // 1. Build Max Heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. 최댓값을 하나씩 배열 뒤로 정착
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);       // 루트 ↔ 마지막 원소
        heapify(arr, i, 0);        // 줄어든 범위에서 재정비
    }
}
// {4,10,3,5,1} → {1,3,4,5,10}

힙의 높이는 log N이고, N번의 추출마다 heapify()가 O(log N)이므로 전체 시간 복잡도는 O(N log N)이다. 추가 메모리가 O(1)이며 최선·평균·최악 모두 동일하다는 것이 장점이다.

💡 힙 자료구조는 정렬뿐 아니라 삽입/삭제 연산도 O(log N)에 수행할 수 있어 우선순위 큐(Priority Queue) 구현에도 폭넓게 사용된다.

---

6한눈에 보는 정리

알고리즘	최선	평균	최악	추가 메모리	안정 정렬	특이사항
삽입 정렬	O(N)	O(N²)	O(N²)	O(1)	✓	거의 정렬된 경우 강력
병합 정렬	O(NlogN)	O(NlogN)	O(NlogN)	O(N)	✓	성능이 일정, 메모리 필요
계수 정렬	O(N+K)	O(N+K)	O(N+K)	O(K)	✓	음수·큰 K 사용 불가
힙 정렬	O(NlogN)	O(NlogN)	O(NlogN)	O(1)	✗	제자리 정렬, 성능 일정

---

7오늘의 회고

항목	내용
새로 배운 것	삽입·병합·계수·힙 정렬의 동작 원리와 시간 복잡도 차이. 힙이 단순한 정렬 도구가 아니라 삽입/삭제도 O(log N)에 처리하는 자료구조라는 점이 인상적이었다.
어려웠던 점	build_max_heap()에서 왜 n/2 - 1부터 시작하는지 처음엔 직관적으로 이해가 안 됐다. 인덱스 규칙(left = 2i+1)을 직접 그려보니, n/2 이상 인덱스는 모두 리프 노드임을 확인할 수 있었다.
기억할 핵심	계수 정렬은 K가 작고 음수가 없을 때만 사용. 범용 상황에서는 병합·힙 정렬이 안전한 선택이며, 이미 거의 정렬된 데이터에는 삽입 정렬이 의외로 강하다.
다음 목표	계수 정렬 응용 문제(문자열 정렬), 커스텀 비교 함수를 이용한 정렬 문제 직접 풀어보기. 힙을 활용한 우선순위 큐 패턴도 별도로 정리할 예정이다.