Python 알고리즘

Python의 버블 정렬(bubble sort)

이 레슨에서는 버블 정렬을 구현하고, 리스트가 정렬되면 바로 멈추는 조기 종료를 추가합니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

정렬은 어디에나 있고, 동작 방식을 이해하면 속도를 따져 볼 수 있습니다. 버블 정렬은 한 단계씩 따라가기 가장 쉬운 정렬 알고리즘이라, 실제 프로그램은 더 빠른 것을 쓰지만 흔히 첫 예제가 됩니다.

일상 속 비유

버블 정렬은 이웃 두 명만 바꾸며 아이들을 키순으로 세우는 것과 같습니다. 줄을 따라 걸으며 키 큰 아이가 앞에 있는 쌍을 바꿉니다. 한 번 걸으면 가장 큰 아이가 끝에 닿습니다. 거품이 수면으로 올라오듯이요. 한 번 걷는 동안 바꿀 것이 없을 때까지 반복합니다.

아이들 줄 세우기에서 코드로
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²) 시간이 걸립니다.

핵심 포인트

  1. result = values.copy() 는 사본을 정렬하므로 호출한 쪽의 리스트는 바뀌지 않습니다.
  2. if result[index] > result[index + 1]: 은 순서가 틀린 쌍을 바꿉니다.
  3. 가장 큰 값들은 이미 끝에 있으므로 end 는 지날 때마다 줄어듭니다.
  4. if not swapped: break 는 바꾼 것이 없으면 일찍 멈추므로, 정렬된 입력은 한 번에 끝납니다.

언제 사용하나요?

  • 비교 기반 정렬이 어떻게 동작하는지 배우기.
  • 교육용 도구와 시각화의 아주 작은 리스트.
  • 한 번 지나며 리스트가 이미 정렬됐는지 확인하기.

필요 없는 경우

  • 모든 실제 프로그램: sorted() 와 list.sort() 가 훨씬 빠르고(O(n log n)) 검증되어 있습니다.
  • 항목이 수백 개를 넘는 리스트: 비교 횟수가 길이의 제곱으로 늘어납니다.

Python의 버블 정렬(bubble sort) 시각화

O(n²)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

예제 코드

코드 실행 →
main.py
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 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

인덱스 하나 더 가기

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 리뷰를 받을 수 있습니다.

모든 챌린지