[알고리즘][파이썬/Python] 버블 정렬 (Bubble Sort)

정의

차례로 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식의 정렬 알고리즘

 

동작 방식

1. 배열(혹은 리스트)의 첫 번째 원소부터 마지막 원소까지 인접 원소 간 대소 비교를 반복하는데, 더 큰 값을 가진 원소가 왼쪽에 있다면 서로 자리를 바꿈 (swap)

2. 위 과정을 반복하여 한 단계가 끝나면 가장 큰 값을 가진 원소가 배열 (혹은 리스트)의 마지막 자리로 정렬되어 있음

3. 한 단계가 끝날 때마다 맨 끝에 위치한 원소는 정렬된 상태이므로 다음 단계에서는 정렬된 원소를 제외하고 대소 비교를 실행

 

메모리 사용 공간

n개의 원소에 대하여 n개의 메모리 사용

 

연산 시간

1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우
- 비교횟수 : i번째 실행 시 (n-i) 번 비교하므로, n(n-1) / 2 번
- 자리교환횟수 : 자리 교환이 발생하지 않는다.
- 총 소요 시간 : n(n-1) / 2
    
2. 최악의 경우 (Worst Case) : 자료가 역순으로 정렬되어 있는 경우
- 비교횟수 : i번째 실행 시 (n-i) 번 비교하므로, n(n-1) / 2 번
- 자리교환횟수 : 모든 i번째 실행 시 (n-i) 번 교환하므로, n(n-1) / 2 번
- 총 소요 시간 : n(n-1)

 

∴ 시간 복잡도 T(n) = O(N^2)

 

소스 코드

# 버블 정렬 (Bubble Sort)

# 버블 정렬 - 오름차순 (Bubble Sort - Ascending)
def bubbleSort_ASC(arr):
    n = len(arr)
    for i in range(n-1, -1, -1):
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 버블 정렬 - 내림차순 (Bubble Sort - Descending)
def bubbleSort_DESC(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-1, i, -1):
            if arr[j] > arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return arr


# 난수를 생성하여 test해보기 (Test by random number) 
from random import randint

lst = [randint(1, 101) for i in range(5)]
print('Bubble Sort(ASC) :', lst, end=' '); print('->', bubbleSort_ASC(lst))
# Bubble Sort(ASC) : [93, 59, 7, 64, 63] -> [7, 59, 63, 64, 93]

lst = [randint(1, 101) for i in range(5)]
print('Bubble Sort(DESC) :', lst, end=' ');print('->', bubbleSort_DESC(lst))
# Bubble Sort(DESC) : [35, 47, 55, 75, 77] -> [77, 75, 55, 47, 35]

 

버블 정렬의 개선

버블 정렬의 시간 복잡도는 O(N^2)으로 매우 좋지 못하다. 그래서, 효율성을 증진시키기 위해 bool 타입의 변수를 사용할 수 있다.

• 처음 for문에서 change = False 를 할당해주고
• 이중 for문 안에서 자리 교환이 일어나면 change = True 할당.
• 실행 도중 모든 자료가 정렬되면 더 이상 자리 교환을 하지 않는다는 버블 정렬 알고리즘의 특성을 이용한 것으로, 만약 i번째 실행에서 한 번도 자리 교환이 일어나지 않아 change가 그대로 False라면, 모든 자료가 정렬된 것이므로 정렬 알고리즘을 중단

def bubbleSort2_ASC(arr):
    n = len(arr)
    for i in range(n-1, -1, -1):
        change = False
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                change = True
        if change == False:
            break
    return arr

그렇다면 얼마나 효율성이 증진되는 것일까? 일단 오름차순으로 정렬하는 버블 정렬에 대해 개념적으로만 생각해보자.

• 최악의 경우, 즉 자료가 역순으로 정렬되어 있을 경우 효율성은 증진되지 않는다. 개선한 부분은 '이미 정렬되어 있는 상태라면 더이상의 무의미한 반복을 회피'한 것이기 때문이다. 정렬 내 값들이 역순으로 정렬되어 있다면 모든 단계에서 change는 True다.
• 최선의 경우, 비교만 n-1번 하고 종료되므로 최선의 경우만 따져본다면 O(N)이 될 수도 있겠다. 하지만, Big-O Notation은 최악의 경우를 기준으로 하기 때문에 시간 복잡도에는 큰 영향을 주지 못한다고 볼 수 있다.

하지만 개인적으로 궁금하기 때문에 두 알고리즘의 성능을 비교해보았다.

from random import randint
from timeit import *

# common bubble sort
def bubbleSort_ASC(arr):
    n = len(arr)
    for i in range(n-1, -1, -1):
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# improved bubble sort
def bubbleSort2_ASC(arr):
    n = len(arr)
    for i in range(n-1, -1, -1):
        change = False
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                change = True
        if change == False:
            break
    return arr

for i in range(5):
    lst = [randint(1, 5001) for i in range(500)]
    t1 = Timer("bubbleSort_ASC(lst)", "from __main__ import bubbleSort_ASC, lst")
    t2 = Timer("bubbleSort2_ASC(lst)", "from __main__ import bubbleSort2_ASC, lst")
    t1_P = t1.timeit(number = 20)
    t2_P = t2.timeit(number = 20)
    print("  common bubble sort * 20 times :", '%.5f' % t1_P, "seconds")
    print("improved bubble sort * 20 times :", '%.5f' % t2_P, "seconds")
    print("The two Algorithms differ by", "%d" % (t1_P/t2_P), "times in performance.\n")

#   common bubble sort * 20 times : 0.79366 seconds
# improved bubble sort * 20 times : 0.00229 seconds
# The two Algorithms differ by 346 times in performance.

#   common bubble sort * 20 times : 0.57355 seconds
# improved bubble sort * 20 times : 0.00402 seconds
# The two Algorithms differ by 142 times in performance.

#   common bubble sort * 20 times : 0.48350 seconds
# improved bubble sort * 20 times : 0.00111 seconds
# The two Algorithms differ by 436 times in performance.

#   common bubble sort * 20 times : 0.69628 seconds
# improved bubble sort * 20 times : 0.00327 seconds
# The two Algorithms differ by 213 times in performance.

#   common bubble sort * 20 times : 0.67580 seconds
# improved bubble sort * 20 times : 0.00363 seconds
# The two Algorithms differ by 186 times in performance.

1부터 5,000 사이의 무작위 숫자 500개로 구성된 동일한 리스트에 대해 일반적인 버블 정렬과 개선된 버블 정렬을 수행한 결과, 적게는 142배에서 크게는 436배까지의 성능 차이를 보였다. 물론 최악의 경우에는 0배일 것이며 최선의 경우에는 훨씬 더 큰 성능 차이를 보일 것이다. 중요한 것은 성능이 좋지 못했던 버블 정렬을 그나마 개선했다는 것이다!