버블 정렬 (Bubble Sort)

1. 버블 정렬 (Bubble Sort) 이란?

  : 인접한 두 원소를 검사하여 정렬하는 방법

    원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보임

    코드가 단순해 자주 사용되는 정렬 알고리즘

↑

무작위 배열수의 버블 정렬 예

2. 장단점

- 장점 : 코드가 단순하다

- 단점 : 느리다 ( T(n) = O(n²) )

3. 버블 정렬 실행 과정 (오름차순)

정렬할 배열

4

1

5

2

3

4 > 1 이므로 자리교체

4

1

5

2

3

1

4

5

2

3

4 < 5 이므로 자리교체 X

1

4

5

2

3

5 > 2 이므로 자리교체

1

4

5

2

3

1

4

2

5

3

5 > 3 이므로 자리교체 (가장 큰 수 5 고정됨)

1

4

2

5

3

1

4

2

3

5

1 < 4 이므로 자리교체 X

1

4

2

3

5

4 > 2 이므로 자리교체

1

4

2

3

5

1

2

4

3

5

4 > 3 이므로 자리교체 (두 번째로 큰 수 4 고정됨)

1

2

4

3

5

1

2

3

4

5

1 < 2 이므로 자리교체 X

1

2

3

4

5

2 < 3 이므로 자리교체 X (세 번째로 큰 수 3 고정됨)

1

2

3

4

5

1 < 2 이므로 자리교체 X (네 번째로 큰 수, 가장 작은 수 2, 1 고정됨)

1

2

3

4

5

4. C 언어 소스 코드 (오름차순)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <stdio.h>   int main() { int arr[] = {3, 1, 2, 5, 4}; int size = sizeof(arr) / sizeof(int); int temp; for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - 1 - i; j++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } }

5. 성능 분석

- 시간 복잡도

  : T(n) = O(n²)

    8번째 줄 loop : $$n번$$

    9번째 줄 loop : $$\sum_{k=1}^{n-1}{(n+1-k)}=\frac{1}{2}n^2+\frac{1}{2}n-1번$$

    10번째 줄 조건문 : $$\sum_{k=1}^{n-1}{(n+1-k)}=\frac{1}{2}n^2-\frac{1}{2}n번$$

    11~13번째 줄 대입연산 : $$0번\sim\sum_{k=1}^{n-1}{(n+1-k)}=\frac{1}{2}n^2-\frac{1}{2}n번$$

- 공간 복잡도

  : 제자리 정렬 (In-place sort)

    원소를 담는 공간 외에 옮겨지는 원소가 저장되는 공간 (위 소스 코드에서의 temp), 루프 변수 (위 소스 코드에서의 i, j) 만이 추가로 사용됨

※ 제자리 정렬 (In-place sort) 이란?

  : 원소들의 갯수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘