보통
Bubble Sort
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 bubbleSort(nums):2 n = nums.length3 반복 회전 = 1 … n-1:4 바꿈 = 거짓 // 이번 회전에 교환이 있었나5 반복 j = 0 … n-1-회전:6 만약 nums[j] > nums[j+1]: // 이웃이 뒤집혀 있으면7 nums[j] ↔ nums[j+1] // 자리를 바꾼다8 바꿈 = 참9 만약 바꿈 = 거짓: 멈춤 // 교환이 없으면 이미 정렬됨10 반환 nums // 정렬 완료
변수
- n
- 5
1 / 12정렬할 배열을 준비합니다. 이웃한 두 값을 견주며 큰 값을 뒤로 밀어냅니다.
인접한 두 값을 반복해 비교·교환하면 큰 값이 거품처럼 뒤로 떠올라 정렬된다.
왜 헷갈리는가
교육용으로 가장 먼저 배우지만 O(n²)라 실무 정렬로는 쓰지 않는다 — '그럼 왜 배우나'가 헷갈린다. 안정 정렬·인접 교환·조기 종료 같은 정렬의 기본 개념을 눈으로 잡는 도구다.
핵심 아이디어
한 번의 패스에서 인접 쌍을 훑으며 순서가 뒤바뀐 것만 교환한다. 패스가 끝날 때마다 가장 큰 값 하나가 끝자리에 확정된다.
한 패스에서 교환이 한 번도 없었다면 이미 정렬된 것이므로 즉시 멈춘다(조기 종료).
복잡도
최악·평균 O(n²)·공간 O(1). 거의 정렬된 데이터는 조기 종료로 O(n)까지 빨라진다. 안정 정렬(같은 값의 원래 순서 보존)이다.
실무에서 어디에 쓰나
실제 정렬은 언어 내장(자바스크립트 sort=Timsort, C++ introsort)을 쓴다. 버블 정렬 자체를 쓰는 경우는 드물지만, 그 개념은 곳곳에 있다.
- n이 아주 작거나(수십 개) 거의 정렬된 데이터의 국소 보정
- '안정 정렬'이 왜 중요한지 이해 — 다중 키 정렬(먼저 이름, 그다음 날짜)
- 인접 교환 = 리스트 재정렬 애니메이션·드래그 정렬의 기본 동작
- 교육: 정렬 비용(비교/교환 횟수)을 눈으로 재는 기준선
흔한 실수
조기 종료를 빼먹어 이미 정렬된 데이터도 O(n²)로 도는 것. 실무에서 직접 구현해 쓰는 것(내장 정렬을 써야 한다).
기억할 것
- 실무 정렬은 내장 함수를 써라(버블은 O(n²)).
- 조기 종료로 거의 정렬된 데이터는 O(n).
- 안정 정렬 — 다중 키 정렬의 토대.
- 정렬 개념(비교·교환·안정성)을 눈으로 익히는 도구.