알고리즘 버블 정렬(Bubble Sort)

문제

 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
 1 5 8 10 7 6 3 2 9 4

 

알고리즘 종류

• Selection sort (내부 : 교환)
• Bubble Sort (내부 : 교환)
• Quick Sort (내부 : 교환)
• Insertion Sort (내부 : 삽입)
• Shell Sort (내부 : 삽입)
• Merge Sort (내부 : 병합)
• Heap Sort (내부 : 선택)
• Radix Sort (내부 : 분배)

 

가장 작은 값을 선택해서 앞으로 보내는 선택정렬에 이어, 이번시간에는 버블 정렬에 대해 알아보도록 합시다.

버블정렬은 선택 정렬과 기본 개념이 비슷합니다. 인접한 두 숫자를 비교해서, 더 작은 숫자를 앞으로 보내주는 것을 반복하는 정렬입니다.

 

 

예를들어 arrpay[5] = {10, 7, 6, 3, 2}가 있다고 가정했을 때

 

시작상태	10	7	6	3	2
i : 0	7	10	6	3	2
i : 1	7	6	10	3	2
i : 2	7	6	3	10	2
i : 3	7	6	3	2	10
i : 0	6	7	3	2	10
i : 1	6	3	7	2	10
i : 2	6	3	2	7	10
i : 0	3	6	2	7	10
i : 1	3	2	6	7	10
i : 0	2	3	6	7	10

1. 10과 7을 비교합니다. 10이 더 크기 때문에 뒤로 이동합니다.

2. 10과 6을 비교합니다. 10이 더 크기 때문에 뒤로 이동합니다.

3. 10과 3을 비교합니다. 10이 더 크기 때문에 뒤로 이동합니다.

4. 10과 2을 비교합니다. 10이 더 크기 때문에 뒤로 이동합니다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. 7과 6을 비교합니다. 7이 더 크기 때문에 뒤로 이동합니다.

2. 7과 3을 비교합니다. 7이 더 크기 때문에 뒤로 이동합니다.

3. 7과 2을 비교합니다. 7이 더 크기 때문에 뒤로 이동합니다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. 6과 3을 비교합니다. 6이 더 크기 때문에 뒤로 이동합니다.

2. 6과 2을 비교합니다. 6이 더 크기 때문에 뒤로 이동합니다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

2. 2과 3을 비교합니다. 3이 더 크기 때문에 그대로 둡니다.

 

 

버블정렬 알고리즘

#include <stdio.h>

int main(void) {
	int i, j, temp;
	int array[10] = { 1, 5, 8, 10, 7, 6, 3, 2, 9, 4};
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
	return 0;
}

 

  위의 소스코드는 서로인접한 값 array[j] 와 array [j+1] 를 비교해서 더 작은값을 앞으로 보내는 과정을 가집니다.

 

 

버블 정렬(bubble sort) 알고리즘의 특징

장점

- 구현이 간단하다

 

단점

- 순서에 맞지 않는 요소를 인접한 요소와 교환한다.

- 가장 왼쪽에 있는 요소는 마지막으로 이동하기 위해, 모든 다른 요소들과 교환이 이루어 져야 한다.

- 알맞는 순서에 있는 요소더라도, 교환이 일어난다.

 

버블 정렬의 시간복잡도 O(N^2)

n-1, n-2, n-3, ... , 2, 1 번 = n(n-1)/2

T(n) = O(n^2)

 

정렬 알고리즘	최고	평균	최저	Run-time
삽입 정렬	n	n^2	n^2	7.438
선택 정렬	n^2	n^2	n^2	10.842
버블 정렬	n^2	n^2	n^2	22.894
셸 정렬	n	n^1.5	n^2	0.056
퀵 정렬	nlog2n	nlog2n	n^2	0.014
힙 정렬	nlog2n	nlog2n	nlog2n	0.034
병합정렬	nlog2n	nlog2n	nlog2n	0.026