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

버블정렬의 원리와 특징 및 성능에 대해서 정리하는 글이다.

<학습 목표>

• 버블정렬의 원리를 이해한다.
• 버블정렬의 특징을 파악한다.
• 버블정렬의 성능을 기억한다.
• 모든 과정을 설명할 수 있다.
• 버블정렬을 프로그래밍 언어로 구현할 수 있다.

버블정렬의 원리

• 모든 인접한 값의 비교를 위해 왼쪽 또는 오른쪽에서 시작하여 반대편 끝으로 이동
• 인접한 두 값을 비교하여 왼쪽 값이 더 큰 경우 자리를 바꾸는 과정을 반복

버블정렬의 정렬 과정

• 가장 오른쪽 값(최댓값)부터 왼쪽 방향(최솟값 방향)으로 정렬되는 과정을 설명
• 비교연산의 기준이 되는 시작하는 위치는 가장 끝에서 가장 끝 바로 하나 전의 위치까지, 진행 방향으로 1씩 이동

배열의 크기 = n = 5

[5, 3, 4, 2, 1] 

1. 첫번째 원소부터 n-1번째 원소까지 순회(4회)하며 오른쪽 원소와 비교를 수행한다

• (0번째, 1번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (1번째, 2번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (2번째, 3번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (3번째, 4번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (4(n-1)번째, 5번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.

결과 : n번째 값(5) 정렬

[3, 4, 2, 1, 5] 

2. 첫번째 원소부터 n-2번째 원소까지 순회(3회)하며 오른쪽 원소와 비교를 수행한다

• (0번째, 1번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (1번째, 2번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (2번째, 3번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (3(n-2)번째, 4번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.

결과 : n, n-1번째 값(4, 5) 정렬

[3, 2, 1, 4, 5] 

3. 첫번째 원소부터 n-3번째 원소까지 순회(2회)하며 오른쪽 원소와 비교를 수행한다

• (0번째, 1번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (1번째, 2번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (2(n-3)번째, 3번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.

결과 : n, n-1, n-2번째 값(3, 4, 5) 정렬

[2, 1, 3, 4, 5] 

4. 첫번째 원소부터 n-4번째 원소까지 순회(1회)하며 오른쪽 원소와 비교를 수행한다

• (0번째, 1번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.
• (1(n-4)번째, 2번째)값을 비교하여 왼쪽 값이 더 클 경우 교환한다.

결과 : n, n-1, n-2번째 값(2, 3, 4, 5) 정렬

[1, 2, 3, 4, 5] 

Source Code

n = len(array) 

for i in range(n - 1, 0, -1):
	for j in range(i):
		if array[j] > array[j+1]:
			array[j], array[j+1] = array[j+1], array[j]

버블정렬의 성능

• 비교 횟수는 최선, 평균, 최악의 경우 모두 동일하므로 일정하다.
• 교환 횟수는 배열의 데이터가 정렬되지 않았을 경우 많아진다.
• 외부 루프에서 n-1번, 내부 루프에서 n-1, n-2, …, 2, 1번의 비교가 일어난다.

입력 크기 n에 대한 버블 정렬 알고리즘은 이중 루프로 구성되며, 바깥 루프는 i=0, …, (n-2)까지 (n-1)번 수행하면서, 안쪽 루프 j에 대해서는 i=0일 때(n-1)번의 인접한 두 값의 비교가 수행되고, i=1일때 (n-2)번 비교, i=2일때는 (n-3)번 비교, …, i=(n-2)일 때 1번의 비교를 수행한다. 따라서 총비교횟수는 (n-1)+(n-2)+(n-3)+…+2+1 = n(n-1)/2이므로, 버블정렬 알고리즘의 시간복잡도는 $O(n^2)$이 된다.

버블정렬의 특징

• 비교 기반의 정렬이다.
• 안정적 정렬이다.

안정적 정렬이란, 동일한 값을 갖는 데이터가 여러 개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지됨을 의미한다. 안정적이지 않은 정렬의 경우, 동일한 값의 두 데이터가 서로 교환되는 경우가 발생하지만 버블정렬은 교환이 발생하지 않는다.

• 제자리 정렬이다.

제자리 정렬은 정렬되는 항목 외에 $O(1)$개의 메모리만 필요하며 $O(log(n))$개의 추가적인 메모리를 인플레이스로 간주한다. 버블 정렬은 주어진 공간 외에 추가적인 공간을 사용하지 않는 정렬이다.

버블정렬의 성능 개선

데이터가 이미 정렬된 상태일 때는 교환이 일어나지 않기 때문에, 교환이 한번도 일어나지 않는 경우 이후의 작업을 수행하지 않고 종료할 수 있도록 개선할 수 있다.

개선된 코드

for i in range(n - 1, 0, -1):
	
	check_exchanged = False #교환여부
	for j in range(i):
		if array[j] > array[j+1]:
			array[j], array[j+1] = array[j+1], array[j]
			
			check_exchanged = True

	if not check_exchanged:
		break

ps. 공부한것을 직접 작성하느라 오류가 있을 수 있으니 이상한 점이 있거나 의견이 있으시다면 코멘트 해주세요!