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

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다.

버블 정렬은 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다.

이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

 

아래와 같은 8개의 숫자가 임의의 순서로 나열되어 있다.

6 3 8 5 2 7 4 1

 

이 숫자들을 오름차순으로 정렬하기 위해 바로 옆에 있는 숫자들과 비교하는 방법을 사용해 보자.

 

먼저 가장 앞의 6과 3을 비교해서 순서를 바꾼다.

교환 전: 6 3 8 5 2 7 4 1

교환 후: 3 6 8 5 2 7 4 1

 

다음 쌍인 6과 8을 비교해보면 교환할 필요가 없으므로 그대로 둔다.

 

바로 다음 쌍인 8과 5를 비교해서 순서를 바꾸자.

교환 전: 3 6 8 5 2 7 4 1

교환 후: 3 6 5 8 2 7 4 1

 

이런 식으로 숫자 끝까지 진행하면 아래와 같이 정렬이 된다.

3 6 5 2 7 4 1 8

 

하지만 아직 오름차순으로 정렬이 되지 않았기 때문에 다시 처음부터 동일한 작업을 반복한다.

3 6 5 2 7 4 1 8

3 6 5 2 7 4 1 8 (교환)

3 5 6 2 7 4 1 8 (교환)

3 5 2 6 7 4 1 8 

3 5 2 6 7 4 1 8 (교환)

3 5 2 6 4 7 1 8 (교환)

3 5 2 6 4 1 7 8

 

조금 더 잘 정렬이 되었다. 이 과정을 끝까지 반복하면 최종적으로 아래와 같이 오름차순으로 정렬이 될 것이다.

1 2 4 3 5 6 7 8

 

의사코드는 다음과 같다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

 

파이썬으로 구현하면 다음과 같다.

def bubbleSort(alist):
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

 

중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로  (n-1)*(n-2) = n^2-3n+2(n−1)∗(n−2)=n^​2​​−3n+2  번의 비교 및 교환이 필요하다.

여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있다.

정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 Ω(n^2)이 된다.

 

만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면 어떨까?

원래의 의사코드에서 안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것이다.

따라서 바깥쪽 루프를 교환이 일어나지 않을 때까지만 수행하도록 다음과 같이 바꿀 수 있다.

Repeat until no swaps

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

 

따라서 최종적으로 버블 정렬의 하한 Ω(n)이 된다.

출처: 부스트코스, 모두를 위한 컴퓨터 과학, https://www.boostcourse.org/cs112/lecture/119022/?isDesc=false