버블 정렬

지난 글: [알고리즘] - 정렬이란?

 

버블 정렬(bubble sort)에서는 '오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환'하는 작업을 반복한다. 오른쪽부터 왼쪽으로 숫자를 옮겨가는 모양이 물속에서 거품이 올라오는 모양과 비슷하다고 해 버블이라고 한다고 한다.

 

1

5	9	3	1	2	8	4	7	6 // 이 경우 7과 6을 비교
							---------

수열의 오른쪽 끝에 저울을 두고 저울의 좌우에 있는 숫자를 비교한다. 비교한 결과, 오른쪽 숫자가 작으면 왼쪽과 바꾼다. 6 < 7 이므로 좌우의 숫자를 교체한다.

5	9	3	1	2	8	4	6	7
							---------

 

2

비교를 완료했으면 저울을 한 칸 왼쪽으로 옮겨서 같은 방법으로 숫자를 비교한다.

5	9	3	1	2	8	4	6	7
						---------

이번에는 4 < 6 이므로 숫자를 교체하지 않는다.

 

3

저울을 한 칸 왼쪽으로 옮긴다. 같은 작업을 저울이 왼쪽 끝에 도착할 때까지 반복한다.

5	9	3	1	2	8	4	6	7
					---------

8 > 4 이므로 숫자를 교체.

5	9	3	1	2	4	8	6	7
					---------

 

4

1	5	9	3	2	4	8	6	7
---------

숫자 교체를 반복하면서 저울이 왼쪽 끝에 도착했다. 일련의 작업으로 수열 중에서 가장 작은 숫자가 왼쪽 끝으로 이동했다.

 

5

왼쪽 끝의 숫자는 정렬을 끝낸 것으로 간주하고, 저울을 다시 오른쪽 끝으로 옮긴다. 저울이 왼쪽 끝에서 두 번째에 도착할 때까지 앞의 작업을 반복한다.

1	5	9	3	2	4	8	6	7
							---------

6 < 7 이므로 교체 X

 

6

저울이 왼쪽 끝에서 두 번째에 도착했다. 수열 중에서 두 번째로 작은 숫자가 두 번째 위치로 이동됐다.

1	2	5	9	3	4	6	8	7
	---------

 

7

저울을 다시 오른쪽 끝으로 옮긴다. 같은 방법으로 모든 숫자가 정렬될 때까지 반복한다.

1	2	3	4	5	6	7	8	9
							---------

정렬이 완료되었다.

 

버블 소트는 1라운드에서 n-1회, 2라운드에서 n-2회, .... n-1라운드에서 1회를 비교한다. 이 때문에 비교 횟수는 입력 데이터의 순서와 상관없이 일정하다. 숫자의 교체 횟수는 입력 데이터에 의존한다. 극단적인 경우, 입력 데이터가 우연히 작은 순으로 나열돼 있을 때는 교체가 한 번도 발생하지 않는다. 반대로 숫자가 큰 순대로 나열돼 있으면 비교할 때마다 교체해 주어야 한다. 따라서 버블 정렬의 계산 시간은 O(n2)가 된다.

 

참고 서적: