bubble sort, insertion sort, selection sort를 설명해 주세요.

Question

Accepted Answer

이들은 세 가지 단순한 **O(n²)** 비교 정렬입니다. 큰 입력에서는 느리지만 이해하기 쉽고 정렬의 동작 원리를 가르치는 데 유용합니다.

## 각각의 동작 방식

- **Bubble sort:** 인접한 순서가 잘못된 쌍을 반복적으로 교환합니다. 큰 값이 매 패스마다 끝으로 "거품처럼 떠오릅니다".
- **Selection sort:** 정렬되지 않은 부분의 최솟값을 찾아 제자리로 교환합니다.
- **Insertion sort:** 각 새 원소를 올바른 위치에 삽입하여 정렬된 접두부를 키워 갑니다.

## 예시 (insertion sort)

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # 배치할 원소
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # 더 큰 원소들을 오른쪽으로 이동
            j -= 1
        arr[j + 1] = key              # 빈 자리에 key를 넣음
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## 비교

| 정렬 | 최선 | 최악 | 안정 | 제자리 |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | 예 | 예 |
| Selection | O(n²) | O(n²) | 아니오 | 예 |
| Insertion | O(n) | O(n²) | 예 | 예 |

## 언제 사용하나 / 함정

Insertion sort는 **작거나 거의 정렬된** 배열에 대해 실제로 빠르며 하이브리드 정렬 내부에서 사용됩니다. 큰 비정렬 데이터에는 세 가지 모두 피하고 대신 O(n log n) 정렬을 사용하세요.

## 왜 중요한가

이 정렬들은 고급 알고리즘을 다루기 전에 불변식, 교환, 안정성에 대한 직관을 길러 줍니다.

특히 insertion sort는 작은 부분 배열에 대해 프로덕션 정렬(예: Timsort) 내부에서 등장합니다.

이들이 왜 O(n²)인지 아는 것은 O(n log n) 정렬로의 도약을 의미 있게 만듭니다.

정렬	최선	최악	안정	제자리
Bubble	O(n)	O(n²)	예	예
Selection	O(n²)	O(n²)	아니오	예
Insertion	O(n)	O(n²)	예	예