[알고리즘] 버블 정렬(Bubble Sort)

1. 1,2번째 원소, 2,3번째 원소, 3,4번째 원소, ... , n-1,n번째 원소를 비교하면서 필요한 경우 스왑 연산을 진행한다.
2. 이 사이클(pass)을 한 번 마치고 나면 살펴본 값들 중 가장 큰 값이 n번째 인덱스에 저장된다.
3. n을 1 감소시키고 과정 1로 되돌아간다.
4. 비교할 값이 더 이상 없으면 정렬을 종료한다.

특징

버블 정렬이라는 이름은 한 사이클마다 가장 큰 원소가 거품 올라오듯 정렬이 진행된다 하여 붙은 것이다.

n, n-1, n-2, ... , 1번으로 총 $\frac{n(n - 1)}{2}$번의 비교 연산이 필요하다.
따라서 시간 복잡도는 O(N^2)이다.

사실 이러한 비효율성 때문에 버블 정렬은 실제로 잘 쓰이지 않고 교육용으로만 다루어지는 편이다.

버블 정렬은 칵테일 정렬(Shaker Sort), 콤브 정렬(Comb Sort) 등으로 파생되기도 하였다.

구현 [Python]

def bubble_sort(a: List[int]) -> None:
    for i in range(len(a) - 1, 0, -1):
        for j in range(0, i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]