[C++ - TIL] 퀵 정렬(Quick Sort)의 재귀적 분할과 포인터 제어

🎮 주제 : 퀵 정렬(Quick Sort)의 재귀적 분할과 포인터 제어

태그 : #C++ #알고리즘 #퀵정렬 #분할정복 #재귀함수 #정렬최적화

---

📌 학습 요약

• 퀵 정렬(Quick Sort)의 원리 : 기준점인 **피벗(Pivot)**을 설정하고, 이보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 몰아넣는 분할(Partition) 과정을 반복하여 정렬을 완성함
• 포인터 이동 전략 : left 포인터는 피벗보다 큰 값을, right 포인터는 피벗보다 작은 값을 찾아 서로 교환하며 피벗의 최종 위치를 확정함
• 재귀적 문제 해결 : 하나의 큰 배열을 피벗을 기준으로 두 개의 작은 부분 배열로 나누고, 각 배열에 대해 동일한 정렬 함수를 재귀적으로 호출함
• 안정적인 종료 조건 : 부분 배열의 크기가 1 이하(start >= end)가 되는 시점에 재귀를 멈추어 불필요한 연산과 스택 오버플로우를 방지함

---

🛠 주요 코드 및 구현 상세

1. 퀵 정렬(Quick Sort) 핵심 구현

void sort(int list[], int start, int end) {
    // 1. 종료 조건: 부분 배열의 원소가 1개 이하일 때
    if (start >= end) return;

    int pivot = start;      // 가장 왼쪽 원소를 피벗으로 설정
    int left = start + 1;
    int right = end;

    // 2. 분할(Partition): 피벗을 기준으로 좌우 정렬
    while (left <= right) {
        // 피벗보다 큰 값을 찾을 때까지 left 이동
        while (left <= end && list[left] <= list[pivot]) left++;
        // 피벗보다 작은 값을 찾을 때까지 right 이동
        while (right > start && list[right] >= list[pivot]) right--;

        if (left > right) {
            // 포인터가 교차했다면 피벗과 right를 교환 (피벗 확정)
            swap(list[pivot], list[right]);
        } else {
            // 교차 전이라면 찾은 두 값을 서로 교환
            swap(list[left], list[right]);
        }
    }

    // 3. 재귀 호출: 확정된 피벗 위치(right)를 기준으로 양옆을 다시 정렬
    sort(list, start, right - 1);
    sort(list, right + 1, end);
}

---

✅ 주요 문법 및 개념 정리

개념 특징 주의 사항

피벗 (Pivot)	분할의 기준이 되는 값	고정 선택 시 정렬된 배열에서 $O(n^2)$ 위험
재귀 (Recursion)	자기 자신을 호출해 범위 축소	base case 누락 시 무한 루프 발생
분할 (Partition)	피벗 좌우로 데이터를 재배치	left와 right의 경계 체크(left <= end) 필수
In-place Sort	추가 메모리 없이 배열 내에서 정렬	재귀 스택 공간은 사용됨

💡 핵심 로직 : 왜 right와 교환하는가?

• while 루프가 끝난 뒤 right 포인터가 가리키는 곳은 피벗보다 작거나 같은 값들 중 가장 오른쪽입니다.
• 따라서 피벗과 right를 바꾸면 피벗 왼쪽에는 항상 피벗보다 작은 값들만 남게 되어 논리적으로 완벽한 분할이 이루어집니다.

---

✨ 느낀 점

• 퀵 정렬의 핵심은 단순히 나누는 것이 아니라, 피벗이 '제 자리를 찾아가는 과정'임을 코드로 구현하며 명확히 이해함
• 재귀 함수에서 start >= end와 같은 종료 조건이 코드의 안정성을 결정짓는 방어벽 역할을 한다는 것을 깨달음
• while문 안의 경계 조건(right > start 등)을 세밀하게 설정하지 않으면 인덱스 범위를 벗어날 수 있음을 배우며 정교한 설계의 중요성을 느낌
• 피벗 위치 확정 후 재귀 호출 범위를 right - 1, right + 1로 설정하여 이미 정렬된 피벗을 제외하는 최적화 원리를 체득함