[Algorithm] 버블정렬

개요

인접한 두 원소를 비교하며 자리를 계속해서 교환해 나가는 정렬 방식이다. 매우 직관적이나, 그만큼 비효율적이다.

원리

각 단계마다 다음과 같은 과정을 거친다.

• 단계별로 모든 원소에 대해 인접한 두 값을 비교한다.
• 앞의 값이 뒤의 값보다 크다면(혹은 작다면) 자리를 교환한다.

한 단계가 끝날 때마다 가장 큰(혹은 작은) 원소가 제일 마지막 자리에 정렬된다.

^{이미지 출처 : https://www.fun-coding.org/Chapter12-bubblesorting.html}

예) 55 7 78 12 42를 오름차순으로 버블정렬하는 과정

정렬 원소 미정렬원소

리스트	비교 대상	동작	정렬 결과
55 7 78 12 42	55 7	교환	7 55 78 12 42
	55 78	유지	7 55 78 12 42
	78 12	교환	7 55 12 78 42
	78 42	교환	7 55 12 42 78
7 55 12 42 78	7 55	유지	7 55 12 42 78
	55 12	교환	7 12 55 42 78
	55 42	교환	7 12 42 55 78
7 12 42 55 78	7 12	유지	7 12 42 55 78
	12 42	유지	7 12 42 55 78
7 12 42 55 78	7 12	유지	7 12 42 55 78
7 12 42 55 78	7	종료	7 12 42 55 78

구현

이중 반복문을 사용해 구현한다. 바깥쪽 반복문에 의해 안쪽 반복문의 범위가 제어된다. 한 단계를 마치면 마지막에 정렬이 종료된 원소가 위차하므로, 단계를 거칠수록 정렬의 범위가 1씩 작아진다.

def BubbleSort(a):
    for i in range(len(a)-1, 0, -1): 
        for j in range(0, i):
            if a[j] > a[j+1]: # swap
                a[j], a[j+1] = a[j+1], a[j]
     return a

반복문 범위 설정에 따라 다음과 같이 구현할 수도 있다. 위의 방식보다 이해가 조금 더 직관적이다.

def BubbleSort(a):
    for i in range(len(a)): # 리스트의 크기만큼 아래 횟수 반복.
        for j in range(len(a)-1): # 각 단계별로 정렬이 끝나지 않은 원소들.
            if a[j] > a[j+1]:
                a[j+1], a[j] = a[j], a[j+1]
    return a

성능

평균적으로 $O(n^2)$의 시간 복잡도를 갖는다. 리스트 안에 n개의 원소가 존재할 때, 최악의 경우 (n-1) + (n-2) + … + 1번 비교가 이루어진다. 하나의 배열 안에서 정렬이 이루어지므로, 공간 복잡도의 경우 $O(n)$이다.