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

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

버블 정렬(Bubble Sort)?

서로 인접한 두 원소끼리 대소비교를 하며 차례대로 정렬하는 알고리즘이다. 비효율적인 정렬 알고리즘의 대표격으로 알려져 있다. 단순히 인접 원소끼리 대소비교 후 치환을 결정하기 때문에 추가 메모리를 요구하지 않는 제자리 정렬에 해당한다.

버블 정렬 동작

위 그림의 배열을 정렬한다고 해보자.

만약 정렬하고자 하는 배열의 길이가 n이라면 총 n-1개의 원소에 대해 $n-1,\ n-2,\ \cdots\ 1$번씩 비교하며 정렬하므로 전체 비교 횟수는 $\cfrac{n(n-1)}{2}$이고 그에 따른 시간복잡도는 $O(n^2)$이다.

python 코드

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

a = [3, 1, 2, 5, 4, 6]
b = [6, 5, 4, 3, 2, 1]
c = [5, 5, 3, 3, 1, 1]
print(f'bubble a:{bubble(a)}, b:{bubble(b)}, c:{bubble(c)}')