2차시 순서를 만드는 기술 — 정렬 알고리즘

🤔

생각 열기 — 1초의 순위

마라톤 결승선과 기록 시계 — 마라톤 결승선 — 수만 명의 기록이 들어오는 즉시 순위가 매겨진다. 이 '순서 만들기'가 바로 정렬이다. 출처: Wikimedia Commons

서울 마라톤에는 3만 명 넘게 참가합니다. 결승선을 통과하는 순간 기록이 찍히고, 몇 초 뒤엔 전체 순위가 나오죠. 사람이 3만 개의 기록을 손으로 줄 세운다면 며칠이 걸릴 거예요. 컴퓨터는 어떻게 순식간에 해낼까요? 그리고 더 중요한 질문 — 줄 세우는 '방법'이 여러 가지라면, 어떤 방법이 더 빠를까요? 오늘은 그 방법(알고리즘)들을 직접 눈으로 보고, 숫자로 비교합니다.

💬 함께 생각해 보기

손에 숫자 카드 5장이 있어요: 5, 2, 4, 1, 3. 여러분은 어떤 순서로 비교하고 옮겨서 정렬하나요? 자기만의 방법을 말로 설명해 보세요 — 그 설명이 바로 여러분의 '정렬 알고리즘'입니다!

1

세 가지 고전 정렬 알고리즘

같은 목표, 서로 다른 전략

정렬(sorting)은 데이터를 일정한 순서로 나열하는 일이에요. 수십 년 동안 수많은 정렬 알고리즘이 발명되었는데, 오늘은 원리가 가장 잘 보이는 세 가지를 배웁니다.

🫧

버블 정렬

이웃끼리 비교해서 순서가 틀렸으면 교환. 끝까지 반복하면 가장 큰 값이 거품처럼 맨 뒤로 떠올라요. 이를 계속 반복!

🏆

선택 정렬

남은 것 중 가장 작은 값을 '선택'해 맨 앞과 교환. 1등 뽑아 앞으로, 남은 것 중 또 1등 뽑아 그다음으로…

🃏

삽입 정렬

새 카드를 이미 정렬된 손패의 알맞은 자리에 끼워 넣기. 카드 게임에서 패를 정리하는 바로 그 방법!

🎬 정렬 시각화 극장 INTERACTIVE

알고리즘을 고르고 ▶ 를 누르세요. 노란 막대 = 지금 비교 중, 빨강 = 교환!, 초록 = 정렬 완료 구역. 비교·교환 횟수가 알고리즘마다 어떻게 다른지 주목!

속도

0

비교 횟수

0

교환·이동 횟수

대기

상태

[안내]같은 데이터를 세 알고리즘으로 각각 정렬해 보고 비교·교환 횟수를 기록해 보세요. (섞기를 누르기 전까지 데이터는 유지됩니다)

🃏 활동 1 — 언플러그드: 손으로 하는 정렬

모둠별로 트럼프 카드(또는 숫자 쪽지) 8장을 섞어 책상에 한 줄로 놓고:

한 명이 '컴퓨터' 역할 — 버블 정렬 규칙만 따라 정렬한다. (옆 카드 두 장씩만 비교·교환 가능!) 옆 사람은 비교 횟수를 센다.
다시 섞고, 이번엔 선택 정렬 규칙으로. 비교 횟수를 또 센다.
마지막으로 삽입 정렬 규칙으로 — 어느 방법이 가장 편했는지, 횟수는 어땠는지 모둠 의견을 나눈다.

💡 규칙을 어기고 싶어질 때마다 기억하세요 — 컴퓨터는 절대 어기지 못합니다. 그래서 규칙(알고리즘) 자체가 좋아야 해요!

2

효율을 숫자로 — 비교 횟수 분석

n이 커지면 차이는 재앙이 된다

시각화 극장에서 봤듯이 세 알고리즘 모두 데이터가 n개면 대략 n × n에 비례하는 횟수의 비교를 해요. n개 각각에 대해 나머지 전부와 비교하는 구조이기 때문이죠. "그게 뭐 어때서?"라고요? n을 키워 보면 생각이 달라집니다.

📈 n² 체감 계산기 — 데이터 개수: 100개

알고리즘	비교 횟수 (대략)	특징
버블 정렬	최대 n(n−1)/2 회 + 교환도 많음	원리가 가장 단순. 거의 정렬된 데이터라면 일찍 끝낼 수 있음
선택 정렬	항상 n(n−1)/2 회	비교는 많지만 교환은 최대 n−1회로 가장 적음
삽입 정렬	평균 약 n(n−1)/4 회	거의 정렬된 데이터에 매우 강함 — 실전에서 작은 데이터에 애용

🏁 알고리즘 레이스 — 같은 데이터, 같은 속도, 다른 알고리즘 INTERACTIVE

무작위 데이터 120개를 세 알고리즘이 초당 같은 작업 횟수로 동시에 정렬합니다. 작업(비교+이동)이 적은 알고리즘이 먼저 끝나겠죠? 예상 1등을 마음속으로 정하고 출발!

🫧 버블 정렬

🏆 선택 정렬

🃏 삽입 정렬

[중계]출발 준비 완료!

💡 레이스가 말해 주는 것

① 같은 문제도 알고리즘에 따라 작업량이 다르다 — 그래서 '비교·분석'이 필요해요. ② 세 알고리즘 모두 n²급이라 데이터가 10배면 작업은 약 100배 — 빅데이터 시대에는 더 빠른 정렬(병합·퀵 정렬, 더 알아보기!)이 필수가 됩니다. ③ 그렇다고 단순한 알고리즘이 쓸모없는 건 아니에요 — 데이터가 작거나 거의 정렬돼 있다면 삽입 정렬이 오히려 실속 챔피언!

✅

확인 문제

바로바로 채점! 해설까지 꼭 읽어 보세요.

📝

2차시 확인 문제

4문항 · 즉시 채점

1이웃한 두 데이터를 비교하여 순서가 잘못되었으면 교환하는 과정을 반복하는 정렬은?

2[5, 2, 4, 1, 3]을 선택 정렬로 정렬할 때, 첫 번째 교환 직후의 상태는?

3카드 게임에서 새로 받은 카드를 이미 정리된 손패의 알맞은 위치에 끼워 넣는 방식과 같은 정렬은?

4n²에 비례하는 정렬 알고리즘이 1,000개를 1초에 정렬했다. 10,000개를 정렬하면 대략 얼마나 걸릴까?

🚀

더 알아보기

교육과정 너머, 궁금한 만큼 깊이!

코딩버블 정렬을 진짜 파이썬으로 — 브라우저에서 바로 실행!

시각화 극장의 버블 정렬을 코드로 옮기면 이렇습니다. ▶ 실행을 눌러 보고, 숫자를 바꾸거나 비교 횟수를 세는 코드를 추가해 보세요. (최초 실행 시 파이썬 엔진을 내려받느라 몇 초 걸려요)

data = [5, 2, 4, 1, 3]
compare = 0          # 비교 횟수 세기

for i in range(len(data) - 1):
    swapped = False                        # 이번 바퀴에 교환이 있었나?
    for j in range(len(data) - 1 - i):
        compare += 1
        if data[j] > data[j + 1]:          # 이웃 비교
            data[j], data[j + 1] = data[j + 1], data[j]  # 교환!
            swapped = True
    print(i + 1, "바퀴 후:", data)
    if not swapped:                        # 교환이 없었다면 이미 정렬됨!
        break

print("정렬 완료:", data)
print("비교 횟수:", compare)

💪 도전: ① data를 [1,2,3,4,5](이미 정렬됨)로 바꾸면 비교 횟수는? (swapped 덕분에 4회로 끝 — 시각화 극장의 조기 종료와 같아요!) ② 10개짜리 리스트로 늘리면? — n²의 성장을 직접 측정해 보세요!

실측⏱️ 진짜 대규모 데이터로 재 보기 — 버블 정렬 vs 파이썬 내장 정렬

계산기로 본 숫자, 진짜일까요? 무작위 데이터 3,000개를 버블 정렬과 파이썬 내장 sorted()(팀소트, 아래 더 알아보기 참고)로 각각 정렬하며 실제 시간을 측정해 봅시다.

import random, time

n = 3000
data = [random.randint(1, 100000) for _ in range(n)]

# ① 버블 정렬로 측정
arr = data[:]                       # 복사본
start = time.perf_counter()
for i in range(len(arr) - 1):
    for j in range(len(arr) - 1 - i):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
bubble_time = time.perf_counter() - start

# ② 내장 정렬(팀소트)로 측정
arr2 = data[:]
start = time.perf_counter()
arr2 = sorted(arr2)
fast_time = time.perf_counter() - start

print("데이터", n, "개 기준")
print("버블 정렬 :", round(bubble_time, 3), "초")
print("내장 정렬 :", round(fast_time, 5), "초")
print("차이      : 약", round(bubble_time / fast_time), "배!")

💪 도전: n을 1000 → 3000 → 6000으로 바꿔 가며 버블 정렬 시간이 어떻게 늘어나는지 기록해 보세요. n이 2배일 때 시간이 약 몇 배가 되나요? (예상: n²이니까 약 4배!) — 이것이 교과서 표의 숫자를 내 손으로 검증하는 방법입니다.

심화알고리즘의 성적표 — 빅오(Big-O) 표기법

컴퓨터 과학자들은 알고리즘의 효율을 빅오 표기법으로 적어요. 데이터가 n개일 때 작업량이 어떤 '급'으로 늘어나는지만 표시하는 방법이죠.

O(n) — n에 비례. 데이터 10배 → 작업 10배 (한 줄로 세워 둔 출석부 읽기)
O(n²) — n의 제곱에 비례. 데이터 10배 → 작업 100배 (오늘 배운 세 정렬!)
O(n log n) — n²보다 훨씬 완만. 병합·퀵 정렬이 여기 속해요.
O(log n) — 데이터가 2배가 되어도 작업은 +1회! (다음 차시의 이진 탐색 — 예고편)

데이터 개수 n 1,000개

n=100만일 때 n²은 1조 번이지만 n log n은 약 2,000만 번 — 5만 배 차이입니다. 알고리즘 공부가 곧 속도라는 것, 숫자가 증명하죠?

심화n²의 벽을 넘는 법 — 병합 정렬과 퀵 정렬

1차시의 분할 정복을 기억하나요? 병합 정렬은 그 전략 그대로예요 — 리스트를 반으로 나누고, 또 나누고… 1개짜리가 되면(이미 정렬!) 둘씩 병합하며 올라옵니다. 병합은 정렬된 두 묶음을 지퍼처럼 한 번씩만 보며 합치면 되니 빨라요. 전체 작업은 O(n log n)!

8개 데이터의 병합 정렬 — 절반씩 쪼개기 3단계(log₂8 = 3), 1개짜리는 이미 정렬, 다시 둘씩 병합 3단계. 한 단계의 작업량은 n이고 단계는 약 log₂n개 — 그래서 전체가 n log n!

퀵 정렬은 기준값(피벗)을 하나 골라 "작은 것은 왼쪽, 큰 것은 오른쪽"으로 가른 뒤 양쪽을 각각 또 가르는 방식이에요. 평균적으로 가장 빠른 축에 속해 이름부터 Quick! 1차시에서 배운 '문제 분해'가 속도의 비밀 병기였던 셈이죠.

실전파이썬의 sort()는 무슨 정렬일까 — 팀소트 이야기

파이썬에서 data.sort() 한 줄이면 정렬 끝 — 그 안에서는 팀소트(Timsort)라는 하이브리드 알고리즘이 돌아갑니다. 2002년 팀 피터스가 파이썬을 위해 만든 이 알고리즘은 병합 정렬 + 삽입 정렬의 합작품이에요. 현실의 데이터는 부분부분 이미 정렬된 경우가 많다는 점을 이용해, 정렬된 구간(run)을 찾아 삽입 정렬로 다듬고 병합 정렬로 합칩니다.

현실 데이터 속에는 '이미 오름차순인 구간'이 숨어 있어요 — 찾아 볼까요?

오늘 배운 '단순한' 알고리즘이 세계 최고 수준의 실전 알고리즘 속에서 여전히 일하고 있는 거예요. 자바, 안드로이드도 팀소트를 씁니다. 기본기는 배신하지 않는다!

📌

한눈에 정리

버블: 이웃 비교·교환 / 선택: 최솟값 선택·교환(교환 최소) / 삽입: 알맞은 자리에 끼우기(거의 정렬된 데이터에 강함)
효율은 비교·교환 횟수로 분석한다 — 같은 결과라도 작업량이 다르다
세 알고리즘 모두 약 n²급: 데이터 10배 → 작업 약 100배
대규모 데이터에는 분할 정복 기반의 더 빠른 정렬(병합·퀵, n log n)이 쓰인다
정렬은 다음 차시 이진 탐색의 전제 조건 — 순서가 있어야 빨리 찾는다!

순서를 만드는 기술정렬 알고리즘