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

버블 정렬이란 (거품 정렬, bubble sort)​

버블 정렬은 서로 인접한 두 원소의 크기를 비교하여 정렬하는 방법이다.

구현은 간단하나 시간복잡도가 O(n^2) 으로 상당히 비효율적이다.

 

 

버블 정렬 예시 및 시간복잡도 증명​

간단한 예시를 통해 버블 정렬 과정을 나타내면 다음과 같다.

위 그림에서 확인할 수 있듯이, 5개의 요소를 거품 정렬을 적용해서 정렬하면

비교연산이 4회 + 3회 + 2회 + 1회 = 10회 소요되는 것을 확인할 수 있고,

요소의 개수를 N개로 일반화하면 (N-1) + (N-2) + (N-3) + ... + 2 + 1 가 된다.

 

이를 공차가 1인 등차수열 공식에 대입해보면,

결과적으로 N*(N+1) / 2 임을 알 수 있다.

 

이를 시간복잡도로 표현해보면 O(n^2) 임을 확인할 수 있다.

 

버블 정렬 예제 코드 (python)​

버블 정렬을 파이썬 코드로 작성하면 다음과 같다.

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]
    
    return arr

test = [3,7,1,4,5,6,2,9,8]
print(bubble_sort(test))    # [1, 2, 3, 4, 5, 6, 7, 8, 9] 

 

버블 정렬 성능 개선 방법과 예제 코드(python)​

만약 주어진 배열이 어느정도 정렬이 된 상태거나 정렬 진행중에 정렬이 완료된 상태일 경우,

기존 버블 정렬은 불필요한 연산을 진행하게 된다.

 

즉, 더 이상 정렬할 필요가 없어질 때 정렬을 멈추게 한다면

불필요한 연산을 줄임으로써 성능 개선을 할 수 있다.

 

버블 정렬 성능 개선 코드를 파이썬 코드로 작성하면 다음과 같다.

# <성능 개선 방법>
# 단계별로 정렬을 진행 중, 
# 만약 교체가 발생하지 않았다면 정렬이 완료된 것으로 간주하고 멈춘다.
def bubble_sort(array):
    for i in range(len(array)-1, 0, -1):
        quit = True
        for j in range(i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
                quit = False
        if quit:
            break
    
    return array

test = [3,7,1,4,5,6,2,9,8]
print(bubble_sort(test))    # [1, 2, 3, 4, 5, 6, 7, 8, 9] 

 

버블정렬 장단점​

• 장점
  • 이해하기 쉬우며, 동시에 구현도 간단하다.
• 단점
  • 시간복잡도가 O(n^2) 이기 때문에 비효율적이다.