버블 정렬 (Bubble Sort)

1. Introduction

버블 정렬은 인접한 두 원소를 비교해가며 정렬하는 정렬 알고리즘이다. 구현이 매우 간단한 것으로 코딩을 처음 배우는 사람들이 주로 쓰는 알고리즘이지만, 성능이 매우 구리다. 같은 $O(n^2)$ 알고리즘 중에서도 독보적으로 느리다!

2. Approach

다음 이미지는 버블 정렬의 과정을 시각화 한 것이다. 출처는 위키피디아. 인접한 두 원소를 비교하는 과정을 정렬이 끝날 때까지 반복한다. 

Example of Bubble Sort

다행이도, 이 과정은 간단한 계산으로 $n(n-1) \over 2$안에 끝나는 것을 알 수 있다.

다음 코드는 파이썬에서 구현한 버블 정렬이다.

def bubble(arr, a, b):
    for i in range(a, b):
        for j in range(a, b-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                

3. Discussion

Stable하며 in-place한 알고리즘에 속한다.

학계에서는 버블 정렬이란 것을 책에서 빼야된다고 하는 수준이다. 필자도 지금에 와서는 가장 쉽게 떠오르는 방법은 선택정렬이고 버블 정렬을 굳이 짜려고 하니 머리속에서 잘 안돌아갔다.