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

버블 정렬 (Bubble Sort)

 

1) 개요

최소 값을 선택해서 이동한다.

 

	정렬된 데이터	정렬할 데이터
입력 데이터		17  14  11  19  13
1단계	11	17  14  19  13
2단계	11  13	17  14  19
3단계	11  13  14	17  19
4단계	11  13  14  17	19
5단계	11  13  14  17  19

 

2) 절차

입력

17

14

11

19

13

15

 

i = 5

0 부터 i - 1 까지, 두 쌍의 값을 비교하여, 왼쪽 값이 크면 서로 위치를 바꾼다.

 

17	14	11	19	13	15
14	17	11	19	13	15

 

14	17	11	19	13	15
14	11	17	19	13	15

 

14

11

17

19

13

15

 

14	11	17	19	13	15
14	11	17	13	19	15

 

14	11	17	13	19	15
14	11	17	13	15	19

 

i = 5 단계를 실행한 결과

0 부터 5 까지의 최대 값이 5 위치에 있다.

 

i = 4

14	11	17	13	15	19
11	14	17	13	15	19

 

11

14

17

13

15

19

 

11	14	17	13	15	19
11	14	13	17	15	19

 

11	14	13	17	15	19
11	14	13	15	17	19

 

i = 4 단계를 실행한 결과

0 부터 4 까지의 최대 값이 4 위치에 있다.

 

 

i = 3

11

14

13

15

17

19

 

11	14	13	15	17	19
11	13	14	15	17	19

 

11

13

14

15

17

19

i = 3 단계를 실행한 결과

0 부터 3 까지의 최대 값이 3 위치에 있다.

 

 

 

i = 2

11

13

14

15

17

19

 

11

13

14

15

17

19

i = 2 단계를 실행한 결과

0 부터 2 까지의 최대 값이 2 위치에 있다.

 

i = 1

11

13

14

15

17

19

i = 1 단계를 실행한 결과

0 부터 1 까지의 최대 값이 1 위치에 있다.

 

 

3) 요약

for (i = a.length - 1; i >= 1; --i) {
    for (j = 0; j < i; ++j) {
        if (a[j] > a[j + 1])
            swap(a, j, j + 1);
    }
}

 

4) 버블 정렬 개선

위 절차에서 i = 2 단계에서 이미 배열을 정렬되어 있다.

이렇게 이미 배열의 정렬이 끝난 경우에, 무의미한 반복을 계속하지 않고 종료할 수 있도록 개선하자.

 

for (i = a.length - 1; i >= 1; --i) {
    boolean 완료 = true;
    for (j = 0; j < i; ++j) {
        if (a[j] > a[j + 1]) {
            swap(a, j, j + 1);
            완료 = false;
        }
    }
    if (완료) break;
}

 

개선된 버블 정렬의 수행시간

입력 배열의 크기가 n이고, c는 상수

 

이미 거의 다 정렬되어 있고, 최대 (n * 1/c) 개의 항목만 순서가 틀어져 있다면

O(n2)

 

최대 c 개의 항목만 순서가 틀어져 있다면,

O(n)