[알고리즘] 2) 버블 정렬 알고리즘

[출처 DaleSeo]

버블 정렬 알고리즘

버블 정렬은 선택 정렬과 유사한 정렬 방식이다. 

선택 정렬은 '최소값'을 확정하고 난 후에 다음 비교로 넘어간 것에 반해 버블 정렬은 바로 직전, 직후 값들을 비교해 나가는 방식을 말한다. 

 

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다. 

선택 정렬과 마찬가지로 구현은 쉽지만, 시간복잡도로 봤을 때는 효율적이지 않은 정렬 방식이다. 

설명

1. 먼저 4와 3을 비교, 3이 더 작음으로 서로 스와핑한다. 

[4, 3, 5, 1, 2]
 ^  ^
4 > 3 => Swap
[3, 4, 5, 1, 2]

2. 이후 4와 5를 비교, 바꿀 필요가 없음을 확인. 

[3, 4, 5, 1, 2]
    ^  ^
4 < 5 => No Swap

3. 5와 1을 비교, 1이 더 작음으로 서로 스와핑 

[3, 4, 5, 1, 2]
       ^  ^
5 > 1 => Swap
[3, 4, 1, 5, 2]

이러한 과정을 반복 수행한다. 

파이썬 구현

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

[최적화]

1. 이전 차례에서 스와핑이 한번도 일어나지 않은 경우에는 정렬되지 않은 값이 하나도 없었다고 간주할 수 있다.

이럴 경우에는 비교를 지속하지 않고 종료한다. 

* swap True, False Flag 사용. 

Initial: [1, 2, 3, 5, 4]

 Pass 1: [1, 2, 3, 4, 5] => Swap 있었음
                      *
 Pass 2: [1, 2, 3, 4, 5] => Swap 없었음
                   *  *
=> 이전 패스에서 swap이 한 번도 없었으니 종료

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        swapped = False
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

 

2. 마지막 스와핑 위치를 확인하여 기록하고, 그 뒤에 모조리 변화가 없었다면 비교 자체를 skip하는 방법.

* last_swap 변수 추가. 

Initial: [3, 2, 1, 4, 5]

 Pass 1: [2, 1, 3, 4, 5] => 마지막 Swap 위치가 index 1
             ^        *
 Pass 2: [1, 2, 3, 4, 5] => 중간 패스 skip하고 바로 index 1로 보낼 값 찾기
          ^     *  *  *

def bubble_sort(arr):
    end = len(arr) - 1
    while end > 0:
        last_swap = 0
        for i in range(end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                last_swap = i
        end = last_swap