버블정렬은 정렬 중에서 가장 기본적이고 쉬운 알고리듬이다. 버블정렬은 배열의 앞에서부터 큰 원소를 뒤쪽으로 보내는 작업을 반복적으로 시행하여 배열 전체를 정렬한다. 이 때 큰 값들이 물속에서 거품이 떠오르는 것처럼 움직이기 때문에 ‘버블’이라는 이름이 붙었다.
간단한 예를 통해서 버블 정렬이 어떻게 작동하는지 살펴보자. 아래와 같은 배열이 있다고 가정하자.
[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의 과정을 반복한다.
- 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