버블 정렬, 삽입 정렬, 선택 정렬

정렬 알고리즘 개요

정렬이란?

정렬(Sorting)은 데이터를 특정 순서대로 나열하는 것입니다.

정렬 기준:

오름차순 (Ascending): 작은 값부터 큰 값 순서
내림차순 (Descending): 큰 값부터 작은 값 순서

예시:

정렬 전: [5, 2, 8, 1, 9]
         │  │  │  │  │
         └──┴──┴──┴──┘
            정렬 과정
         │  │  │  │  │
정렬 후: [1, 2, 5, 8, 9] (오름차순)

정렬 과정 시각화

입력 배열: [5, 2, 8, 1, 9]
           │
           └─ 정렬 전 상태

┌─────────────────────────────────────┐
│         정렬 알고리즘 적용          │
└─────────────────────────────────────┘
           │
           ├─ 버블 정렬: 인접 요소 비교 및 교환
           ├─ 삽입 정렬: 요소를 정렬된 부분에 삽입
           └─ 선택 정렬: 최소값 찾아서 교환
           │
           ↓

출력 배열: [1, 2, 5, 8, 9]
           │
           └─ 정렬 후 상태 (오름차순)

기본 정렬 알고리즘

이 문서에서는 다음 세 가지 기본 정렬 알고리즘을 다룹니다:

버블 정렬 (Bubble Sort)
삽입 정렬 (Insertion Sort)
선택 정렬 (Selection Sort)

공통 특징:

구현이 간단함
이해하기 쉬움
작은 데이터셋에 적합
시간 복잡도: O(n²)

버블 정렬 (Bubble Sort)

알고리즘 개요

버블 정렬은 인접한 두 요소를 비교하여 큰 값을 오른쪽으로 이동시키는 방식으로 정렬합니다.

특징:

가장 큰 값이 "거품"처럼 위로 올라가는 모습
구현이 매우 간단함
비효율적 (O(n²))

알고리즘 동작 원리

기본 아이디어:

배열의 첫 번째 요소부터 마지막 요소까지 순회
인접한 두 요소를 비교
왼쪽이 오른쪽보다 크면 교환
한 번의 순회가 끝나면 가장 큰 값이 맨 오른쪽에 위치
남은 요소들에 대해 반복

알고리즘 흐름도

시작
  ↓
배열 입력: [5, 2, 8, 1, 9]
  ↓
┌─────────────────────┐
│ 외부 루프 (i=0~n-2) │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ 내부 루프 (j=0~n-2-i)│
└─────────────────────┘
  ↓
┌─────────────────────┐
│ arr[j] > arr[j+1]?  │
└─────────────────────┘
  ↓
  ├─ 예 → [교환] ────┐
  │                  │
  └─ 아니오          │
  ↓                  │
┌─────────────────────┐│
│ j++ (다음 요소)     ││
└─────────────────────┘│
  ↓                    │
  └────────────────────┘
  ↓
┌─────────────────────┐
│ i++ (다음 순회)     │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ 모든 요소 정렬됨?   │
└─────────────────────┘
  ↓
  ├─ 아니오 → 외부 루프로
  │
  └─ 예 → 종료

도식화

예시: [5, 2, 8, 1, 9]를 오름차순으로 정렬

1단계: 첫 번째 순회 (i=0)

초기 상태: [5, 2, 8, 1, 9]
           ↑  ↑
         비교: 5 > 2 → 교환

[2, 5, 8, 1, 9]
      ↑  ↑
    비교: 5 < 8 → 유지

[2, 5, 8, 1, 9]
         ↑  ↑
       비교: 8 > 1 → 교환

[2, 5, 1, 8, 9]
            ↑  ↑
          비교: 8 < 9 → 유지

1단계 완료: [2, 5, 1, 8, 9]
                    ↑
                  가장 큰 값(9)이 맨 오른쪽에 위치

2단계: 두 번째 순회 (i=1)

현재 상태: [2, 5, 1, 8, 9]
           ↑  ↑
         비교: 2 < 5 → 유지

[2, 5, 1, 8, 9]
      ↑  ↑
    비교: 5 > 1 → 교환

[2, 1, 5, 8, 9]
         ↑  ↑
       비교: 5 < 8 → 유지

2단계 완료: [2, 1, 5, 8, 9]
                    ↑
                  두 번째로 큰 값(8)이 정렬됨

3단계: 세 번째 순회 (i=2)

현재 상태: [2, 1, 5, 8, 9]
           ↑  ↑
         비교: 2 > 1 → 교환

[1, 2, 5, 8, 9]
      ↑  ↑
    비교: 2 < 5 → 유지

3단계 완료: [1, 2, 5, 8, 9]
                  ↑
                정렬 완료!

Java 코드 구현

public class BubbleSort {
    /**
     * 버블 정렬 - 오름차순
     * @param arr 정렬할 배열
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;

        // 외부 루프: n-1번 반복 (마지막 요소는 자동으로 정렬됨)
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // 최적화: 교환이 일어났는지 확인

            // 내부 루프: 인접한 요소들을 비교
            // i번째 순회 후에는 뒤에서 i개의 요소가 이미 정렬됨
            for (int j = 0; j < n - 1 - i; j++) {
                // 인접한 두 요소 비교
                if (arr[j] > arr[j + 1]) {
                    // 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // 교환이 일어나지 않았다면 이미 정렬된 상태
            if (!swapped) {
                break; // 조기 종료 (최적화)
            }
        }
    }

    /**
     * 버블 정렬 - 내림차순
     */
    public static void bubbleSortDescending(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] < arr[j + 1]) { // 부등호 방향만 변경
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 테스트 코드
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};

        System.out.println("정렬 전: " + java.util.Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("정렬 후: " + java.util.Arrays.toString(arr));
    }
}

단계별 상세 설명

1. 외부 루프 (i):

for (int i = 0; i < n - 1; i++)

n-1번 반복 (마지막 요소는 자동으로 정렬됨)
각 반복마다 하나의 요소가 올바른 위치에 배치됨

2. 내부 루프 (j):

for (int j = 0; j < n - 1 - i; j++)

n - 1 - i: 이미 정렬된 요소는 제외
인접한 요소들을 비교하여 교환

3. 비교 및 교환:

if (arr[j] > arr[j + 1]) {
    int temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
}

4. 최적화 (조기 종료):

if (!swapped) {
    break; // 이미 정렬된 상태면 종료
}

시간 복잡도 분석

최선의 경우: O(n)

이미 정렬된 배열
조기 종료로 첫 번째 순회 후 종료

평균/최악의 경우: O(n²)

모든 요소를 비교해야 함
총 비교 횟수: n(n-1)/2

공간 복잡도: O(1)

추가 메모리 사용 없음

삽입 정렬 (Insertion Sort)

알고리즘 개요

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 정렬된 부분의 적절한 위치에 삽입하는 방식입니다.

특징:

카드를 정리하는 방식과 유사
작은 데이터셋에 매우 효율적
거의 정렬된 배열에 매우 빠름

알고리즘 동작 원리

기본 아이디어:

첫 번째 요소는 이미 정렬된 것으로 간주
두 번째 요소부터 순회 시작
현재 요소를 정렬된 부분의 적절한 위치에 삽입
삽입 위치를 찾기 위해 정렬된 부분을 역순으로 비교
모든 요소에 대해 반복

알고리즘 흐름도

시작
  ↓
배열 입력: [5, 2, 8, 1, 9]
  ↓
┌─────────────────────┐
│ 정렬된 부분: [5]    │
│ 정렬 안된 부분: [2,8,1,9]│
└─────────────────────┘
  ↓
┌─────────────────────┐
│ i=1부터 n-1까지 반복│
└─────────────────────┘
  ↓
┌─────────────────────┐
│ current = arr[i]    │
│ j = i - 1           │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ j >= 0 &&           │
│ arr[j] > current?   │
└─────────────────────┘
  ↓
  ├─ 예 → [arr[j+1] = arr[j], j--] ──┐
  │                                   │
  └─ 아니오                            │
  ↓                                   │
┌─────────────────────┐              │
│ arr[j+1] = current  │              │
└─────────────────────┘              │
  ↓                                   │
  └──────────────────────────────────┘
  ↓
┌─────────────────────┐
│ i++ (다음 요소)     │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ 모든 요소 처리됨?   │
└─────────────────────┘
  ↓
  ├─ 아니오 → 다음 요소로
  │
  └─ 예 → 종료

도식화

예시: [5, 2, 8, 1, 9]를 오름차순으로 정렬

초기 상태

[5, 2, 8, 1, 9]
 ↑
정렬된 부분 (첫 번째 요소만)

1단계: i=1 (요소 2 삽입)

[5, 2, 8, 1, 9]
 ↑  ↑
정렬된 부분 | 현재 요소

현재 요소: 2
정렬된 부분과 비교: 5 > 2 → 2를 5 앞에 삽입

[2, 5, 8, 1, 9]
 ↑  ↑
정렬된 부분 (2개)

2단계: i=2 (요소 8 삽입)

[2, 5, 8, 1, 9]
 ↑  ↑  ↑
정렬된 부분 | 현재 요소

현재 요소: 8
정렬된 부분과 비교: 5 < 8 → 이미 올바른 위치

[2, 5, 8, 1, 9]
 ↑     ↑
정렬된 부분 (3개)

3단계: i=3 (요소 1 삽입)

[2, 5, 8, 1, 9]
 ↑     ↑  ↑
정렬된 부분 | 현재 요소

현재 요소: 1
비교: 8 > 1 → 이동
[2, 5, 1, 8, 9]

비교: 5 > 1 → 이동
[2, 1, 5, 8, 9]

비교: 2 > 1 → 이동
[1, 2, 5, 8, 9]

[1, 2, 5, 8, 9]
 ↑        ↑
정렬된 부분 (4개)

4단계: i=4 (요소 9 삽입)

[1, 2, 5, 8, 9]
 ↑        ↑  ↑
정렬된 부분 | 현재 요소

현재 요소: 9
비교: 8 < 9 → 이미 올바른 위치

[1, 2, 5, 8, 9]
 ↑           ↑
정렬 완료!

Java 코드 구현

public class InsertionSort {
    /**
     * 삽입 정렬 - 오름차순
     * @param arr 정렬할 배열
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // 두 번째 요소부터 시작 (첫 번째는 이미 정렬된 것으로 간주)
        for (int i = 1; i < n; i++) {
            int current = arr[i]; // 현재 삽입할 요소
            int j = i - 1;       // 정렬된 부분의 마지막 인덱스

            // 정렬된 부분을 역순으로 순회하며 삽입 위치 찾기
            // current보다 큰 요소들을 오른쪽으로 이동
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j]; // 오른쪽으로 이동
                j--;                  // 왼쪽으로 이동
            }

            // 적절한 위치에 current 삽입
            arr[j + 1] = current;
        }
    }

    /**
     * 삽입 정렬 - 내림차순
     */
    public static void insertionSortDescending(int[] arr) {
        int n = arr.length;

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

            while (j >= 0 && arr[j] < current) { // 부등호 방향 변경
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = current;
        }
    }

    // 테스트 코드
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};

        System.out.println("정렬 전: " + java.util.Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("정렬 후: " + java.util.Arrays.toString(arr));
    }
}

단계별 상세 설명

1. 외부 루프 (i):

for (int i = 1; i < n; i++)

두 번째 요소(i=1)부터 시작
각 반복마다 하나의 요소를 정렬된 부분에 삽입

2. 현재 요소 저장:

int current = arr[i];

삽입할 요소를 임시 변수에 저장
이후 이동 과정에서 덮어쓰기 방지

3. 삽입 위치 찾기:

while (j >= 0 && arr[j] > current) {
    arr[j + 1] = arr[j];
    j--;
}

정렬된 부분을 역순으로 순회
current보다 큰 요소들을 오른쪽으로 이동
current보다 작거나 같은 요소를 찾으면 중단

4. 요소 삽입:

arr[j + 1] = current;

찾은 위치에 current 삽입

시간 복잡도 분석

최선의 경우: O(n)

이미 정렬된 배열
각 요소가 이미 올바른 위치에 있음

평균/최악의 경우: O(n²)

모든 요소를 비교하고 이동해야 함
총 비교 횟수: n(n-1)/2

공간 복잡도: O(1)

추가 메모리 사용 없음

특징:

거의 정렬된 배열에 매우 효율적
작은 데이터셋에 적합
안정 정렬 (Stable Sort)

선택 정렬 (Selection Sort)

알고리즘 개요

선택 정렬은 배열에서 가장 작은(또는 큰) 요소를 찾아서 맨 앞(또는 맨 뒤)으로 이동시키는 방식으로 정렬합니다.

특징:

가장 직관적인 정렬 알고리즘
구현이 간단함
불안정 정렬 (Unstable Sort)

알고리즘 동작 원리

기본 아이디어:

배열에서 가장 작은 요소를 찾음
가장 작은 요소를 첫 번째 위치와 교환
남은 배열에서 다시 가장 작은 요소를 찾음
두 번째 위치와 교환
모든 요소에 대해 반복

알고리즘 흐름도

시작
  ↓
배열 입력: [5, 2, 8, 1, 9]
  ↓
┌─────────────────────┐
│ i=0부터 n-2까지 반복│
└─────────────────────┘
  ↓
┌─────────────────────┐
│ minIndex = i        │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ j=i+1부터 n-1까지   │
│ 반복하여 최소값 찾기│
└─────────────────────┘
  ↓
┌─────────────────────┐
│ arr[j] < arr[minIndex]?│
└─────────────────────┘
  ↓
  ├─ 예 → [minIndex = j] ──┐
  │                        │
  └─ 아니오                │
  ↓                        │
┌─────────────────────┐   │
│ j++ (다음 요소)     │   │
└─────────────────────┘   │
  ↓                        │
  └────────────────────────┘
  ↓
┌─────────────────────┐
│ minIndex != i?      │
└─────────────────────┘
  ↓
  ├─ 예 → [arr[i] ↔ arr[minIndex]] ──┐
  │                                   │
  └─ 아니오                            │
  ↓                                   │
┌─────────────────────┐              │
│ i++ (다음 위치)     │              │
└─────────────────────┘              │
  ↓                                   │
  └──────────────────────────────────┘
  ↓
┌─────────────────────┐
│ 모든 요소 정렬됨?   │
└─────────────────────┘
  ↓
  ├─ 아니오 → 다음 위치로
  │
  └─ 예 → 종료

도식화

예시: [5, 2, 8, 1, 9]를 오름차순으로 정렬

1단계: i=0 (가장 작은 요소 찾기)

[5, 2, 8, 1, 9]
 ↑
시작 위치

전체 배열에서 가장 작은 요소 찾기:
5, 2, 8, 1, 9 → 가장 작은 값: 1 (인덱스 3)

[5, 2, 8, 1, 9]
 ↑           ↑
시작 위치 | 최소값

교환: arr[0] ↔ arr[3]

[1, 2, 8, 5, 9]
 ↑
정렬된 부분 (1개)

2단계: i=1 (두 번째로 작은 요소 찾기)

[1, 2, 8, 5, 9]
    ↑
시작 위치 (정렬된 부분 제외)

남은 배열 [2, 8, 5, 9]에서 가장 작은 요소 찾기:
2, 8, 5, 9 → 가장 작은 값: 2 (인덱스 1)

[1, 2, 8, 5, 9]
    ↑
이미 올바른 위치에 있음 (교환 불필요)

[1, 2, 8, 5, 9]
 ↑  ↑
정렬된 부분 (2개)

3단계: i=2 (세 번째로 작은 요소 찾기)

[1, 2, 8, 5, 9]
       ↑
시작 위치

남은 배열 [8, 5, 9]에서 가장 작은 요소 찾기:
8, 5, 9 → 가장 작은 값: 5 (인덱스 3)

[1, 2, 8, 5, 9]
       ↑  ↑
시작 위치 | 최소값

교환: arr[2] ↔ arr[3]

[1, 2, 5, 8, 9]
 ↑     ↑
정렬된 부분 (3개)

4단계: i=3 (네 번째로 작은 요소 찾기)

[1, 2, 5, 8, 9]
          ↑
시작 위치

남은 배열 [8, 9]에서 가장 작은 요소 찾기:
8, 9 → 가장 작은 값: 8 (인덱스 3)

[1, 2, 5, 8, 9]
          ↑
이미 올바른 위치에 있음

[1, 2, 5, 8, 9]
 ↑        ↑
정렬 완료!

Java 코드 구현

public class SelectionSort {
    /**
     * 선택 정렬 - 오름차순
     * @param arr 정렬할 배열
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 외부 루프: n-1번 반복 (마지막 요소는 자동으로 정렬됨)
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 최소값의 인덱스

            // 내부 루프: i+1부터 끝까지 최소값 찾기
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 더 작은 값을 찾으면 인덱스 업데이트
                }
            }

            // 최소값을 현재 위치와 교환
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    /**
     * 선택 정렬 - 내림차순
     */
    public static void selectionSortDescending(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int maxIndex = i; // 최대값의 인덱스

            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[maxIndex]) { // 부등호 방향 변경
                    maxIndex = j;
                }
            }

            if (maxIndex != i) {
                int temp = arr[i];
                arr[i] = arr[maxIndex];
                arr[maxIndex] = temp;
            }
        }
    }

    // 테스트 코드
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};

        System.out.println("정렬 전: " + java.util.Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("정렬 후: " + java.util.Arrays.toString(arr));
    }
}

단계별 상세 설명

1. 외부 루프 (i):

for (int i = 0; i < n - 1; i++)

n-1번 반복
각 반복마다 하나의 요소가 올바른 위치에 배치됨

2. 최소값 찾기:

int minIndex = i;
for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[minIndex]) {
        minIndex = j;
    }
}

i+1부터 끝까지 순회하며 최소값의 인덱스 찾기
minIndex에 최소값의 인덱스 저장

3. 교환:

if (minIndex != i) {
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

최소값을 현재 위치(i)와 교환
이미 올바른 위치에 있으면 교환 불필요

시간 복잡도 분석

모든 경우: O(n²)

최선, 평균, 최악 모두 동일
항상 모든 요소를 비교해야 함
총 비교 횟수: n(n-1)/2

공간 복잡도: O(1)

추가 메모리 사용 없음

특징:

교환 횟수가 적음 (최대 n-1번)
불안정 정렬 (같은 값의 요소 순서가 바뀔 수 있음)

세 가지 알고리즘 비교

비교 표

항목	버블 정렬	삽입 정렬	선택 정렬
시간 복잡도 (최선)	O(n)	O(n)	O(n²)
시간 복잡도 (평균)	O(n²)	O(n²)	O(n²)
시간 복잡도 (최악)	O(n²)	O(n²)	O(n²)
공간 복잡도	O(1)	O(1)	O(1)
안정 정렬	예	예	아니오
적응형	예 (조기 종료)	예	아니오
교환 횟수	많음	중간	적음
비교 횟수	많음	중간	많음
이미 정렬된 배열	빠름	매우 빠름	느림
역순 배열	느림	느림	느림
작은 데이터셋	적합	매우 적합	적합
큰 데이터셋	비적합	비적합	비적합

시각적 비교 다이어그램

시간 복잡도 비교

시간 복잡도 (최선의 경우)
┌─────────────────────────────────────┐
│                                     │
│ O(n²) ──────────────────────────── │ 선택 정렬
│                                     │
│ O(n) ────────────────               │ 버블 정렬
│                                     │ 삽입 정렬
│                                     │
└─────────────────────────────────────┘
     작은 n              큰 n

시간 복잡도 (평균/최악의 경우)
┌─────────────────────────────────────┐
│                                     │
│ O(n²) ──────────────────────────── │ 모두 동일
│                                     │
│                                     │
│                                     │
└─────────────────────────────────────┘
     작은 n              큰 n

교환 횟수 비교

교환 횟수 (배열 크기 n=5인 경우)
┌─────────────────────────────────────┐
│                                     │
│ 많음 ────────────────               │ 버블 정렬
│                                     │ (평균 10회)
│ 중간 ────────────────               │ 삽입 정렬
│                                     │ (평균 5회)
│ 적음 ────────────────               │ 선택 정렬
│                                     │ (최대 4회)
└─────────────────────────────────────┘

안정성 및 적응형 비교

안정 정렬 여부
┌─────────────┬─────────────┬─────────────┐
│ 버블 정렬   │ 삽입 정렬   │ 선택 정렬   │
│    ✅       │    ✅       │    ❌       │
└─────────────┴─────────────┴─────────────┘

적응형 여부
┌─────────────┬─────────────┬─────────────┐
│ 버블 정렬   │ 삽입 정렬   │ 선택 정렬   │
│    ✅       │    ✅       │    ❌       │
│ (조기 종료) │ (빠른 삽입) │ (항상 동일) │
└─────────────┴─────────────┴─────────────┘

시각적 비교

정렬 과정 비교 (배열: [5, 2, 8, 1, 9])

버블 정렬:

[5,2,8,1,9] → [2,5,8,1,9] → [2,5,1,8,9] → [2,1,5,8,9] → [1,2,5,8,9]
인접 요소 비교 및 교환

삽입 정렬:

[5,2,8,1,9] → [2,5,8,1,9] → [2,5,8,1,9] → [1,2,5,8,9] → [1,2,5,8,9]
요소를 정렬된 부분에 삽입

선택 정렬:

[5,2,8,1,9] → [1,2,8,5,9] → [1,2,8,5,9] → [1,2,5,8,9] → [1,2,5,8,9]
최소값을 찾아서 교환

언제 무엇을 사용할까?

버블 정렬:

✅ 교육 목적 (이해하기 쉬움)
✅ 이미 거의 정렬된 배열
❌ 큰 데이터셋
❌ 실전 사용 (비효율적)

삽입 정렬:

✅ 작은 데이터셋 (n < 50)
✅ 이미 거의 정렬된 배열
✅ 실시간 데이터 스트림
✅ 다른 정렬 알고리즘의 하이브리드에 사용
❌ 큰 데이터셋

선택 정렬:

✅ 교환 비용이 높은 경우 (메모리 이동이 적음)
✅ 간단한 구현이 필요한 경우
❌ 실전 사용 (비효율적)
❌ 안정 정렬이 필요한 경우

알고리즘 선택 가이드 플로우차트

정렬 알고리즘 선택
  ↓
┌─────────────────────┐
│ 데이터 크기는?      │
└─────────────────────┘
  ↓
  ├─ 작음 (n < 50) ────────────────┐
  │                                 │
  └─ 큼 (n ≥ 50) ──────────────────┐
  ↓                                 │
┌─────────────────────┐            │
│ 이미 정렬되어 있나? │            │
└─────────────────────┘            │
  ↓                                 │
  ├─ 예 → [삽입 정렬] ──────────────┤
  │                                 │
  └─ 아니오                          │
  ↓                                 │
┌─────────────────────┐            │
│ 교육/학습 목적인가? │            │
└─────────────────────┘            │
  ↓                                 │
  ├─ 예 → [버블 정렬] ──────────────┤
  │                                 │
  └─ 아니오                          │
  ↓                                 │
┌─────────────────────┐            │
│ 교환 비용이 높은가? │            │
└─────────────────────┘            │
  ↓                                 │
  ├─ 예 → [선택 정렬] ──────────────┤
  │                                 │
  └─ 아니오                          │
  ↓                                 │
┌─────────────────────┐            │
│ 실전 사용인가?      │            │
└─────────────────────┘            │
  ↓                                 │
  └─ 예 → [더 효율적인 알고리즘 권장]│
        (퀵 정렬, 병합 정렬 등)     │
                                      │
──────────────────────────────────────┘

실전 예제 코드

통합 예제 프로그램

import java.util.Arrays;
import java.util.Scanner;

public class SortingAlgorithmsDemo {

    // 버블 정렬
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

    // 삽입 정렬
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    }

    // 선택 정렬
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    // 배열 복사 (원본 보존)
    public static int[] copyArray(int[] arr) {
        return Arrays.copyOf(arr, arr.length);
    }

    // 메인 메서드
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("배열 크기 입력: ");
        int n = sc.nextInt();

        int[] original = new int[n];
        System.out.println("배열 요소 입력:");
        for (int i = 0; i < n; i++) {
            original[i] = sc.nextInt();
        }

        System.out.println("\n원본 배열: " + Arrays.toString(original));

        // 버블 정렬
        int[] arr1 = copyArray(original);
        bubbleSort(arr1);
        System.out.println("버블 정렬: " + Arrays.toString(arr1));

        // 삽입 정렬
        int[] arr2 = copyArray(original);
        insertionSort(arr2);
        System.out.println("삽입 정렬: " + Arrays.toString(arr2));

        // 선택 정렬
        int[] arr3 = copyArray(original);
        selectionSort(arr3);
        System.out.println("선택 정렬: " + Arrays.toString(arr3));

        sc.close();
    }
}

실행 예시

배열 크기 입력: 5
배열 요소 입력:
5
2
8
1
9

원본 배열: [5, 2, 8, 1, 9]
버블 정렬: [1, 2, 5, 8, 9]
삽입 정렬: [1, 2, 5, 8, 9]
선택 정렬: [1, 2, 5, 8, 9]

성능 분석

시간 복잡도 비교

최선의 경우:

버블 정렬: O(n) - 조기 종료
삽입 정렬: O(n) - 이미 정렬된 배열
선택 정렬: O(n²) - 항상 모든 요소 비교

평균/최악의 경우:

모두 O(n²)

시간 복잡도 비교 그래프

연산 횟수 (n² 기준)
┌─────────────────────────────────────────┐
│                                         │
│ n² ──────────────────────────────────── │ 선택 정렬 (최선)
│                                         │ 버블/삽입 (평균/최악)
│                                         │
│                                         │
│ n ────────────────                      │ 버블 정렬 (최선)
│                                         │ 삽입 정렬 (최선)
│                                         │
│                                         │
└─────────────────────────────────────────┘
    10    50    100   500   1000
         배열 크기 (n)

공간 복잡도

모두 O(1):

추가 메모리 사용 없음
제자리 정렬 (In-place Sort)

공간 복잡도 비교

메모리 사용량
┌─────────────────────────────────────────┐
│                                         │
│ O(1) ───────────────────────────────── │ 모두 동일
│                                         │ (추가 메모리 없음)
│                                         │
│                                         │
│                                         │
└─────────────────────────────────────────┘
    10    50    100   500   1000
         배열 크기 (n)

실제 성능 테스트

작은 배열 (n=10):

세 알고리즘 모두 비슷한 성능

중간 배열 (n=100):

삽입 정렬이 약간 빠름
버블 정렬과 선택 정렬은 비슷

큰 배열 (n=1000):

모두 느림 (O(n²)의 한계)
실전에서는 더 효율적인 알고리즘 사용 권장

성능 비교 시각화

실행 시간 비교 (상대적)
┌─────────────────────────────────────────┐
│                                         │
│ 느림 ────────────────────────────────── │ 선택 정렬 (n=1000)
│                                         │ 버블 정렬 (n=1000)
│ 중간 ────────────────────────────────── │ 삽입 정렬 (n=1000)
│                                         │
│ 빠름 ────────────────────────────────── │ 삽입 정렬 (n=10)
│                                         │ 버블 정렬 (n=10)
│                                         │ 선택 정렬 (n=10)
└─────────────────────────────────────────┘

데이터 크기에 따른 성능 변화
┌─────────────────────────────────────────┐
│                                         │
│ 시간 ────────────────────────────────── │ n=1000
│                                         │
│       ──────────────────────────────── │ n=100
│                                         │
│             ────────────────────────── │ n=10
│                                         │
└─────────────────────────────────────────┘
     버블    삽입    선택
     정렬    정렬    정렬

연습 문제

문제 1: 내림차순 정렬

각 알고리즘을 내림차순으로 정렬하도록 수정하세요.

문제 2: 문자열 배열 정렬

정수 배열 대신 문자열 배열을 정렬하도록 수정하세요.

힌트:

public static void bubbleSort(String[] arr) {
    // String.compareTo() 사용
    if (arr[j].compareTo(arr[j + 1]) > 0) {
        // 교환
    }
}

문제 3: 객체 배열 정렬

Student 객체 배열을 이름 순으로 정렬하도록 구현하세요.

문제 4: 정렬 과정 출력

각 단계마다 배열의 상태를 출력하도록 수정하세요.

문제 5: 비교 횟수 카운트

각 알고리즘의 비교 횟수를 카운트하여 출력하세요.

문제 6: 성능 측정

각 알고리즘의 실행 시간을 측정하여 비교하세요.

힌트:

long startTime = System.nanoTime();
bubbleSort(arr);
long endTime = System.nanoTime();
System.out.println("실행 시간: " + (endTime - startTime) + " ns");

연습 문제 답안

문제 1: 내림차순 정렬

답안:

각 알고리즘의 비교 연산자 방향만 변경하면 됩니다.

버블 정렬:

public static void bubbleSortDescending(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) { // 부등호 방향 변경: > → <
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

삽입 정렬:

public static void insertionSortDescending(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int current = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] < current) { // 부등호 방향 변경: > → <
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
}

선택 정렬:

public static void selectionSortDescending(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int maxIndex = i; // 최소값 대신 최대값 찾기
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[maxIndex]) { // 부등호 방향 변경: < → >
                maxIndex = j;
            }
        }
        if (maxIndex != i) {
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }
}

문제 2: 문자열 배열 정렬

답안:

버블 정렬:

public static void bubbleSort(String[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            // String.compareTo() 사용
            if (arr[j].compareTo(arr[j + 1]) > 0) {
                String temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

삽입 정렬:

public static void insertionSort(String[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        String current = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j].compareTo(current) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
}

선택 정렬:

public static void selectionSort(String[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j].compareTo(arr[minIndex]) < 0) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            String temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

테스트 코드:

public static void main(String[] args) {
    String[] arr = {"banana", "apple", "cherry", "date"};
    System.out.println("정렬 전: " + Arrays.toString(arr));
    bubbleSort(arr);
    System.out.println("정렬 후: " + Arrays.toString(arr));
    // 출력: [apple, banana, cherry, date]
}

문제 3: 객체 배열 정렬

답안:

Student 클래스:

class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

버블 정렬:

public static void bubbleSort(Student[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j].getName().compareTo(arr[j + 1].getName()) > 0) {
                Student temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

삽입 정렬:

public static void insertionSort(Student[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        Student current = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j].getName().compareTo(current.getName()) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
}

선택 정렬:

public static void selectionSort(Student[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j].getName().compareTo(arr[minIndex].getName()) < 0) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            Student temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

테스트 코드:

public static void main(String[] args) {
    Student[] students = {
        new Student("Charlie", 20),
        new Student("Alice", 19),
        new Student("Bob", 21)
    };

    System.out.println("정렬 전: " + Arrays.toString(students));
    bubbleSort(students);
    System.out.println("정렬 후: " + Arrays.toString(students));
    // 출력: [Alice(19), Bob(21), Charlie(20)]
}

문제 4: 정렬 과정 출력

답안:

버블 정렬 (과정 출력):

public static void bubbleSortWithSteps(int[] arr) {
    int n = arr.length;
    System.out.println("정렬 시작: " + Arrays.toString(arr));

    for (int i = 0; i < n - 1; i++) {
        System.out.println("\n" + (i + 1) + "단계:");
        boolean swapped = false;

        for (int j = 0; j < n - 1 - i; j++) {
            System.out.print("  비교: arr[" + j + "]=" + arr[j] + 
                           " vs arr[" + (j+1) + "]=" + arr[j+1]);

            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
                System.out.println(" → 교환!");
            } else {
                System.out.println(" → 유지");
            }
        }

        System.out.println("  결과: " + Arrays.toString(arr));

        if (!swapped) {
            System.out.println("  조기 종료 (이미 정렬됨)");
            break;
        }
    }

    System.out.println("\n최종 결과: " + Arrays.toString(arr));
}

삽입 정렬 (과정 출력):

public static void insertionSortWithSteps(int[] arr) {
    int n = arr.length;
    System.out.println("정렬 시작: " + Arrays.toString(arr));

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

        System.out.println("\n" + i + "단계: 요소 " + current + " 삽입");
        System.out.println("  정렬된 부분: " + 
                          Arrays.toString(Arrays.copyOf(arr, i)));
        System.out.println("  현재 요소: " + current);

        while (j >= 0 && arr[j] > current) {
            System.out.println("    비교: " + arr[j] + " > " + current + " → 이동");
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = current;
        System.out.println("  삽입 위치: 인덱스 " + (j + 1));
        System.out.println("  결과: " + Arrays.toString(arr));
    }

    System.out.println("\n최종 결과: " + Arrays.toString(arr));
}

선택 정렬 (과정 출력):

public static void selectionSortWithSteps(int[] arr) {
    int n = arr.length;
    System.out.println("정렬 시작: " + Arrays.toString(arr));

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        System.out.println("\n" + (i + 1) + "단계: 인덱스 " + i + "부터 최소값 찾기");

        for (int j = i + 1; j < n; j++) {
            System.out.print("  비교: arr[" + minIndex + "]=" + arr[minIndex] + 
                           " vs arr[" + j + "]=" + arr[j]);
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
                System.out.println(" → 새로운 최소값!");
            } else {
                System.out.println(" → 유지");
            }
        }

        System.out.println("  최소값: " + arr[minIndex] + " (인덱스 " + minIndex + ")");

        if (minIndex != i) {
            System.out.println("  교환: arr[" + i + "]=" + arr[i] + 
                             " ↔ arr[" + minIndex + "]=" + arr[minIndex]);
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        } else {
            System.out.println("  이미 올바른 위치에 있음 (교환 불필요)");
        }

        System.out.println("  결과: " + Arrays.toString(arr));
    }

    System.out.println("\n최종 결과: " + Arrays.toString(arr));
}

문제 5: 비교 횟수 카운트

답안:

버블 정렬 (비교 횟수 카운트):

public static int bubbleSortWithCount(int[] arr) {
    int n = arr.length;
    int compareCount = 0;

    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            compareCount++; // 비교 횟수 증가
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }

    return compareCount;
}

삽입 정렬 (비교 횟수 카운트):

public static int insertionSortWithCount(int[] arr) {
    int n = arr.length;
    int compareCount = 0;

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

        while (j >= 0) {
            compareCount++; // 비교 횟수 증가
            if (arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            } else {
                break;
            }
        }

        arr[j + 1] = current;
    }

    return compareCount;
}

선택 정렬 (비교 횟수 카운트):

public static int selectionSortWithCount(int[] arr) {
    int n = arr.length;
    int compareCount = 0;

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            compareCount++; // 비교 횟수 증가
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    return compareCount;
}

테스트 코드:

public static void main(String[] args) {
    int[] arr = {5, 2, 8, 1, 9};
    int[] arr1 = Arrays.copyOf(arr, arr.length);
    int[] arr2 = Arrays.copyOf(arr, arr.length);
    int[] arr3 = Arrays.copyOf(arr, arr.length);

    System.out.println("원본 배열: " + Arrays.toString(arr));

    int count1 = bubbleSortWithCount(arr1);
    System.out.println("버블 정렬 비교 횟수: " + count1);

    int count2 = insertionSortWithCount(arr2);
    System.out.println("삽입 정렬 비교 횟수: " + count2);

    int count3 = selectionSortWithCount(arr3);
    System.out.println("선택 정렬 비교 횟수: " + count3);
}

문제 6: 성능 측정

답안:

성능 측정 함수:

public static void measurePerformance() {
    // 테스트 데이터 생성
    int[] sizes = {100, 500, 1000, 5000};

    for (int size : sizes) {
        System.out.println("\n=== 배열 크기: " + size + " ===");

        // 랜덤 배열 생성
        int[] arr1 = generateRandomArray(size);
        int[] arr2 = Arrays.copyOf(arr1, arr1.length);
        int[] arr3 = Arrays.copyOf(arr1, arr1.length);

        // 버블 정렬 측정
        long start1 = System.nanoTime();
        bubbleSort(arr1);
        long end1 = System.nanoTime();
        long time1 = end1 - start1;

        // 삽입 정렬 측정
        long start2 = System.nanoTime();
        insertionSort(arr2);
        long end2 = System.nanoTime();
        long time2 = end2 - start2;

        // 선택 정렬 측정
        long start3 = System.nanoTime();
        selectionSort(arr3);
        long end3 = System.nanoTime();
        long time3 = end3 - start3;

        System.out.println("버블 정렬:   " + time1 + " ns (" + (time1 / 1_000_000.0) + " ms)");
        System.out.println("삽입 정렬:   " + time2 + " ns (" + (time2 / 1_000_000.0) + " ms)");
        System.out.println("선택 정렬:   " + time3 + " ns (" + (time3 / 1_000_000.0) + " ms)");
    }
}

// 랜덤 배열 생성 헬퍼 메서드
public static int[] generateRandomArray(int size) {
    int[] arr = new int[size];
    Random random = new Random();
    for (int i = 0; i < size; i++) {
        arr[i] = random.nextInt(1000);
    }
    return arr;
}

더 정확한 측정 (여러 번 실행하여 평균):

public static void measurePerformanceAverage() {
    int[] sizes = {100, 500, 1000};
    int iterations = 10; // 10번 실행하여 평균

    for (int size : sizes) {
        System.out.println("\n=== 배열 크기: " + size + " (평균 " + iterations + "회 실행) ===");

        long total1 = 0, total2 = 0, total3 = 0;

        for (int i = 0; i < iterations; i++) {
            int[] arr1 = generateRandomArray(size);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);

            // 버블 정렬
            long start = System.nanoTime();
            bubbleSort(arr1);
            total1 += System.nanoTime() - start;

            // 삽입 정렬
            start = System.nanoTime();
            insertionSort(arr2);
            total2 += System.nanoTime() - start;

            // 선택 정렬
            start = System.nanoTime();
            selectionSort(arr3);
            total3 += System.nanoTime() - start;
        }

        System.out.println("버블 정렬 평균: " + (total1 / iterations / 1_000_000.0) + " ms");
        System.out.println("삽입 정렬 평균: " + (total2 / iterations / 1_000_000.0) + " ms");
        System.out.println("선택 정렬 평균: " + (total3 / iterations / 1_000_000.0) + " ms");
    }
}

이미 정렬된 배열에서의 성능 측정:

public static void measurePerformanceSorted() {
    int[] sizes = {100, 500, 1000};

    for (int size : sizes) {
        System.out.println("\n=== 이미 정렬된 배열 크기: " + size + " ===");

        // 이미 정렬된 배열 생성
        int[] arr1 = new int[size];
        for (int i = 0; i < size; i++) {
            arr1[i] = i;
        }

        int[] arr2 = Arrays.copyOf(arr1, arr1.length);
        int[] arr3 = Arrays.copyOf(arr1, arr1.length);

        long start1 = System.nanoTime();
        bubbleSort(arr1);
        long time1 = System.nanoTime() - start1;

        long start2 = System.nanoTime();
        insertionSort(arr2);
        long time2 = System.nanoTime() - start2;

        long start3 = System.nanoTime();
        selectionSort(arr3);
        long time3 = System.nanoTime() - start3;

        System.out.println("버블 정렬: " + (time1 / 1_000_000.0) + " ms");
        System.out.println("삽입 정렬: " + (time2 / 1_000_000.0) + " ms");
        System.out.println("선택 정렬: " + (time3 / 1_000_000.0) + " ms");
    }
}

요약

핵심 정리

버블 정렬: 인접 요소를 비교하여 교환, 가장 큰 값이 오른쪽으로 이동
삽입 정렬: 요소를 정렬된 부분에 삽입, 카드 정리와 유사
선택 정렬: 최소값을 찾아서 교환, 가장 직관적

알고리즘 비교 요약표

┌─────────────────────────────────────────────────────────────┐
│                    정렬 알고리즘 비교                        │
├──────────────┬──────────────┬──────────────┬─────────────────┤
│   항목       │  버블 정렬   │  삽입 정렬   │   선택 정렬      │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 시간 복잡도  │              │              │                 │
│ (최선)       │    O(n)      │    O(n)      │    O(n²)        │
│ (평균/최악)  │    O(n²)     │    O(n²)     │    O(n²)        │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 공간 복잡도  │    O(1)      │    O(1)      │    O(1)         │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 안정 정렬    │     ✅       │     ✅       │     ❌          │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 적응형       │     ✅       │     ✅       │     ❌          │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 교환 횟수    │    많음      │    중간      │    적음         │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 비교 횟수    │    많음      │    중간      │    많음         │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 작은 데이터  │    적합      │  매우 적합   │    적합         │
├──────────────┼──────────────┼──────────────┼─────────────────┤
│ 큰 데이터    │   비적합     │   비적합     │   비적합        │
└──────────────┴──────────────┴──────────────┴─────────────────┘

공통 특징

모두 O(n²) 시간 복잡도
모두 O(1) 공간 복잡도
작은 데이터셋에 적합
구현이 간단함

알고리즘별 특징 시각화

버블 정렬
┌─────────────────────────────────────┐
│  [5,2,8,1,9]                        │
│   ↑↑                                │
│   비교 및 교환                       │
│  [2,5,8,1,9]                        │
│     ↑↑                              │
│     비교 및 교환                     │
│  ...                                │
│  [1,2,5,8,9]                        │
└─────────────────────────────────────┘
특징: 인접 요소 비교, 가장 큰 값이 오른쪽으로

삽입 정렬
┌─────────────────────────────────────┐
│  [5] | [2,8,1,9]                    │
│  정렬된 부분 | 정렬 안된 부분        │
│                                      │
│  [2,5] | [8,1,9]                    │
│  정렬된 부분 | 정렬 안된 부분        │
│                                      │
│  [2,5,8] | [1,9]                    │
│  ...                                │
│  [1,2,5,8,9]                        │
└─────────────────────────────────────┘
특징: 요소를 정렬된 부분에 삽입

선택 정렬
┌─────────────────────────────────────┐
│  [5,2,8,1,9]                        │
│   ↑        ↑                        │
│  시작    최소값 찾기                 │
│  [1,2,8,5,9]                        │
│     ↑                               │
│  다음 위치에서 최소값 찾기            │
│  ...                                │
│  [1,2,5,8,9]                        │
└─────────────────────────────────────┘
특징: 최소값 찾아서 교환

선택 가이드

교육 목적: 버블 정렬 (가장 이해하기 쉬움)
작은 데이터셋: 삽입 정렬 (가장 효율적)
교환 비용이 높은 경우: 선택 정렬 (교환 횟수 적음)
실전 사용: 더 효율적인 알고리즘 권장 (퀵 정렬, 병합 정렬 등)

학습 로드맵

정렬 알고리즘 학습 순서
  ↓
┌─────────────────────┐
│ 1. 버블 정렬        │ ← 가장 이해하기 쉬움
│    (기본 개념)      │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ 2. 선택 정렬        │ ← 직관적
│    (최소값 찾기)    │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ 3. 삽입 정렬        │ ← 실용적
│    (삽입 개념)      │
└─────────────────────┘
  ↓
┌─────────────────────┐
│ 4. 고급 정렬        │ ← 다음 단계
│    (퀵, 병합 등)    │
└─────────────────────┘

작성일: 2026-01-30
범위: 버블 정렬, 삽입 정렬, 선택 정렬

'BackEnd > Java' 카테고리의 다른 글

JavaAir 항공 예약 시스템 - 해설 (0)	2026.02.14
JavaAir 항공 예약 시스템 - 코딩 문제 (0)	2026.02.14
String 주요 메서드 예제 (0)	2026.02.09
Stream API 연습문제 - 도서 관리 시스템 문제 - 풀이 (0)	2026.01.30
Java 람다 표현식 (0)	2026.01.28

버블 정렬, 삽입 정렬, 선택 정렬

버블 정렬, 삽입 정렬, 선택 정렬

목차

정렬 알고리즘 개요

정렬이란?

정렬 과정 시각화

기본 정렬 알고리즘

버블 정렬 (Bubble Sort)

알고리즘 개요

알고리즘 동작 원리

알고리즘 흐름도

도식화

1단계: 첫 번째 순회 (i=0)

2단계: 두 번째 순회 (i=1)

3단계: 세 번째 순회 (i=2)

Java 코드 구현

단계별 상세 설명

시간 복잡도 분석

삽입 정렬 (Insertion Sort)

알고리즘 개요

알고리즘 동작 원리

알고리즘 흐름도

도식화

초기 상태

1단계: i=1 (요소 2 삽입)

2단계: i=2 (요소 8 삽입)

3단계: i=3 (요소 1 삽입)

4단계: i=4 (요소 9 삽입)

Java 코드 구현

단계별 상세 설명

시간 복잡도 분석

선택 정렬 (Selection Sort)

알고리즘 개요

알고리즘 동작 원리

알고리즘 흐름도

도식화

1단계: i=0 (가장 작은 요소 찾기)

2단계: i=1 (두 번째로 작은 요소 찾기)

3단계: i=2 (세 번째로 작은 요소 찾기)

4단계: i=3 (네 번째로 작은 요소 찾기)

Java 코드 구현

단계별 상세 설명

시간 복잡도 분석

세 가지 알고리즘 비교

비교 표

시각적 비교 다이어그램

시간 복잡도 비교

교환 횟수 비교

안정성 및 적응형 비교

시각적 비교

언제 무엇을 사용할까?

알고리즘 선택 가이드 플로우차트

실전 예제 코드

통합 예제 프로그램

실행 예시

성능 분석

시간 복잡도 비교

시간 복잡도 비교 그래프

공간 복잡도

공간 복잡도 비교

실제 성능 테스트

성능 비교 시각화

연습 문제

문제 1: 내림차순 정렬

문제 2: 문자열 배열 정렬

문제 3: 객체 배열 정렬

문제 4: 정렬 과정 출력

문제 5: 비교 횟수 카운트

문제 6: 성능 측정

연습 문제 답안

문제 1: 내림차순 정렬

문제 2: 문자열 배열 정렬

문제 3: 객체 배열 정렬

문제 4: 정렬 과정 출력

문제 5: 비교 횟수 카운트

문제 6: 성능 측정

요약

핵심 정리

알고리즘 비교 요약표

공통 특징