파이썬으로 배우는 버블 정렬(Bubble Sort) 구현 방법

이 글에서는 대표적인 정렬 알고리즘 중 하나인 버블 정렬(Bubble Sort)을 파이썬으로 구현하는 방법을 알아봅니다. 버블 정렬은 인접한 두 요소를 반복적으로 비교하고 교환하며 배열을 정렬하는 가장 기본적인 알고리즘으로, 정렬 학습의 첫걸음에 적합합니다.

버블 정렬의 동작 원리

버블 정렬은 다음과 같은 과정으로 동작합니다.

배열의 첫 번째 요소(인덱스 0)부터 시작하여 현재 요소와 바로 다음 요소를 비교합니다.
현재 요소가 다음 요소보다 크면 두 요소의 위치를 서로 교환(swap)합니다.
현재 요소가 다음 요소보다 작거나 같으면 그대로 두고 다음 요소로 이동합니다.

이 과정을 배열의 끝까지 반복하면 가장 큰 값이 맨 뒤로 이동하며, 이를 배열의 길이만큼 반복하면 전체 배열이 오름차순으로 정렬됩니다.

알고리즘 진행 과정

첫 번째 패스(pass)에서는 인접한 요소들을 차례로 비교·교환하여 최댓값을 배열의 마지막 위치로 보냅니다.
두 번째 패스에서는 나머지 요소들에 대해 같은 작업을 수행하여 두 번째로 큰 값을 뒤에서 두 번째 위치로 보냅니다.
이 과정을 배열이 완전히 정렬될 때까지 반복합니다.

파이썬 구현 예제

아래는 문자열 배열을 버블 정렬로 정렬하는 파이썬 코드입니다.

def bubbleSort(ar):
    n = len(ar)
    # 배열의 모든 요소를 순회합니다
    for i in range(n):
        # 마지막 i개의 요소는 이미 제자리에 정렬되어 있습니다
        for j in range(0, n-i-1):
            # 현재 요소가 다음 요소보다 크면 서로 교환합니다
            if ar[j] > ar[j+1]:
                ar[j], ar[j+1] = ar[j+1], ar[j]

# 위 알고리즘을 테스트하기 위한 드라이버 코드
ar = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']
bubbleSort(ar)
print("Sorted array is:")
for i in range(len(ar)):
    print(ar[i])

실행 결과

Sorted array is:
a
i
l
o
r
t
t
u

'tutorial'이라는 문자열이 알파벳 순서대로 'a, i, l, o, r, t, t, u'로 정렬된 것을 확인할 수 있습니다.

시간 복잡도

최선의 경우(이미 정렬된 배열): O(n)
평균 및 최악의 경우: O(n²)
공간 복잡도: O(1) — 제자리(in-place) 정렬 방식

버블 정렬은 구현이 간단하지만 데이터 양이 많을 경우 성능이 떨어지므로, 주로 학습용이나 소규모 데이터 정렬에 적합합니다.

마무리

이번 글에서는 파이썬 3.x 환경에서 버블 정렬을 구현하는 방법과 동작 원리, 시간 복잡도까지 살펴보았습니다. 버블 정렬의 개념을 확실히 익히면 선택 정렬, 삽입 정렬 등 다른 정렬 알고리즘을 이해하는 데 큰 도움이 됩니다.