개요[편집 / 원본 편집]
Bubble Sort는 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 [math]\displaystyle{ O(n^2) }[/math]의 시간 복잡도를 갖는다. 다른 정렬 알고리즘에 비해 속도가 상당히 느린 편[1]이지만, 코드가 단순하기 때문에 자주 사용된다.
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라는 이름을 가지게 되었다.
정렬 과정[편집 / 원본 편집]
다음과 같이 다섯 개의 숫자가 주어졌을 때, Bubble Sort로 정렬하는 방법은 다음과 같다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 5 | 3 | 7 | 9 | 1 |
첫번째 순회[편집 / 원본 편집]
1. 먼저 5와 3 을 비교했을때 3보다 5가 더 큰 수 이므로, 두 수의 자리를 교체한다.
- 교체 전
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 5 |
3 |
7 | 9 | 1 |
- 교체 후
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 |
5 |
7 | 9 | 1 |
2. 다음, 오른쪽으로 한 칸 이동하여 5와 7을 비교한다. 여기서는 이미 큰 수 (7) 가 뒤에 있으므로 교체하지 않는다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 |
7 |
9 | 1 |
3. 다시 오른쪽으로 한 칸 이동하여 7와 9을 비교한다. 여기서도 이미 큰 수 (9) 가 뒤에 있으므로 교체하지 않는다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 |
9 |
1 |
4. 다시 '오른쪽으로 한 칸 이동하여 9와 1을 비교한다. 9가 1보다 더 큰 수 이므로, 두 수의 자리를 교체한다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 | 1 |
9
|
첫번째 순회 정리[편집 / 원본 편집]
한 번의 순회가 끝났다. 모든 원소를 한 번 씩 들러본 결과, 다섯 개의 숫자 중 가장 큰 수인 9가 파도처럼 밀려 맨 마지막, 즉 정렬이 완료 되었을 때의 자신의 자리를 찾아갔다.
여기서 다음번 순회 부터는 모든 원소를 방문할 필요가 없다.[2]
위와 같은 과정이 한 차례 진행될 때마다, 뒤에서부터 정렬이 완료된 원소들이 하나 씩 위치하게 되는 것을 볼 수 있다. 정렬이 완료된 원소들은 다시 정렬 될 필요가 없다.
따라서 두 번째 순회 부터는 이미 정렬이 완료된 원소들을 제외한 원소들만 방문하여 정렬해 주면 된다.
두번째 순회[편집 / 원본 편집]
나머지 원소들의 자리도 찾아주기 위해 9를 제외한 원소들을 처음부터 다시 반복하여 비교해 보자.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 | 1 | 9 |
1. 3과 5 를 비교했을 때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않는다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 |
5 |
7 | 1 | 9 |
2. 다음 오른쪽으로 한 칸 이동하여 5와 7을 비교한다. 이미 큰 수( 7 ) 가 뒤에 있으므로 교체하지 않는다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 |
7 |
1 | 9 |
3. 다시 오른쪽으로 한 칸 이동하여 7와 1을 비교합니다. 7이 1보다 더 큰 수 이므로, 두 수의 자리를 교체한다.
- 교체 전
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 |
1 |
9 |
- 교체 후
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 1 |
7 |
9 |
두번째 순회 정리[편집 / 원본 편집]
두 번째 순회가 완료 되었다. 남은 네 개의 원소 중 가장 큰 수인 7이 자신의 자리를 찾아갔다.
세번째 순회[편집 / 원본 편집]
나머지 세 개의 원소들을 다시 처음부터 순회해 준다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 1 | 7 | 9 |
1. 3과 5 를 비교했을때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않는다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 |
5 |
1 | 7 | 9 |
2. 다음 오른쪽으로 한칸 이동하여 5와 1을 비교한다. 5가 1보다 더 큰 수 이므로, 두 수의 자리를 교체해 준다.
- 교체 전
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 |
1 |
7 | 9 |
- 교체 후
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 1 |
5 |
7 | 9 |
세번째 순회 정리[편집 / 원본 편집]
세번째 순회가 완료 되었다. 남은 세 개의 원소 중 가장 큰 수인 5가 자신의 자리를 찾아갔다.
네번째 순회[편집 / 원본 편집]
나머지 두 개의 원소들을 다시 처음부터 순회해 준다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 1 | 5 | 7 | 9 |
1. 3과 1을 비교한다. 3이 1보다 더 큰 수 이므로, 두 수의 자리를 교체해 준다.
- 교체 전
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 |
1 |
5 | 7 | 9 |
- 교체 후
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 1 |
3 |
5 | 7 | 9 |
네번째 순회 정리[편집 / 원본 편집]
네번째 순회로 정렬이 완료되었다. 원소들이 큰 순서대로 뒤로 밀려가 거품처럼 정렬되는 모습을 볼 수 있다.
알고리즘 분석[편집 / 원본 편집]
비교 횟수[편집 / 원본 편집]
버블 정렬은 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 전체 원소의 개수가 [math]\displaystyle{ n }[/math]개 라고 할 때, 총 [math]\displaystyle{ n-1 }[/math]번 순회하면 정렬이 끝난다.
위의 예제에서는 총 원소 개수가 5개 이므로, [math]\displaystyle{ 4 + 3 + 2 + 1 = 10 }[/math]번 비교하게 된다. 이를 수식으로 일반화 시키면 다음과 같다.
[math]\displaystyle{ (n-1)+(n-2)+...+2+1=(n-1) \times n \div 2 = \frac{n(n-1)}{2} }[/math]
자리 교환 횟수[편집 / 원본 편집]
최선의 경우[3], 자리 교환이 한번도 이루어 지지 않으므로, 시간복잡도에 영향을 미치지 않게 된다.
하지만 최악의 경우[4], 원소를 비교 할 때마다 자리 교환이 일어나므로, 자리 교환 횟수 또한 비교 횟수와 같이 [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] 가 된다.
따라서 평균적으로 [math]\displaystyle{ O(n^2) }[/math] 의 시간복잡도를 가지게 된다.
코드[편집 / 원본 편집]
순회할 원소의 개수가 하나씩 줄어든다는 점을 적용한 코드 예제이다.
int main()
{
int N = 5; //배열의 길이
int i, j, temp;
int data[] = { 5, 3, 7, 9, 1 };
// Bubble Sort
for (i = 0; i < N; i++) {
for (j = 0; j < N-(i+1); j++) {
if (data[j] > data[j+1]) {
// 자리교환
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
}
}
}
}
정리[편집 / 원본 편집]
Bubble Sort는 이처럼 이해하기도 쉽고 코드도 단순하지만, 이라는 시간복잡도 때문에 비교할 데이터의 개수가 많을 수록 성능이 저하된다.
예제에서는 원소의 개수가 5개 뿐이라 10번의 연산만 하면 되었지만, 데이터의 개수가 만 개만 되어도 무려 약 오천만 번의 비교 연산을 필요로 하기 때문에 Bubble Sort는 데이터의 개수가 적은 경우에 주로 사용하게 됩니다.