13강. 퀵 정렬과 피벗: 평균 성능과 최악 상황 이해하기

?1. 이번 강의에서 해결할 문제

제자리 정렬의 장점을 얻고 싶지만 피벗을 잘못 선택하면 이미 정렬된 입력에서 재귀가 한쪽으로 치우칠 수 있습니다.

✓2. 학습 목표

✓이 강의를 마치면

• 피벗과 파티션의 역할을 설명합니다.
• 제자리 퀵 정렬을 구현합니다.
• 균형 분할과 편향 분할의 복잡도를 비교합니다.

◇3. 핵심 개념

퀵 정렬은 피벗보다 작거나 같은 값과 큰 값을 분리한 뒤 양쪽을 재귀 정렬합니다. 분할이 균형에 가까우면 깊이 O(log n), 전체 평균 O(n log n)입니다. 매번 가장 작거나 큰 값이 피벗이면 깊이 O(n), 최악 O(n²)과 O(n) 재귀 스택이 됩니다. 무작위 피벗이나 중앙값 근사는 위험을 줄이지만 최악 가능성을 없애는 보장은 아닙니다.

✎4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/QuickSortDemo.java

src/QuickSortDemo.java

import java.util.Arrays;

public class QuickSortDemo {
    static void sort(int[] a, int low, int high) {
        if (low >= high) return;
        int pivotIndex = partition(a, low, high);
        sort(a, low, pivotIndex - 1);
        sort(a, pivotIndex + 1, high);
    }
    static int partition(int[] a, int low, int high) {
        int mid = low + (high - low) / 2;
        swap(a, mid, high);
        int pivot = a[high], boundary = low;
        for (int i = low; i < high; i++) if (a[i] <= pivot) swap(a, i, boundary++);
        swap(a, boundary, high);
        return boundary;
    }
    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    public static void main(String[] args) {
        int[] scores = {1400, 600, 1200, 900, 1200};
        sort(scores, 0, scores.length - 1);
        System.out.println(Arrays.toString(scores));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/QuickSortDemo.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/QuickSortDemo.java와 out 아래 생성되는 class 파일

Windows PowerShell

Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\QuickSortDemo.java
java -cp .\out QuickSortDemo

예상 결과: [600, 900, 1200, 1200, 1400]이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

→5. 코드와 알고리즘이 동작하는 이유

partition이 반환한 위치에는 피벗의 최종 값이 놓이고 왼쪽은 피벗 이하, 오른쪽은 피벗 초과라는 불변식이 생깁니다. 배열 자체에서 교환해 별도 배열은 없지만 재귀 스택이 평균 O(log n), 최악 O(n)입니다. 이 구현은 안정 정렬이 아닙니다.

!6. 자주 하는 실수와 해결법

!자주 하는 실수

• 실수: 피벗을 포함한 구간으로 다시 재귀 호출하기 해결: pivotIndex - 1과 + 1로 제외합니다.
• 실수: 평균 O(n log n)을 최악 보장으로 쓰기 해결: 피벗 분할 모양에 따른 최악 O(n²)을 함께 적습니다.
• 실수: 제자리라는 이유로 공간 O(1)이라 단정하기 해결: 재귀 호출 스택을 공간에 포함합니다.

✎7. 직접 실습

✎직접 실습

1. 첫 원소 피벗에서 정렬된 배열의 분할 모양을 그립니다.
2. 중복값이 많은 입력을 테스트합니다.
3. 병합 정렬과 시간·공간·안정성을 표로 비교합니다.

실습 기록에는 입력 크기, 예상 결과, 실제 결과, 시간·공간 복잡도와 사용한 JDK 버전을 함께 남깁니다. 실제 사용자 ID나 개인정보 대신 P1, P2 같은 가상 데이터를 사용합니다.

?8. 이해 점검 질문 3개

?이해 점검

1. 파티션이 끝난 뒤 보장되는 조건은 무엇인가요?
2. 퀵 정렬이 O(n²)이 되는 분할 모양은 무엇인가요?
3. 제자리 구현에도 추가 공간이 필요한 이유는 무엇인가요?

■9. 핵심 요약

■핵심 요약

퀵 정렬은 피벗 분할이 균형이면 빠르고 메모리 지역성이 좋지만 최악 O(n²)이 가능합니다. 평균과 최악, 재귀 스택, 안정성을 분리해 평가합니다.