버블정렬
거품 정렬 또는 버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.
JavaScript 거품 정렬 구현
function bubbleSort(arr) {
for (let i = 0 ; i < arr.length; i++) {
for (let j = 1; j < arr.length - i; j++) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; // 스왑
}
}
}
return arr;
}
bubbleSort([5, 3, 2, 4, 1]);
동작 순서
| i | j | arr[j] | j-1 | arr[j-1] | arr | 비고 |
|---|---|---|---|---|---|---|
| 0 | 1 | 3 | 0 | 5 | [3, 5, 4, 2, 1] | |
| 0 | 2 | 4 | 1 | 5 | [3, 4, 5, 2, 1] | |
| 0 | 3 | 2 | 2 | 5 | [3, 4, 2, 5, 1] | |
| 0 | 4 | 2 | 3 | 5 | [3, 4, 2, 1, 5] | 제일 큰 수 5 고정 |
| 1 | 1 | 4 | 0 | 3 | [3, 4, 2, 1, 5] | |
| 1 | 2 | 2 | 1 | 4 | [3, 2, 4, 1, 5] | |
| 1 | 3 | 1 | 2 | 4 | [3, 2, 1, 4, 5] | 그 다음 큰 수 4 고정 |
| 2 | 1 | 2 | 0 | 3 | [2, 3, 1, 4, 5] | |
| 2 | 2 | 2 | 1 | 3 | [2, 1, 3, 4, 5] | 그 다음 큰 수 3 고정 |
| 3 | 1 | 2 | 0 | 1 | [1, 2, 3, 4, 5] | 남은 두 수 비교해서 정렬 |
특징
- 구현이 매우 간단하다는 장점이 있음
- 인접한 요소와 계속 비교해야하므로 연산 시간이 오래 걸림
- 이미 정렬이 완료되었다 하더라도 계속 비교 작업이 일어남
개선 방법
정렬이 한번도 일어나지 않았다면 이미 정렬이 완료되었다는 뜻이므로 작업을 끝냄
개선 전 코드
처음부터 정렬되어 있는 배열을 정렬 시도했지만 무지성으로 정렬을 반복한다
function bubbleSort(arr) {
for (let i = 0 ; i < arr.length; i++) {
for (let j = 1; j < arr.length - i; j++) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; // 스왑
}
console.log(i, j, arr);
}
}
return arr;
}
bubbleSort([1, 2, 3, 4, 5]);
/**
0 1 [ 1, 2, 3, 4, 5 ]
0 2 [ 1, 2, 3, 4, 5 ]
0 3 [ 1, 2, 3, 4, 5 ]
0 4 [ 1, 2, 3, 4, 5 ]
1 1 [ 1, 2, 3, 4, 5 ]
1 2 [ 1, 2, 3, 4, 5 ]
1 3 [ 1, 2, 3, 4, 5 ]
2 1 [ 1, 2, 3, 4, 5 ]
2 2 [ 1, 2, 3, 4, 5 ]
3 1 [ 1, 2, 3, 4, 5 ]
* /
개선 후 코드
반복문을 도는 횟수가 한번으로 최소화 됨
function bubbleSort(arr) {
for (let i = 0 ; i < arr.length; i++) {
let cnt = 0;
for (let j = 1; j < arr.length - i; j++) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
cnt++; // 스왑이 일어난 횟수 셈
}
console.log(i, j, arr);
}
if (cnt === 0) return arr; // 한 번도 스왑이 일어나지 않았다면 이미 정렬이 완료된 것
}
return arr;
}
bubbleSort([1, 2, 3, 4, 5]);
/**
0 1 [ 1, 2, 3, 4, 5 ]
0 2 [ 1, 2, 3, 4, 5 ]
0 3 [ 1, 2, 3, 4, 5 ]
0 4 [ 1, 2, 3, 4, 5 ]
* /