08 — 버블 정렬

람다가 체육 시간에 키 순서로 줄 서는 친구들을 보며 "옆 친구랑 키만 비교해서 자리를 바꾸면 줄이 맞춰지지 않을까?"라고 발견하고, 돌핀쌤이 "그게 버블 정렬이에요!"라고 안내하는 도입 장면

🙋‍♀️ 람다: "선생님이 키 순서로 줄을 세우셨는데, 옆 친구하고만 키를 비교해서 큰 사람을 뒤로 보내기를 반복했더니 결국 줄이 딱 맞춰지더라고요!"

🐬 돌핀쌤: "두 친구가 오늘 배울 걸 미리 발견했네요! 옆끼리 비교해서 큰 값을 뒤로 보내는 이 방법이 바로 버블 정렬이에요. 가장 큰 값이 거품처럼 뒤로 떠오른다고 해서 붙은 이름이지요."

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 버블 정렬이에요. 숫자가 든 리스트를 작은 순서대로 줄 세우는 코드예요.

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

numbers = [64, 34, 25, 12, 22]
print(bubble_sort(numbers))

실행하면 이렇게 나와요.

[12, 22, 25, 34, 64]

뒤죽박죽이던 [64, 34, 25, 12, 22] 가 작은 순서대로 줄을 섰죠?

🐬 돌핀쌤: "10줄도 안 되는 짧은 코드지만, 이 안에 정렬의 핵심이 다 들어 있어요. 지금부터 이 코드가 왜 정렬을 해내는지 하나씩 풀어볼게요. 다 보고 나면 위 코드가 술술 읽힐 거예요."

💡 어떻게 풀까? — 옆 친구랑만 비교하기

키가 다른 학생 5명을 줄 세운다고 해봐요.

[170][155][182][163][178]

규칙은 딱 하나예요. "옆에 있는 두 명을 비교해서, 키 큰 사람을 오른쪽으로 보내기"

이걸 왼쪽부터 끝까지 반복하면, 한 바퀴 돌 때마다 가장 큰 사람이 거품처럼 맨 뒤로 떠올라요.

[170][155] 비교 → 170이 크니까 교환  →  [155][170][182][163][178]
[170][182] 비교 → 182가 크니까 그대로 →  [155][170][182][163][178]
[182][163] 비교 → 182가 크니까 교환  →  [155][170][163][182][178]
[182][178] 비교 → 182가 크니까 교환  →  [155][170][163][178][182]
                                                          ↑ 182가 맨 뒤로!

이 한 바퀴를 라운드라고 불러요. 라운드를 반복하면 큰 수부터 차례로 뒤에 쌓이면서 전체가 정렬돼요.

🙋‍♂️ 제네릭: "옆끼리만 봤는데 가장 큰 182가 맨 뒤에 딱 자리잡았네요. 신기해요!"

키 대신 숫자가 들어 있어도 똑같아요. 맨 위 코드의 [64, 34, 25, 12, 22] 도 이 규칙 그대로 정렬할 거예요.

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 라운드를 반복해요

for i in range(n - 1):       # 라운드 (n-1번 반복)

학생이 n 명이면 라운드는 n - 1 번이면 충분해요. 마지막 한 명은 자동으로 제자리니까요.

② 옆끼리 비교해요

    for j in range(n - 1 - i):   # 한 라운드 안에서 이웃 비교
        if arr[j] > arr[j + 1]:  # j번과 그 옆(j+1)번 비교

arr[j] 와 바로 옆 arr[j + 1] 을 비교해요. 앞이 더 크면 순서가 잘못된 거예요.

💡 비교 범위가 n - 1 - i 인 이유: 라운드(i)가 한 번 끝날 때마다 맨 뒤에 큰 수가 하나씩 확정돼요. 확정된 뒤쪽은 다시 볼 필요가 없으니, 라운드가 갈수록 비교 범위를 한 칸씩 줄여요. 숫자 5개(n=5)면 → 1라운드 4번, 2라운드 3번, 3라운드 2번, 4라운드 1번 비교.

③ 잘못된 순서면 자리를 바꿔요 (교환)

            arr[j], arr[j + 1] = arr[j + 1], arr[j]   # 두 자리 교환

이 한 줄이 두 값을 동시에 맞바꿔요. 파이썬은 이렇게 한 줄로 교환할 수 있어요.

교환 전: arr[j]=170, arr[j+1]=155
교환 후: arr[j]=155, arr[j+1]=170

🐬 돌핀쌤: "한쪽을 먼저 덮어쓰면 원래 값이 사라져요. 그래서 arr[j], arr[j+1] = arr[j+1], arr[j] 한 줄 교환을 습관으로 들이면 좋아요."

④ 정렬된 리스트를 돌려줘요

    return arr

라운드를 다 돌고 나면 arr 은 정렬이 끝나 있어요. 그걸 돌려줘요.

⑤ 전체가 어떻게 굴러가는지 — [64, 34, 25, 12, 22]

라운드가 끝날 때마다 맨 뒤부터 하나씩 확정돼요.

라운드1 끝: [34, 25, 12, 22, |64|]      ← 64 확정
라운드2 끝: [25, 12, 22, |34, 64|]      ← 34 확정
라운드3 끝: [12, 22, |25, 34, 64|]      ← 25 확정
라운드4 끝: [|12, 22, 25, 34, 64|]      ← 전체 완료!

🙋‍♀️ 람다: "라운드가 하나 끝날 때마다 뒤쪽 확정 구간이 한 칸씩 늘어나네요! 그래서 다음 라운드는 비교 범위를 한 칸 줄여도 되는 거군요."

✍️ 직접 완성해보기

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - ___):         # 비교 범위 (라운드마다 줄어듦)
            if arr[j] > arr[___]:            # 옆끼리 비교
                arr[j], arr[j + 1] = arr[___], arr[___]   # 교환
    return arr

numbers = [64, 34, 25, 12, 22]
print(bubble_sort(numbers))   # [12, 22, 25, 34, 64]

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

📌 오늘 배운 것

개념	설명
버블 정렬	이웃한 두 값을 비교해 큰 값을 뒤로 보내며 정렬
이웃 비교	`arr[j]` 와 `arr[j + 1]` 두 값을 비교
교환(swap)	순서가 틀리면 `arr[j], arr[j+1] = arr[j+1], arr[j]`
라운드	한 바퀴마다 맨 뒤에 큰 값이 하나씩 확정 → 비교 범위 `n - 1 - i`
시간복잡도	O(n²) — 라운드 × 이웃 비교, 이중 반복이라 데이터 많으면 느림

🐬 돌핀쌤: "이웃 비교, 교환, 라운드마다 맨 뒤 확정! 이 세 박자면 어떤 리스트가 와도 정렬할 수 있어요. 잘했어요! 👏"

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

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

정렬 방향 바꾸기 — > 를 < 로 바꾸면 큰 수부터(내림차순) 정렬돼요. → 예제로 연습
교환 횟수 세기 — swap_count 변수를 두고 교환할 때마다 +1 하면 데이터가 얼마나 섞여 있었는지 알 수 있어요. → 예제로 연습
조기 종료 최적화 — 한 라운드 동안 교환이 한 번도 없으면 이미 정렬된 거예요. break 로 바로 끝내면 이미 정렬된 경우 O(n)까지 빨라져요. → 예제로 연습
단계별 출력 — 라운드마다 리스트 상태를 print 하면 정렬 과정을 눈으로 볼 수 있어요.

🐬 돌핀쌤: "기본을 완벽히 익힌 다음 도전하세요. 변형은 전부 '이웃 비교 + 교환'이라는 같은 뼈대 위에 살을 붙인 거예요."

참고 — 왜 O(n²)일까?

리스트에 n개가 있을 때 비교 횟수를 세어 보면:

라운드 1: n-1 번  +  라운드 2: n-2 번  +  ...  +  라운드 n-1: 1 번
= n × (n-1) / 2  ≈  n² / 2

n	비교 횟수
10	약 45번
100	약 4,950번
1,000	약 499,500번

n이 10배가 되면 비교는 약 100배. 이게 O(n²) 의 모습이에요(3차시와 연결). 그래서 버블 정렬은 데이터가 많으면 잘 안 써요.

08 — 버블 정렬

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1