버블 정렬(bubble sort)

<버블 정렬(bubble sort)>

​인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.
첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(bubble) 정렬이라 한다. 

 

[버블 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 버블 정렬 방법으로 정렬하는 과정을 살펴보자.

① 인접한 두 원소를 비교하여 자리를 교환하는 작업을 첫 번째 원소부터 마지막 원소까지 차례로 반복하여 가장 큰 원소 69를 마지막 자리로 정렬.

② 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 31을 끝에서 두 번째 자리로 정렬.

③ 이과정을 반복 수행한다. 

 

④ 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 8을 끝에서 일곱 번째 자리로 정렬.

버블 정렬을 분석해보자.

[메모리 사용공간]
n개의 원소에 대하여 n개의 메모리 사용 

 

[연산 시간]
1. 최선의 경우 : 자료가 이미 정렬되어있는 경우
- 비교횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
- 자리교환횟수 : 자리교환이 발생하지 않음
2. 최악의 경우 : 자료가 역순으로 정렬되어있는 경우
- 비교횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
−자리교환횟수 : i번째 원소를 (n-i)번 교환하므로, n(n-1)/2 번
평균 시간 복잡도는 O(n2)이 된다.

 

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)