Python의 버블 정렬(bubble sort)
이 레슨에서는 버블 정렬을 구현하고, 리스트가 정렬되면 바로 멈추는 조기 종료를 추가합니다.
소개
어떤 문제를 해결하나요
정렬은 어디에나 있고, 동작 방식을 이해하면 속도를 따져 볼 수 있습니다. 버블 정렬은 한 단계씩 따라가기 가장 쉬운 정렬 알고리즘이라, 실제 프로그램은 더 빠른 것을 쓰지만 흔히 첫 예제가 됩니다.
일상 속 비유
버블 정렬은 이웃 두 명만 바꾸며 아이들을 키순으로 세우는 것과 같습니다. 줄을 따라 걸으며 키 큰 아이가 앞에 있는 쌍을 바꿉니다. 한 번 걸으면 가장 큰 아이가 끝에 닿습니다. 거품이 수면으로 올라오듯이요. 한 번 걷는 동안 바꿀 것이 없을 때까지 반복합니다.
result[index] > result[index + 1]👫 키 큰 아이가 앞에 있나요?result[index], result[index + 1] = ...🔄 두 이웃 바꾸기for end in range(len(result) - 1, 0, -1):🚶 매번 한 명 짧게 다시 줄 걷기if not swapped: break✅ 한 번 걷는 동안 바꾼 게 없음: 정렬됨버블 정렬은 리스트를 반복해서 지나며 순서가 틀린 이웃 항목을 바꾸고, 한 번 지나는 동안 바꾼 것이 없으면 멈춥니다. 일반적으로 O(n²) 시간이 걸립니다.
핵심 포인트
result = values.copy()는 사본을 정렬하므로 호출한 쪽의 리스트는 바뀌지 않습니다.if result[index] > result[index + 1]:은 순서가 틀린 쌍을 바꿉니다.- 가장 큰 값들은 이미 끝에 있으므로
end는 지날 때마다 줄어듭니다. if not swapped: break는 바꾼 것이 없으면 일찍 멈추므로, 정렬된 입력은 한 번에 끝납니다.
언제 사용하나요?
- 비교 기반 정렬이 어떻게 동작하는지 배우기.
- 교육용 도구와 시각화의 아주 작은 리스트.
- 한 번 지나며 리스트가 이미 정렬됐는지 확인하기.
필요 없는 경우
- 모든 실제 프로그램:
sorted()와list.sort()가 훨씬 빠르고(O(n log n)) 검증되어 있습니다. - 항목이 수백 개를 넘는 리스트: 비교 횟수가 길이의 제곱으로 늘어납니다.
Python의 버블 정렬(bubble sort) 시각화
O(n²)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
def bubble_sort(values):
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8]))
실행 결과
[1, 2, 4, 5, 8]
코드 설명
한 번 훑고 나면 정렬되지 않은 부분의 가장 큰 값이 이미 제자리에 있으므로, 다음 훑기는 요소 하나만큼 짧아집니다. 변수 swapped는 그 훑기에서 교환이 있었는지를 기록합니다. 교환이 한 번도 없었다면 리스트는 이미 정렬된 것이므로 반복을 일찍 끝냅니다. 최악의 경우 복잡도가 O(n²)이라 큰 데이터에는 맞지 않습니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
인덱스 하나 더 가기
index 가 마지막 위치에 닿으면 result[index + 1] 은 끝을 넘어갑니다.
for index in range(len(result)):
if result[index] > result[index + 1]:
for index in range(end):
if result[index] > result[index + 1]:
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지