09 — 선택 정렬 · 삽입 정렬

람다와 제네릭이 숫자 카드를 정렬하며 "가장 작은 걸 골라 앞으로 둘까, 한 장씩 끼워 넣을까?" 두 방법을 떠올리는 도입, 돌핀쌤이 선택/삽입 정렬을 안내

🙋‍♀️ 람다: "카드 [5, 3, 1, 4, 2] 를 작은 순서로 줄 세우고 싶은데… 전체에서 가장 작은 걸 골라 맨 앞에 두기를 반복하면 되지 않을까요?"

🙋‍♂️ 제네릭: "그것도 좋고, 카드를 한 장씩 뽑아 손패의 알맞은 자리에 끼워 넣어도 되잖아!"

🐬 돌핀쌤: "두 친구가 각각 좋은 방법을 떠올렸어요! 람다 방법이 선택 정렬, 제네릭 방법이 삽입 정렬이에요. 지난 시간 버블 정렬에 이어, 오늘은 이 두 가지를 함께 배워 봐요."

🎯 오늘 완성할 코드는?

오늘 만들 건 선택 정렬과 삽입 정렬, 두 가지예요. 둘 다 숫자 리스트를 작은 순서대로 줄 세우는 코드인데, 가는 길이 서로 달라요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

# 선택 정렬 — 전체에서 가장 작은 값을 골라 맨 앞에 놓기
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i                  # 현재 구간의 최솟값 인덱스
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j           # 더 작은 값을 찾으면 갱신
        arr[i], arr[min_idx] = arr[min_idx], arr[i]   # 최솟값과 맨 앞 교환
    return arr

print(selection_sort([5, 3, 1, 4, 2]))   # [1, 2, 3, 4, 5]


# 삽입 정렬 — 카드 한 장씩 알맞은 자리에 끼워 넣기
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]                 # 삽입할 값
        j = i - 1
        while j >= 0 and arr[j] > key:   # key보다 큰 값들을 오른쪽으로 밀기
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key             # 알맞은 자리에 삽입
    return arr

print(insertion_sort([5, 3, 1, 4, 2]))   # [1, 2, 3, 4, 5]

실행하면 이렇게 나와요.

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

뒤죽박죽이던 [5, 3, 1, 4, 2] 가 두 방법 모두 작은 순서대로 줄을 섰죠?

🐬 돌핀쌤: "결과는 똑같지만 가는 방법이 달라요. 선택 정렬은 '가장 작은 걸 골라 앞으로', 삽입 정렬은 '한 장씩 알맞은 자리에 끼워 넣기'예요. 지금부터 두 코드가 왜 정렬을 해내는지 하나씩 풀어볼게요."

💡 어떻게 풀까? — 고르기 vs 끼우기

같은 카드 [5, 3, 1, 4, 2] 를 두 가지 방법으로 정렬해 볼게요.

선택 정렬 — 가장 작은 걸 골라 맨 앞에 놓기

바닥에 카드가 흩어져 있어요. 그중 가장 작은 카드를 찾아 맨 왼쪽에 놓고, 남은 카드에서 또 가장 작은 걸 찾아 그다음에 놓아요.

[5, 3, 1, 4, 2]  →  가장 작은 1을 찾아 맨 앞으로  →  [1, 3, 5, 4, 2]
남은 [3, 5, 4, 2] →  가장 작은 2를 찾아 그다음에  →  [1, 2, 5, 4, 3]
...

삽입 정렬 — 카드 한 장씩 알맞은 자리에 끼우기

카드 게임에서 패를 받을 때처럼, 카드를 한 장씩 뽑아 손에 든 정렬된 카드 사이 알맞은 자리에 끼워 넣어요.

손패 [5]      카드 3을 받음  →  3 < 5 → 앞에 끼움  →  [3, 5]
손패 [3, 5]   카드 1을 받음  →  맨 앞에 끼움       →  [1, 3, 5]
...

🙋‍♀️ 람다: "하나는 흩어진 카드에서 고르는 거고, 다른 하나는 손패에 끼워 넣는 거네요!"

맨 위 코드의 [5, 3, 1, 4, 2] 도 이 두 방법 그대로 정렬할 거예요.

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요. 먼저 선택 정렬이에요.

① 매 단계, 맨 앞 자리를 정해요

for i in range(n - 1):
    min_idx = i                  # 현재 구간의 최솟값 인덱스

i 는 "이번에 채울 자리"예요. min_idx 는 "지금까지 본 것 중 가장 작은 값의 자리"인데, 일단 i 로 시작해요.

💡 min_idx = i 를 빠뜨리면 안 돼요! 비교할 기준이 없어서 에러가 나요. 매 라운드 시작마다 꼭 i 로 초기화해요.

② 남은 구간에서 최솟값을 찾아요

    for j in range(i + 1, n):
        if arr[j] < arr[min_idx]:
            min_idx = j           # 더 작은 값을 찾으면 갱신

i + 1 부터 끝까지 훑으면서, 지금 기록된 최솟값(arr[min_idx])보다 작은 값이 나오면 min_idx 를 그 자리로 바꿔요.

③ 최솟값을 맨 앞과 교환해요

    arr[i], arr[min_idx] = arr[min_idx], arr[i]   # 최솟값과 맨 앞 교환

찾은 최솟값을 이번 자리(i)로 보내요. 선택 정렬은 한 라운드에 교환이 딱 1번이에요.

이번엔 삽입 정렬이에요.

④ 카드를 한 장 뽑아요 (key)

for i in range(1, n):
    key = arr[i]                 # 삽입할 값
    j = i - 1

첫 번째 카드는 이미 정렬된 셈 치고, 두 번째(i=1)부터 한 장씩 뽑아요. 뽑은 값을 key 에 따로 저장하고, j 는 그 바로 왼쪽 자리예요.

💡 key = arr[i] 로 미리 저장하는 게 중요해요! 아래에서 값을 오른쪽으로 밀다 보면 arr[i] 자리가 덮어써질 수 있거든요.

⑤ 큰 값들을 오른쪽으로 밀어요

    while j >= 0 and arr[j] > key:   # key보다 큰 값들을 오른쪽으로 밀기
        arr[j + 1] = arr[j]
        j -= 1

왼쪽으로 가면서 key 보다 큰 값을 만나면 그 값을 한 칸 오른쪽으로 밀어요. key 보다 작거나 같은 값을 만나거나 맨 앞(j < 0)까지 가면 멈춰요.

⑥ 빈 자리에 끼워 넣어요

    arr[j + 1] = key             # 알맞은 자리에 삽입

밀기가 멈춘 자리 바로 다음(j + 1)이 key 가 들어갈 알맞은 자리예요. 거기에 끼워 넣어요.

⑦ 전체가 어떻게 굴러가는지 — [5, 3, 1, 4, 2]

선택 정렬 — 매 라운드 앞쪽부터 하나씩 확정돼요.

라운드1: 최솟값 1 찾아 앞과 교환 →  [|1|, 3, 5, 4, 2]
라운드2: 최솟값 2 찾아 교환       →  [1, |2|, 5, 4, 3]
라운드3: 최솟값 3 찾아 교환       →  [1, 2, |3|, 4, 5]
라운드4: 최솟값 4 (이미 제자리)   →  [1, 2, 3, |4|, 5]  완료!

삽입 정렬 — 한 장씩 뽑아 정렬된 부분에 끼워요.

key=3 →  3을 [5] 앞에 끼움      →  [3, 5, 1, 4, 2]
key=1 →  1을 맨 앞에 끼움       →  [1, 3, 5, 4, 2]
key=4 →  4를 3과 5 사이에 끼움  →  [1, 3, 4, 5, 2]
key=2 →  2를 1과 3 사이에 끼움  →  [1, 2, 3, 4, 5]  완료!

🙋‍♂️ 제네릭: "선택 정렬은 앞쪽부터 확정되고, 삽입 정렬은 정렬된 구간이 점점 자라네요! 결과는 똑같이 [1, 2, 3, 4, 5] 예요."

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = ___                # 최솟값 인덱스 (i로 시작)
        for j in range(i + 1, n):
            if arr[j] < arr[___]:    # 더 작은 값이면
                min_idx = j           # 갱신
        arr[i], arr[min_idx] = arr[min_idx], arr[i]   # 최솟값과 맨 앞 교환
    return arr

print(selection_sort([5, 3, 1, 4, 2]))   # [1, 2, 3, 4, 5]


def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]                 # 삽입할 값
        j = i - 1
        while j >= 0 and arr[j] > ___:   # key보다 큰 값들을 오른쪽으로 밀기
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = ___             # 알맞은 자리에 삽입
    return arr

print(insertion_sort([5, 3, 1, 4, 2]))   # [1, 2, 3, 4, 5]

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
선택 정렬	남은 구간에서 최솟값을 골라 맨 앞과 교환 (라운드당 교환 1번)
`min_idx`	최솟값의 자리를 기억하는 변수. 매 라운드 `i` 로 초기화 필수
삽입 정렬	카드처럼 한 장씩 뽑아 알맞은 자리에 끼워 넣기
`key`	뽑은 값을 미리 저장 → 밀기 중에 값이 덮어써지는 걸 방지
시간복잡도	둘 다 O(n²). 단, 삽입 정렬은 거의 정렬된 데이터에서 O(n)으로 빨라짐

🐬 돌핀쌤: "선택은 '고르기', 삽입은 '끼우기'! 결과는 같아도 가는 길이 다르다는 걸 알면 정렬의 절반은 이해한 거예요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요.

내림차순으로 정렬하기 — 선택 정렬에서 < 를 > 로 바꿔 최댓값을 앞으로 보내면 큰 순서대로 정렬돼요. → 예제로 연습
입력받아 정렬하기 — input() 으로 받은 숫자들을 선택/삽입 정렬로 정렬해 출력해 봐요. → 예제로 연습
세 정렬 한꺼번에 비교 — 버블·선택·삽입을 같은 데이터에 모두 돌려 결과가 같은지 확인해 봐요. 방법은 달라도 결과는 같답니다.

참고 — 언제 어떤 정렬이 유리할까?

데이터 상태	선택 정렬	삽입 정렬
거의 정렬됨	O(n²)	O(n) — 매우 빠름
완전히 역순	O(n²)	O(n²)
랜덤	O(n²)	O(n²)

삽입 정렬은 데이터가 이미 거의 정렬돼 있으면 밀기가 거의 안 일어나서 빨라져요. 그래서 카드 게임처럼 하나씩 추가되는 상황에 잘 맞아요. 선택 정렬은 교환이 라운드당 1번뿐이라, 교환 비용이 클 때 유리해요.

09 — 선택 정렬 · 삽입 정렬

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1