버블 정렬 (Bubble Sort)

버블정렬은 정렬 중에서 가장 기본적이고 쉬운 알고리듬이다. 버블정렬은 배열의 앞에서부터 큰 원소를 뒤쪽으로 보내는 작업을 반복적으로 시행하여 배열 전체를 정렬한다. 이 때 큰 값들이 물속에서 거품이 떠오르는 것처럼 움직이기 때문에 ‘버블’이라는 이름이 붙었다.

간단한 예를 통해서 버블 정렬이 어떻게 작동하는지 살펴보자. 아래와 같은 배열이 있다고 가정하자.

[45][53][26][93][62][20][33][17]

첫번째 위치에서 다음 위치의 값과 비교를 하면, 오른쪽의 값이 크다. 그렇다면 다음 위치로 넘어간다. 두 번째 위치 (53)에서 다음 위치의 값과 비교하면 오른쪽의 값이 작다. 이 때에는 26과 53의 값을 바꾼다.

[45][26][53][93][62][20][33][17]
    ^^^^^^^^

같은 방식으로 기준 위치를 옮겨가면서 오른쪽의 숫자가 더 작다면 자리를 바꾼다. 이 과정을 배열의 끝까지 반복한다면 가장 큰 값이 맨 뒤로 가게 된다.

[45][26][53][62][20][33][17][93]

다시 처음부터 이 과정을 반복한다. 두번째로 큰 62가 93의 앞까지 밀려나게 된다.

[26][45][53][20][33][17][62][93]

이 과정을 계속반복하게 되면 배열은 정렬된 상태가 된다. 완전히 정렬된 상태라면 배열의 끝까지 탐색하는 동안 값의 교체가 한 번도 일어나지 않는다. 따라서 교체가 일어나지 않을 때까지 비교, 교체를 반복하면 된다.

알고리듬을 정리하면 다음과 같다.

  1. 배열의 첫 위치에서 그 다음 위치의 값을 비교하여 오른쪽 값보다 크다면 두 값을 교체한다.
  2. 배열의 끝까지 1의 과정을 반복한다.
  3. 1~2의 과정을 교체가 더 이상 일어나지 않을 때까지 반복한다.

이를 코드로 정리하면 다음과 같다. 버블 정렬은 제자리 정렬로, 인자로 넘겨진 리스트의 내부에서 순서를 조정하며 정렬함수 자체는 리턴값이 None이다.

from typing import List, TypeVar

# 임의의 타입 T를 정의한다.
T = TypeVar('T')


def bubble_sort(xs: List[T]):
    # 배열의 길이가 2보다 작으면 이미 정렬된 상태이다.
    l = len(xs)
    if l < 2:
        return
        
    while True:
        swapped = False # 교체가 일어났는지 여부
        for i in range(l - 1):
            if xs[i] > xs[i+1]:
                xs[i], xs[i+1] = xs[i], xs[i+1]
                swapped = True
        # 교체가 일어나지 않았다면 루프탈출
        if not swapped:
            break