for textmining

버블정렬

05 Nov 2017 | Bubble sort sort

이번 글에서는 버블정렬(bubble sort)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.

concepts

버블정렬은 가장 간단하지만 비효율적인 정렬 알고리즘입니다. 이미 정렬되어 있는 데이터에 적합한 기법입니다. 다음과 같은 숫자들에 버블정렬을 적용한다고 칩시다.

4, 3, 5, 2

이를 배열에 담으면 다음과 같습니다.

index 0 1 2 3
value 4 3 5 2

버블정렬은 오른쪽 끝에서 시작해 오름차순 정렬합니다. 우선 2와 5를 비교합니다(위 표). 왼쪽에 있는 5가 크므로 자리를 바꿔 줍니다(아래 표).

index 0 1 2 3
value 4 3 2 5

이번엔 2와 3을 비교합니다(위 표). 왼쪽에 있는 3이 크므로 자리를 바꿔 줍니다(아래 표).

index 0 1 2 3
value 4 2 3 5

이번엔 2와 4를 비교합니다(위 표). 왼쪽에 있는 4가 크므로 자리를 바꿔 줍니다(아래 표). 포인터가 다 돌았으므로 첫번째 iteration이 끝났습니다.

index 0 1 2 3
value 2 4 3 5

이제는 정렬이 끝난 2를 제외하고, 4, 3, 5를 정렬할 차례입니다. 오른쪽 끝 요소인 5와 3을 비교합니다(위 표). 왼쪽에 있는 3이 작으므로 자리를 바꿀 필요가 없습니다(아래 표).

index 0 1 2 3
value 2 4 3 5

이번엔 3과 4를 비교합니다(위 표). 왼쪽에 있는 4가 크므로 자리를 바꿔 줍니다(아래 표). 이로써 두번째 iteration이 끝났습니다.

index 0 1 2 3
value 2 3 4 5

이제는 정렬이 끝난 2와 3을 제외하고, 4, 5를 정렬할 차례입니다. 마지막으로 5와 4를 비교합니다. 왼쪽에 있는 4가 작으므로 자리를 바꿀 필요가 없습니다. 이로써 모든 정렬이 끝났습니다.

계산복잡성

버블정렬은 큰 원소가 앞쪽으로 이동하면서 마치 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 이러한 명칭이 붙은 것 같습니다. 정렬 대상 데이터가 $n$개일 때 비교횟수는 다음 표와 같습니다.

iteration 비교 횟수 위치 변경 최대 횟수
1 $n-1$ $n-1$
2 $n-2$ $n-2$
… … …
$n-2$ $2$ $2$
$n-1$ $1$ $1$

버블정렬의 계산복잡성은 비교 횟수 + 위치변경 횟수에 비례합니다. 다음과 같습니다.

\[\begin{align*} T\left( n \right) =&2\times\sum _{ i=1 }^{ n-1 }{ i } \\ =&2\times\frac { n\left( n-1 \right) }{ 2 } \\ =&O\left( { n }^{ 2 } \right) \end{align*}\]

배열이 모두 순서대로 정렬되어 있는 상태라면 비교만 수행할 뿐 위치변경을 하지 않아도 되기 때문에 조금 더 가벼워질 수는 있을 겁니다. 그러나 아래와 같이 단 하나의 값이라도 제 자리에 있지 않으면 iteration마다 위치 변경을 해주어야 하기 때문에 계산복잡성은 여전히 $O(n^2)$이 됩니다. 매우 비효율적입니다.

6, 1, 2, 3, 4, 5

1, 6, 2, 3, 4, 5

1, 2, 6, 3, 4, 5

…

버블정렬의 특징

위 예시에서도 알 수 있듯 버블정렬은 정렬시 부가 메모리가 필요 없는 inplace sort 기법입니다. 아울러 두 값이 같으면 위치를 바꾸지 않기 때문에 stable sort 기법입니다.

파이썬 구현

버블정렬의 파이썬 코드는 다음과 같습니다.

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp



Related Posts

Comments