Bubble Sort (거품 정렬)

거품 정렬은 반복적으로 인접한 요소를 교환하며 동작하는 알고리즘이다.

 

아래는 ( 5 1 4 2 8 )에 거품정렬를 적용한 예제이다.

(큰 수를 오른쪽으로 보내는 방식으로 오름차순으로 정렬한다. 왼쪽에서 오른쪽으로 진행)

 

1단계 ( 5 1 4 2 8 ) 5와 1을 비교한다. 5는 1보다 크므로 5와 1의 위치변경이 발생한다. -> ( 1 5 4 2 8 ) ( 1 5 4 2 8 ) 5와 4를 비교한다. 5는 4보다 크므로 5와 4의 위치변경이 발생한다. -> ( 1 4 5 2 8 ) ( 1 4 5 2 8 ) 5와 2를 비교한다. 5는 2보다 크므로 5와 2의 위치변경이 발생한다. -> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) 5와 8를 비교한다. 5는 8보다 작으므로 위치변경이 발생하지 않는다. -> ( 1 4 2 5 8 )   1단계를 실행함으로 8은 정렬 완료 상태가 된다.   2단계 ( 1 4 2 5 8 ) 1과 4를 비교한다. 1은 4보다 작으므로 위치변경이 발생하지 않는다. -> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) 4와 2를 비교한다. 4는 2보다 크므로 4와 2의 위치변경이 발생한다. -> (1 2 4 5 8 ) ( 1 2 4 5 8 ) 4와 5를 비교한다. 4는 5보다 작으므로 위치변경이 발생하지 않는다. -> ( 1 2 4 5 8 )   정렬이 완료된 8은 비교 대상이 되지 않는다. 2단계를 실행함으로 5, 8은 정렬 완료 상태가 된다.   3단계 ( 1 2 4 5 8 ) 1과 2를 비교한다. 1은 2보다 작으므로 위치변경이 발생하지 않는다. -> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) 2와 4를 비교한다. 2는 4보다 작으므로 위치변경이 발생하지 않는다. -> ( 1 2 4 5 8 )   정렬이 완료된 5, 8은 비교 대상이 되지 않는다. 3단계를 실행함으로 4, 5, 8은 정렬 완료 상태가 된다.   4단계 ( 1 2 4 5 8 ) 1과 2를 비교한다. 1은 2보다 작으므로 위치변경이 발생하지 않는다. -> ( 1 2 4 5 8 )   정렬이 완료된 4, 5, 8은 비교 대상이 되지 않는다. 4단계를 실행함으로 2, 4, 5, 8은 정렬 완료 상태가 된다.

 

거품정렬은 위와 같은 방식으로 실행된다.

 

거품정렬 시간복잡도

- 최악의 경우 (배열이 정렬 기준 역순으로 되어 있을 경우)  : O(n*n)

- 최선의 경우 (이미 정렬이 되어 있는 경우) :O(n)

(기본적으로 알고리즘의 시간복잡도는 최악의 경우를 말한다.)

 

거품 정렬 예제 1

 

위의 코드는 아래와 같이 실행된다.

 

2단계 실행 후 정렬 완료 (컴퓨터는 그 사실을 알 수 없으므로 3단계를 실행)

3단계에서는 Swap이 발생하지 않는다. (정렬이 완료 되었음을 의미)

4단계 실행 (무의미한 실행)

 

무의미한 실행을 줄이기 위해서 최적화된 알고리즘은 아래와 같다.

 

거품 정렬 예제 2

 

위의 코드는 아래와 같이 실행된다. (무의미한 실행은 하지 않는다.)

 

2단계 실행 후 정렬 완료 (컴퓨터는 그 사실을 알 수 없으므로 3단계를 실행)

3단계에서는 Swap이 발생하지 않는다. (정렬이 완료 되었음을 의미. 알고리즘 종료)