Skip to main content

거품 정렬

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

거품 정렬은 버블 정렬이라고도 불리며, 서로 인접한 두 원소의 크기를 비교하여 정렬하는 방법이다. 구현은 간단하나 시간복잡도가 O(n2)O(n^2) 이여서 비효율적이다.

거품 정렬 예시 및 시간복잡도 증명​

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

위 그림에서 확인할 수 있듯이, 5개의 요소를 거품 정렬을 적용해서 정렬하면 비교연산이 4회 + 3회 + 2회 + 1회 = 10회 소요되는 것을 확인할 수 있고, 요소의 개수를 N개로 일반화하면 (N-1) + (N-2) + (N-3) + ... + 2 + 1 가 된다. 이를 공차가 1인 등차수열 공식에 대입해보면, 결과적으로 N∗(N−1)2\frac{N*(N-1)}{2} 임을 알 수 있다. 이를 시간복잡도로 표현해보면 위에서도 언급했듯 O(n2)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(n2)O(n^2) 이기 때문에 비효율적이다.

나올 수 있는 면접 질문​

  • 거품 정렬의 정의와 시간복잡도 증명
  • 거품 정렬 성능 개선이 가능여부와 가능하다면 방법은

참고​

기여자​


Junho Moon
📦