[정글 베이직 8] 버블 정렬

 

크래프톤 정글  ·  베이직 8

버블 정렬로
정렬 알고리즘을
이해한다는 것

BEFORE   일반 버블

for i in range(n-1):
  for j in range(n-i-1):
    if arr[j] > arr[j+1]:
      swap
# 항상 n-1 패스 수행

→

AFTER   최적화 버블

swapped = False
  ...
  swapped = True
if not swapped:
    break
# 이미 정렬됐으면 즉시 종료

cedis  ·  2026.3.8

이번 주제는 버블 정렬(Bubble Sort)이다.

정렬 알고리즘 중 가장 직관적인 방식 — 옆에 있는 두 숫자를 비교해서 큰 쪽을 뒤로 보내는 걸 반복하면 어느새 정렬이 완성된다.
기본 버전과 조기 종료 최적화 버전, 두 가지를 직접 구현하면서 왜 이 차이가 생기는지까지 짚어보자.

문제 소개

정렬되지 않은 정수 배열을 오름차순으로 정렬하는 것. 단, 직접 정렬 알고리즘을 구현해야 한다.

항목	내용
입력	[64, 34, 25, 12, 22, 11, 90]
출력	[11, 12, 22, 25, 34, 64, 90]
핵심 도구	이중 반복문, swap, break

📌

이번 챕터의 핵심 키워드: 버블 정렬, swap, swapped 플래그, 최악/최선 시간복잡도 차이

버블 정렬이란

배열을 처음부터 끝까지 한 번 훑으면서 인접한 두 원소를 비교한다.
왼쪽이 더 크면 두 원소를 교환(swap)한다. 한 번 순회가 끝나면 가장 큰 값이 맨 뒤로 이동해 있다.
이걸 배열이 정렬될 때까지 반복한다.

💡

이름이 버블인 이유: 큰 숫자가 거품(bubble)처럼 뒤로 떠오르는 모습과 닮았다.

1패스 시뮬레이션 — [5, 3, 8, 4]

1패스 진행 (i = 0) O(n) 비교

초기 → 5 3 8 4

5 > 3 → 교환 → 3 5 8 4

5 < 8 → 유지 → 3 5 8 4

8 > 4 → 교환 → 3 5 4 8

1패스 완료 — 가장 큰 값 8이 맨 뒤로 이동

이 과정을 반복하면 2패스 후 두 번째 큰 값이, 3패스 후 세 번째 큰 값이 자리를 잡는다.
그래서 외부 반복문은 n-1번이면 충분하다 — 마지막 한 자리는 자동으로 정렬되어 있기 때문이다.

구현 1 — 기본 버블 정렬

 

python

def bubble_sort(arr): n = len(arr) for i in range(n - 1): # 외부: n-1 패스 for j in range(n - i - 1): # 내부: 정렬된 뒷부분 제외 if arr[j] > arr[j + 1]: arr[j], arr[j+1] = arr[j+1], arr[j] # 파이썬 swap return arr

핵심 포인트 3가지

• 1range(n-1) — 마지막 패스는 이미 정렬된 상태이므로 n-1번이면 충분
• 2range(n-i-1) — i패스 이후 뒤쪽 i개는 이미 정렬 완료. 비교 범위를 줄임
• 3a, b = b, a — 파이썬은 임시 변수 없이 한 줄로 swap 가능

💡

파이썬 swap 문법
다른 언어: tmp = a; a = b; b = tmp (3줄)
파이썬: a, b = b, a (1줄) — 오른쪽을 먼저 평가하고 동시에 대입

전체 실행 추적 — [64, 34, 25, 12]

# 1패스 (i=0) — 범위: j = 0 ~ 2 64 > 34 → 교환 → [34, 64, 25, 12] 64 > 25 → 교환 → [34, 25, 64, 12] 64 > 12 → 교환 → [34, 25, 12, 64] ← 최댓값 고정 # 2패스 (i=1) — 범위: j = 0 ~ 1 34 > 25 → 교환 → [25, 34, 12, 64] 34 > 12 → 교환 → [25, 12, 34, 64] # 3패스 (i=2) — 범위: j = 0 25 > 12 → 교환 → [12, 25, 34, 64] 결과: [12, 25, 34, 64] ✓

⚠️

시간복잡도: O(n²)
이유: 외부(n-1) × 내부(n-i-1) = 약 n²/2번 비교. 빅오에서 상수는 무시하므로 O(n²).
n = 1,000이면 약 50만 번. n = 100,000이면 약 50억 번 — 느리다.

구현 2 — 최적화 버블 정렬 (조기 종료)

기본 버블 정렬의 문제: 이미 정렬된 배열 [1,2,3,4,5]도 n-1번 패스를 모두 수행한다.
swapped 플래그를 추가하면, 교환이 한 번도 없었던 패스 → 이미 정렬 완료 → break로 즉시 종료할 수 있다.

 

python

def bubble_sort_optimized(arr): n = len(arr) for i in range(n): swapped = False # 이 패스에서 교환 발생 여부 for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True # 교환 발생 → 플래그 ON if not swapped: # 교환 없음 = 이미 정렬됨 break return arr

swapped 플래그 동작 원리

# 입력: [1, 2, 3, 4, 5] (이미 정렬됨) 패스 1 (i=0): swapped = False 1 < 2 → 교환 없음 2 < 3 → 교환 없음 3 < 4 → 교환 없음 4 < 5 → 교환 없음 패스 끝 → swapped 여전히 False → if not swapped: break → 즉시 종료! 결과: 1패스만에 완료 → 시간복잡도 O(n)

🐌 일반 버블 정렬

[1,2,3,4,5] 입력 시
n-1 = 4패스 모두 수행
시간 O(n²)

⚡ 최적화 버블 정렬

[1,2,3,4,5] 입력 시
swap 없음 감지 → 1패스에 종료
최선 O(n)

⚠️

if not swapped:는 swapped가 False일 때 True다.
즉, "한 번도 교환이 일어나지 않았을 때" 실행 → break → 루프 탈출.

실행 결과

 

python

if __name__ == "__main__": arr1 = [64, 34, 25, 12, 22, 11, 90]

print(f"정렬 후: {bubble_sort(arr1.copy())}") arr2 = [1, 2, 3, 4, 5]

print(f"최적화 (이미 정렬): {bubble_sort_optimized(arr2.copy())}")

arr3 = [5, 4, 3, 2, 1] print(f"역순 정렬: {bubble_sort(arr3.copy())}")

 

output

정렬 후: [11, 12, 22, 25, 34, 64, 90]

최적화 (이미 정렬): [1, 2, 3, 4, 5]

역순 정렬: [1, 2, 3, 4, 5]

복잡도 정리

버전	시간 — 최악	시간 — 최선	공간	특징
기본 버블	O(n²)	O(n²)	O(1)	항상 n-1 패스 수행
최적화 버블	O(n²)	O(n)	O(1)	이미 정렬됐으면 조기 종료

📌

공간복잡도 O(1)인 이유
버블 정렬은 배열 안에서 원소를 교환(in-place)하기 때문에 추가 배열이나 자료구조가 필요 없다.
사용하는 추가 변수는 i, j, swapped 정도 — 입력 크기와 무관하므로 O(1).

---

파이썬 문법 핵심 정리

이번 문제에서 새로 나온 문법들.

a, b = b, a

임시 변수 없이 두 값 교환 (파이썬 swap)

swapped = False

Boolean 플래그 초기화 — 이벤트 발생 여부 추적

swapped = True

교환이 일어났을 때 플래그 ON

if not swapped:

swapped가 False면 조건 실행 (not은 Boolean 반전)

break

반복문 즉시 탈출 — 이후 반복 건너뜀

arr.copy()

리스트 얕은 복사 — 원본 훼손 없이 테스트

#Python #알고리즘 #정렬 #버블정렬 #크래프톤정글 #베이직8