Bubble Sort(버블 정렬)

버블 정렬은 인접한 두 개의 요소를 비교하고 필요한 경우에 위치를 교환하여 정렬을 수행하는 정렬 알고리즘이다.

1. Bubble Sort(버블 정렬) 문제

예제를 통해서 버블 정렬을 한 번 알아보자

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하라.

1 10 5 8 7 6 4 3 2 9

2. Bubble Sort(버블 정렬) 풀이

지난 번에는 선택 정렬로 풀어봤던 문제를 버블 정렬로 풀어보자

바로 옆에 있는 값과 비교하여 더 작은 값을 앞으로 보낸다

이 과정을 반복한다

1 10 5 8 7 6 4 3 2 9 의 원본 배열이 있을 때

인접한 두 요소를 비교하여 자리를 바꾼다

(1 10) 5 8 7 6 4 3 2 9 - 숫자가 더 큰 10 오른쪽에 있으므로 그대로 둔다

1 (5 10) 8 7 6 4 3 2 9 - 10과 5중 10이 더 크므로 10을 오른쪽으로 이동한다

이 과정을 반복한다

1 5 (8 10) 7 6 4 3 2 9

1 5 8 (7 10) 6 4 3 2 9
1 5 8 7 (6 10) 4 3 2 9
1 5 8 7 6 (4 10) 3 2 9
1 5 8 7 6 4 (3 10) 2 9
1 5 8 7 6 4 3 (2 10) 9
1 5 8 7 6 4 3 2 (9 10)

1 5 8 7 6 4 3 2 9 10

가장 숫자가 큰 10을 왼쪽으로 보냈으니, 이제 10을 제외한 나머지를 반복해준다 - 한번의 반복을 했을 때 가장 큰값이 맨 뒤로 이동

// 다음의 배열을 오름차순으로 정렬하시오
const arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];

// 현재의 요소와 바꿀 수 있는 변수 temp
let temp;

for (let i = 0; i < arr.length; i++) {
	for (let j = 0; j < 9 - i; j++) {
		// 왼쪽 요소가 오른쪽 요소보다 클 경우
		if (arr[j] > arr[j + 1]) {
			// 두 요소의 자리를 바꾼다
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
}

console.log(arr);

3. Bubble Sort(버블 정렬)의 효율성

구현하기에는 간단하지만, 가장 효율성이 떨어진다

선택정렬과 같이 10 + 9 + 8 + ... + 1 번의 연산이 필요하다

선택정렬의 경우에는 운이 좋으면 연산의 횟수를 줄일 수 있으나,

버블정렬의 경우 모든 요소를 비교하므로 선택 정렬보다 비효율적이라고 할 수 있다

이를 수식으로 표현하면, n(n + 1)/2 번의 비교연산을 해야한다

따라서 O(n^2)의 수행시간을 가진다

참고자료

동빈나 유튜브
https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz