[알고리즘] 버블정렬

버블정렬은 리스트를 검사하여 두 인접한 원소가 오름차순 정렬에 맞지 않으면 이들을 서로 교환하는 알고리즘 입니다.

 

a[1], a[2] 비교 및 교환

a[2], a[3] 비교 및 교환

a[3], a[4] 비교 및 교환

                .

                .

                .

a[n-1], a[n] 비교 및 교환  

이 과정을 반복하면 가장 큰 원소가 배열의 n 위치로 끓어 오르게 되는데, 이것이 첫 번째 패스 입니다.

두 번째 패스에서는 다시 배열의 처음부터 인접한 원소를 비교하여 순서가 맞지 않을 경우 교환하면서 검사합니다.

이 때는 마지막 비교가 a[n-2] 와 a[n-1]이 됩니다. // 이미 가장 큰 원소는 가장 오른쪽에 들어가 있기 때문입니다.

이 패스는 배열에서 두 번째로 큰 원소를 n-1의 위치로 끓어 오르게 합니다.

 

이 정렬은 가장 큰 원소가 가장 오른쪽으로 이동하게되는 알고리즘입니다.

 

알고리즘 특징

• 거품 정렬은 점점 큰 값들을 뒤에서 부터 앞으로 하나씩 쌓여 나가게 때문에 후반으로 갈수록 정렬 범위가 하나씩 줄어들게 됩니다.
• 왜냐하면, 다음 패스에서는 이전 패스에서 뒤로 보내놓은 가장 큰 값이 있는 위치 전까지만 비교해도 되기 때문입니다.
• 제일 작은 값을 찾아서 맨 앞에 위치시키는 선택 정렬과 비교했을 때 정반대의 정렬 방향을 가집니다.
• 다른 정렬 알고리즘에 비해서 자리 교대(swap)가 빈번하게 일어나는 경향을 가지고 있습니다. 예를 들어, 선택 정렬의 경우 각 패스에서 자리 교대가 딱 한번만 일어납니다.
• 최적화 여지가 많은 알고리즘입니다. 예를 들어, 위 그림에서 Pass 5는 생략할 수 있는 패스입니다. 왜냐하면 Pass 4에서 한 번도 자리 교대가 일어나지 않았기 때문입니다.

복잡도 분석

• 거품 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
• 시간 복잡도는 우선 루프문을 통해 맨 뒤부터 맨 앞까지 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 하나의 루프에서는 인접한 값들의 대소 비교 및 자리 교대를 위해서 O(N)을 시간이 필요하게 됩니다. 따라서 거품 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.
• 하지만, 거품 정렬은 부분적으로 정렬되어 있는 배열에 대해서는 최적화를 통해서 성능을 대폭 개선할 수 있으며, 완전히 정렬되어 있는 배열이 들어올 경우, O(N)까지도 시간 복잡도를 향상시킬 수 있습니다.

구현

선택 정렬과 마찬가지로 두 개의 반복문이 필요합니다. 내부 반복문에서는 첫번째 값부터 이전 패스에서 뒤로 보내놓은 값이 있는 위치 전까지 앞뒤 값을 계속해서 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 자리 교대(swap)를 합니다. 외부 반복문에서는 뒤에서 부터 앞으로 정렬 범위를 n-1부터 1까지 줄여나갑니다.

 

 

ADL 코드

bubbleSort(a[], n)
	for(i <-n; i > 1; i<- i-1) do 
    	for(j<- 1; j < i; j<_ j+1) do 
          if(a[j]> a[j+1]) then a[j]와 a[j+1] 교환;
end bubbleSort()

 

Python 코드

def bubbleSort(a, n):
	for i in range(n, 1, -1):
    	for j in range(1, i):
        	if a[j] > a[j+1]: 
            	a[j], a[j+1] = a[j+1], a[j]

 

버블 정렬 알고리즘의 비교 횟수를 생각해봅시다.

 

i = 5일때 4번 비교

i = 4일때 3번 비교

i = 3일때 2번 비교

i = 2일때 1번 비교

따라서 버블 정렬 알고리즘은 N개의 원소 각각에 대해 N-1번의 비교를 해야되기 때문에 전체 비교 횟수는 N(N-1)/2가 되어

전체 시간 복잡도는 O(N^2)가 됩니다. 

 

레코드를 계속 교환하기 때문에 레코드의 크기가 큰 경우 불리합니다.

 

거의 정렬된 화일일 경우 유리한 정렬입니다.

 

안정적인 제자리 정렬입니다.