정렬
버블 정렬
옆 사람과 키 순서로 서 보기
여섯 칸을 작은 수부터 늘어놓아 보세요. 두 칸을 누르면 자리가 바뀝니다.
두 칸을 눌러 자리를 바꿉니다
바꾼 횟수 0
0번 바꿔서 맞췄습니다. 여러분은 전체를 눈으로 보고 골랐습니다.
컴퓨터는 한눈에 못 봅니다. 옆칸 둘씩만 견줄 수 있습니다. 그래서 앞에서 뒤로 훑으며 앞이 크면 바꾸기를 되풀이합니다.
한 바퀴 돌면 가장 큰 수가 맨 뒤로 밀려납니다. 이렇게 옆칸 비교만으로 정렬하는 방법 = 버블 정렬
한 바퀴에 큰 수 하나가 자리를 잡는다
- 한 바퀴 — 앞에서 뒤로 훑으며 옆칸끼리만 견준다
- 바퀴가 끝나면 — 가장 큰 수가 맨 뒤에 확정된다. 다음 바퀴는 한 칸 덜 본다
- 그래서 — 칸이 n개면 바퀴도 n−1번. 비교는 n²에 가깝다
코드는 바퀴 두 번 도는 것이 전부다
다음을 눌러 한 줄씩 넘기며 확정된 칸이 뒤에서부터 쌓이는 걸 보세요.
50
21
92
13
74
45
다음을 눌러 한 줄씩 넘겨 보세요
n = 6
bubble_sort.py
- 1def bubble_sort(arr):
- 2 n = len(arr)
- 3 for i in range(n - 1):
- 4 for j in range(n - 1 - i):
- 5 if arr[j] > arr[j + 1]:
- 6 arr[j], arr[j + 1] = arr[j + 1], arr[j]
- 7 return arr
0 / 35
i— 몇 번째 바퀴인가j— 그 바퀴에서 지금 보는 자리n - 1 - i— 뒤쪽 확정된 칸은 다시 안 본다
이미 작은 수부터 정렬된 배열을 넣으면 비교는 몇 번일까요?
버블 정렬은 실전에서 쓰지 않는다
버블 정렬 · 1000개499,500번
Python sorted · 1000개9,966번
여섯 칸짜리 예시에서는 비교 15번, 교환 8번이었습니다. 칸이 늘어나면 이 수가 제곱으로 커집니다.
그래도 버블 정렬을 배우는 이유
옆칸만 비교제자리에서 정렬n² 가 어떤 느낌인지
다음 장에서는 한 바퀴에 가장 작은 수를 골라 앞으로 보내는 선택 정렬을 봅니다.