2. 버블·선택·삽입 정렬

🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)

정렬 = 인벤토리 정렬에 씁니다. "이름순", "가격순", "획득 순"처럼 아이템 목록을 한 줄로 재배치할 때 버블·선택·삽입 같은 비교 정렬이 쓰여요. 시험에는 "한 단계 지나면 배열이 어떻게 되나?"가 자주 나옵니다.

버블 정렬(Bubble Sort, 버블 소트)

맨 앞부터 바로 옆 숫자랑 비교해서, 순서가 잘못됐으면 자리를 바꿔요. 한 번 쭉 지나가면 가장 큰 수가 맨 뒤로 가요. 게임 인벤토리를 이름순·가격순으로 정렬할 때 같은 생각이에요. 시험에 자주 나와요.

버블 정렬: 인접 쌍 비교 후 스왑. 한 패스마다 최댓값이 오른쪽으로.

📌 이론(알고리즘 단계) ↔ 파이썬 표현

버블 정렬 인접 비교(큰가?) → arr[j] > arr[j+1] | 스왑(자리 바꾸기) → arr[j], arr[j+1] = arr[j+1], arr[j]

대응 버블 정렬은 "리스트(배열)"를 한 칸씩 보면서, 인접한 두 값 비교와 자리 바꾸기(스왑)만 반복해요.

리스트[j], 리스트[j+1]: j번째 칸과 그 바로 옆(j+1) 칸의 값이에요. 버블 정렬은 "옆과 비교"하므로 이 두 인덱스가 핵심입니다.
비교 연산자 > (크다): arr[j] > arr[j+1]이면 "왼쪽이 더 크다" → 오름차순이면 자리를 바꿔야 해요. 반대로 정렬하려면 <를 씁니다.
a, b = b, a (스왑): 파이썬에서는 한 줄로 두 변수의 값을 맞바꿀 수 있어요. arr[j], arr[j+1] = arr[j+1], arr[j]로 두 칸의 값을 서로 바꿉니다. 임시 변수 없이 구현할 수 있어요.

왜 이렇게 구현하나요? 버블 정렬의 정의가 "인접한 두 원소를 비교해서 순서가 잘못됐으면 교환"이에요. 그래서 리스트 인덱싱, 비교 연산자, 스왑 문법만 알면 코드로 옮길 수 있습니다.

📌 파이썬 들여쓰기·루프 기초

들여쓰기(indent) 파이썬에서는 칸 띄우기(스페이스 또는 탭)가 "이 줄이 어느 블록에 속하는지"를 정해요. for·if 다음에 오는 줄은 반드시 한 단계 들여쓰기해요. 들여쓰기가 같으면 같은 블록이에요.

for 루프 for 변수 in range(시작, 끝)은 "시작부터 끝 직전까지" 변수를 0, 1, 2, … 로 바꿔 가며 반복해요. for j in range(0, n - 1 - i)면 j는 0, 1, …, n-2-i까지 돼요. range(n)은 0부터 n 직전까지예요.

중첩 루프 바깥 for i in range(n): 안에 for j in range(...):가 들어 있으면, i가 한 번 바뀔 때마다 j 루프가 전부 도는 구조예요. 버블 정렬은 "바깥: 패스 횟수, 안: 인접 비교"로 두 겹 루프를 씁니다.

① 비교 연산자: arr[j]가 arr[j+1]보다 클 때 바꿈 → > ② 스왑: 두 값 맞바꾸기 → arr[j+1], arr[j]

if arr[j] _____ arr[j + 1]: → arr[j], arr[j + 1] = _____

첫 빈칸: 두 번째:

🐍 파이썬 (바로 실행)

🟨 자바스크립트로 확인

var arr = [64, 34, 25, 12, 22];
console.log('정렬 전:', arr);
var n = arr.length;
for (var i = 0; i < n; i++) {
  for (var j = 0; j < n - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) {
      var t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t;
    }
  }
}
console.log('정렬 후:', arr);

선택 정렬(Selection Sort, 셀렉션 소트)

아직 정렬 안 된 구간에서 가장 작은 수를 찾아서, 그 구간의 맨 앞 자리와 바꿔요. 그 다음은 두 번째 칸부터 같은 일을 반복해요.

문제 및 해설

📋 기출 유형

[5, 2, 8, 1, 9]를 선택 정렬로 오름차순 할 때, 첫 번째 단계 후 배열은?

정답: [1, 2, 8, 5, 9]

풀이 단계

선택 정렬의 "첫 번째 단계"는 아직 정렬 안 된 구간 전체(맨 앞~맨 뒤)에서 가장 작은 값을 찾는 것입니다.
최솟값은 1(인덱스 3)이에요. 이 1을 그 구간의 맨 앞 자리(인덱스 0)에 있는 5와 자리 바꿉니다.
바꾼 결과: 맨 앞이 1이 되고, 원래 1이 있던 자리에는 5가 들어갑니다. → [1, 2, 8, 5, 9].

한 줄 요약 선택 정렬 첫 단계 = "전체에서 최솟값 찾아서 맨 앞과 교환". 더 많은 예제 →

문제 및 답 확인

[3, 7, 1]을 버블 정렬로 한 번 쭉 지나간 후 배열은?

답 보기

정답: [3, 1, 7]

풀이 버블 정렬은 맨 앞부터 "바로 옆과 비교해서 크면 자리 바꾸기"를 끝까지 한 번 도는 게 1패스예요. (3,7) 비교 → 3<7이므로 그대로. (7,1) 비교 → 7>1이므로 바꿈 → [3, 1, 7]. 이렇게 한 번 지나가면 그 패스에서 가장 큰 값(7)이 맨 뒤로 갑니다.

한 줄 요약 옆과 비교해서 큰 걸 뒤로 보내므로, 한 번 지나가면 가장 큰 수가 맨 뒤로 이동해요.

도전과제

풀어 본 뒤 정답을 펼쳐 확인하세요.

도전 1. [5, 2, 8, 1]을 버블 정렬로 한 패스(맨 앞부터 옆과 비교·스왑 한 바퀴) 지난 후 배열은?

정답 보기

정답: [2, 5, 1, 8]

(5,2) 비교 → 스왑 [2,5,8,1]. (5,8) 유지. (8,1) 비교 → 스왑 [2,5,1,8]. 한 패스 후 최댓값 8이 맨 뒤로 갔어요. 인벤토리 정렬에서 "한 번 정렬 버튼 누른 효과"와 같은 한 단계예요.

도전 2. 선택 정렬의 "한 단계"는 무엇을 하나요? 버블 정렬과 어떻게 다르나요? (한 줄씩)

정답 보기

선택 정렬 한 단계: 아직 정렬 안 된 구간에서 "가장 작은 값"을 찾아서 그 구간의 맨 앞 자리와 교환.

버블와 차이: 버블은 "옆과 비교해서 큰 걸 뒤로 밀어냄". 선택은 "전체 중 최솟값을 골라서 한 자리에 놓음".

삽입 정렬(Insertion Sort, 인서션 소트)

앞부분을 "이미 정렬된 줄"이라고 생각하고, 그 다음 숫자를 알맞은 자리에 끼워 넣는 방식이에요. 카드 놀이할 때 손에 든 카드를 순서대로 끼워 넣는 것과 비슷해요.

😄 조크 디버깅 = n번째 버그를 잡으면 (n+1)번째 버그가 보이는 과정의 반복. 더 보기 →

🔄 유사 알고리즘 비교: 버블·선택·삽입 정렬

세 가지 모두 비교 정렬이지만, "한 단계에서 무엇을 하느냐"가 달라요. 아래 표로 차이를 비교해 보세요.

구분	버블 정렬	선택 정렬	삽입 정렬
한 단계(1패스)에서 하는 일	맨 앞부터 옆과 비교해서 크면 스왑. 한 바퀴 돌면 가장 큰 값이 맨 뒤로.	아직 정렬 안 된 구간에서 최솟값을 찾아서 그 구간의 맨 앞과 교환.	다음 숫자 하나를 골라 이미 정렬된 앞부분 안에서 알맞은 자리에 끼워 넣기.
비교 대상	인접한 두 칸 (j와 j+1)	구간 전체에서 최솟값 탐색	앞의 정렬된 구간과 비교하며 자리 찾기
교환(스왑) 횟수	한 패스에 여러 번 (인접 쌍마다 필요 시)	한 단계당 1번 (최솟값과 맨 앞만)	끼워 넣을 때까지 앞쪽 원소들을 한 칸씩 밀어냄 (이동 많음)
공통점	모두 배열(리스트)을 사용하고, 비교 연산과 자리 바꾸기/이동으로 오름차순(또는 내림차순)을 만듦. 시험에 "한 단계 후 배열 상태"가 자주 나옴.

위 실습은 이 강의(버블·선택·삽입 정렬)에서 배운 인접 비교·스왑(비교 연산자 >, a,b=b,a)을 쓰는 예제입니다. 손으로 해보려면 실습: 정렬 (손으로 하기).