티스토리 뷰
소개
Bubble Sort는 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 
일반적으로 가장 빠른 정렬 알고리즘은
Quick Sort로 시간 복잡도입니다.
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라는 이름을 가지게 되었다고 하네요^^ 아래 버블 소트의 애니매이션 예시에서 정말 거품 같은지 직접 확인해 보시기 바랍니다.
정렬과정
다음과 같이 다섯 개의 숫자가 주어졌을 때, Bubble Sort로 정렬해 보겠습니다.
이를 배열에 담으면 아래 표와 같습니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 5 | 3 | 7 | 9 | 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 |
다음 오른쪽으로 한칸 이동하여 5와 7을 비교합니다. 여기서는 이미 큰 수 (7) 가 뒤에 있으므로 교체하지 않습니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 |
7 |
9 | 1 |
다시 오른쪽으로 한칸 이동하여 7와 9을 비교합니다. 여기서도 이미 큰 수 (9) 가 뒤에 있으므로 교체하지 않습니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 |
9 |
1 |
다시 오른쪽으로 한칸 이동하여 9와 1을 비교합니다. 9가 1보다 더 큰 수 이므로, 두 수의 자리를 교체해 줍니다.
교체전
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 | 9 |
1 |
교체후
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 | 1 |
9 |
자, 한번의 순회가 끝났습니다. 이 알고리즘의 이름이 왜
Bubble Sort인지 이제 조금 아시겠나요?모든 원소를 한 번씩 들러본 결과, 다섯개의 숫자 중
가장 큰 수인 9가 파도처럼 밀려 맨 마지막, 즉 정렬이 완료 되었을 때의 자신의 자리를 찾아갔습니다.여기서 다음번 순회 부터는 모든 원소를 방문할 필요가 없다는 것을 아시겠나요? 가장 큰 수 9는 정렬 된 후 자신이 있어야할 위치에 도착했기 때문입니다.
위와 같은 과정이 한차례 진행될 때마다,
뒤에서부터정렬이 완료된 원소들이하나씩 위치하게 되는 것을 볼 수 있습니다. 정렬이 완료된 원소들은 다시 정렬 될 필요가 없겠죠?따라서 두 번째 순회 부터는 이미 정렬이 완료된 원소들을
제외한원소들만 방문하여 정렬해 주면 됩니다.
이제 나머지 원소들의 자리도 찾아주기 위해 9를 제외한 원소들을 처음부터 다시 반복하여 비교해 봅시다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 | 7 | 1 | 9 |
3, 5 를 비교했을때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않습니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 |
5 |
7 | 1 | 9 |
다음 오른쪽으로 한칸 이동하여 5와 7을 비교합니다. 이미 큰 수( 7 ) 가 뒤에 있으므로 교체하지 않습니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 |
7 |
1 | 9 |
다시 오른쪽으로 한칸 이동하여 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 |
3, 5 를 비교했을때 이미 큰 수( 5 ) 가 뒤에 있으므로 자리를 교체하지 않습니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 |
5 |
1 | 7 | 9 |
다음 오른쪽으로 한칸 이동하여 5와 1을 비교합니다. 5가 1보다 더 큰 수 이므로, 두 수의 자리를 교체해 줍니다.
교체 전
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 5 |
1 |
7 | 9 |
교체 후
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 1 |
5 |
7 | 9 |
계속 같은 방식으로 세 번째 순회를 시작합니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 1 | 5 | 7 | 9 |
3, 1를 비교했을때 1보다 3이 더 큰 수 이므로 자리를 교체해 줍니다.
교체 전
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 |
1 |
5 | 7 | 9 |
교체 후
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 1 |
3 |
5 | 7 | 9 |
이후의 과정도 위의 방식처럼 진행하게 됩니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 1 | 3 | 5 | 7 | 9 |
여기서는 이제 정렬이 끝났으므로 생략하도록 하겠습니다.
이제
Bubble Sort가 어떻게 작동하는지 아시겠나요?
원소들이 큰 순서대로 뒤로 밀려가 거품처럼 정렬되는 모습을 볼 수 있었습니다.
알고리즘 분석
다음으로 시간복잡도를 알아봅시다.
비교 횟수
버블 정렬은 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝납니다. 위의 예제에서는 총 원소 개수가 5개 이므로, 4 + 3 + 2 + 1 = 10번 비교하게 됩니다. 이를 수식으로 일반화 시키면 다음과 같습니다.
자리 교환 횟수
최선의 경우 ( 이미 정렬된 원소들이 주어진 경우 ) , 자리 교환이 한번도 이루어 지지 않으므로, 시간복잡도에 영향을 미치지 않게 됩니다.
하지만 최악의 경우 ( 역순으로 정렬된 원소들이 주어진 경우 ), 원소를 비교 할 때마다 자리 교환이 일어나므로, 자리 교환 횟수 또한 비교 횟수와 같이
가 됩니다.
따라서 평균적으로
의 시간복잡도를 가지게 됩니다.
애니매이션 예시
위키백과에서 만든 애니매이션과 또 다른 동영상예시를 첨부합니다. 동영상 예시를 보시면 더 재미있게 Bubble Sort를 이해하실 수 있습니다. 원소들이 춤을 추거든요..ㅋㅋ
위 애니메이션의 y축은 수의 크기, x축은 원소의 인덱스를 나타냅니다. 큰 수부터 거품처럼 밀려 제 자리를 찾아 정렬되는 것을 볼 수 있습니다.
- 동영상예시
…
구현
코드는 굉장히 간단합니다. 위에서 순회할 원소의 개수가 하나씩 줄어든다는 점을 기억 하셨다면 쉽게 이해하실 수 있습니다.
1.int main()
2.{
3. int N = 5; //배열의 길이
4. int i, j, temp;
5. int data[] = { 5, 3, 7, 9, 1 };
6.
7. // Bubble Sort
8. for (i = 0; i < N; i++) {
9. for (j = 0; j < N-(i+1); j++) {
10. if (data[j] > data[j+1]) {
11. // 자리교환
12. temp = data[j+1];
13. data[j+1] = data[j];
14. data[j] = temp;
15. }
16. }
17. }
18.}
정리
Bubble Sort는 이처럼 이해하기도 쉽고 코드도 단순하지만, 
예제에서는 원소의 개수가 5개 뿐이라 10번의 연산만 하면 되었습니다.
하지만 데이터의 개수가 만 개만 되어도 무려 약 오천만 번의 비교 연산을 필요로 하기 때문에 Bubble Sort는 데이터의 개수가 적은 경우에 주로 사용하게 됩니다.
추가적으로 Bubble Sort 를 개선하는 코드를 구글링 해보시면 도움이 됩니다. ( 최선의 경우 비교 자체를 시작 하지 않게, 최악의 경우 뒤에서 부터 정렬 등등..)
끝
- Total
- Today
- Yesterday