11강. 버블·선택·삽입 정렬: 느리지만 중요한 기본 원리

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

표준 sort만 호출하면 정렬 과정의 비교와 이동 비용, 이미 정렬된 입력에서의 차이를 체감하기 어렵습니다.

✓2. 학습 목표

✓이 강의를 마치면

• 버블·선택·삽입 정렬의 핵심 동작을 구분합니다.
• 최선·평균·최악 시간 복잡도를 비교합니다.
• 학습 구현과 실무 표준 정렬의 역할을 구분합니다.

◇3. 핵심 개념

버블 정렬은 인접 역순을 교환해 큰 값을 뒤로 보냅니다. 선택 정렬은 남은 구간의 최솟값을 골라 앞에 놓습니다. 삽입 정렬은 정렬된 앞 구간에 현재 값을 끼워 넣습니다. 버블과 삽입은 조기 종료 조건이 있으면 정렬된 입력에서 최선 O(n), 선택 정렬은 여전히 모든 비교를 해 O(n²)입니다. 세 알고리즘의 평균·최악은 O(n²)이며 큰 일반 입력에는 표준 정렬을 우선합니다.

✎4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

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

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

대상 파일: src/ElementarySorts.java

src/ElementarySorts.java

import java.util.Arrays;

public class ElementarySorts {
    static void bubbleSort(int[] values) {
        for (int end = values.length - 1; end > 0; end--) {
            boolean swapped = false;
            for (int i = 0; i < end; i++) {
                if (values[i] > values[i + 1]) {
                    swap(values, i, i + 1);
                    swapped = true;
                }
            }
            if (!swapped) return;
        }
    }

    static void selectionSort(int[] values) {
        for (int i = 0; i < values.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < values.length; j++) {
                if (values[j] < values[min]) min = j;
            }
            swap(values, i, min);
        }
    }

    static void insertionSort(int[] values) {
        for (int i = 1; i < values.length; i++) {
            int key = values[i];
            int j = i - 1;
            while (j >= 0 && values[j] > key) {
                values[j + 1] = values[j];
                j--;
            }
            values[j + 1] = key;
        }
    }

    static void swap(int[] values, int i, int j) {
        int temp = values[i];
        values[i] = values[j];
        values[j] = temp;
    }

    public static void main(String[] args) {
        int[] scores = {1200, 700, 1500, 900};
        int[] bubble = scores.clone();
        int[] selection = scores.clone();
        int[] insertion = scores.clone();
        bubbleSort(bubble);
        selectionSort(selection);
        insertionSort(insertion);
        System.out.println("버블: " + Arrays.toString(bubble));
        System.out.println("선택: " + Arrays.toString(selection));
        System.out.println("삽입: " + Arrays.toString(insertion));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

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

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

대상: src/ElementarySorts.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\ElementarySorts.java
java -cp .\out ElementarySorts

예상 결과: 버블·선택·삽입 세 줄 모두 [700, 900, 1200, 1500]을 출력합니다.

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

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

버블은 한 회전 뒤 가장 큰 남은 값을 끝에 고정하고, 선택은 가장 작은 남은 값의 위치를 찾아 앞에 고정합니다. 삽입은 i 앞 구간이 정렬되어 있다는 불변식을 유지하며 key보다 큰 값을 오른쪽으로 밉니다. 조기 종료 버블과 삽입은 이미 정렬된 입력에서 최선 O(n), 선택은 최선도 O(n²)입니다. 세 알고리즘의 평균·최악은 O(n²), 추가 공간은 O(1)입니다.

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

!자주 하는 실수

• 실수: 세 알고리즘을 모두 O(n²) 한 줄로만 외우기 해결: 최선 상황, 교환 횟수, 안정성 차이를 함께 비교합니다.
• 실수: 루프 경계를 잘못 잡아 첫 값이나 마지막 값을 빠뜨리기 해결: 작은 배열을 손으로 추적합니다.
• 실수: 학습 구현을 표준 sort보다 우선 사용하기 해결: 직접 구현은 원리 학습과 특수 제약에 한정합니다.

✎7. 직접 실습

✎직접 실습

1. 세 메서드에 비교·교환 또는 이동 횟수 카운터를 추가합니다.
2. 이미 정렬된 배열에서 버블 조기 종료와 선택 정렬의 비교 횟수를 비교합니다.
3. 빈 배열·한 원소·중복·역순 배열로 세 구현을 테스트합니다.

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

?8. 이해 점검 질문 3개

?이해 점검

1. 삽입 정렬의 반복 불변식은 무엇인가요?
2. 선택 정렬의 최선 시간도 O(n²)인 이유는 무엇인가요?
3. 작은 정렬 알고리즘을 배우는 목적은 무엇인가요?

■9. 핵심 요약

■핵심 요약

기본 정렬은 비교·이동·불변식을 눈으로 확인하기 좋습니다. 상황별 복잡도를 구분하되 큰 일반 입력에는 검증된 표준 정렬을 사용합니다.