버블 정렬(Bubble Sort)은 가장 기본적인 정렬 알고리즘 중 하나로, 인접한 두 요소를 반복적으로 비교하고 순서가 올바르지 않으면 서로 교환하는 방식으로 동작합니다. 이 과정을 배열 전체에 대해 반복하면 큰 값이 거품이 떠오르듯 배열의 끝으로 밀려나게 되어 '버블' 정렬이라는 이름이 붙었습니다.
이번 글에서는 리터럴 값으로 이루어진 배열을 입력받아 버블 정렬 방식으로 오름차순 정렬하는 자바스크립트 함수를 작성해 보겠습니다.
버블 정렬의 동작 원리
- 배열의 처음부터 인접한 두 요소를 차례대로 비교합니다.
- 앞의 요소가 뒤의 요소보다 크면(오름차순 기준) 두 요소의 위치를 서로 교환(swap)합니다.
- 한 번의 순회가 끝나면 가장 큰 값이 배열의 맨 끝에 위치하게 됩니다.
- 정렬이 완료될 때까지 이 과정을 반복합니다.
예제 코드
그럼 실제 코드를 작성해 보겠습니다.
const arr = [4, 56, 4, 23, 8, 4, 23, 2, 7, 8, 8, 45];
// 두 요소의 위치를 교환하는 헬퍼 함수
const swap = (items, firstIndex, secondIndex) => {
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
};
// 버블 정렬 구현
const bubbleSort = items => {
var len = items.length,
i, j;
for (i = len - 1; i >= 0; i--) {
for (j = len - i; j >= 0; j--) {
if (items[j] < items[j - 1]) {
swap(items, j, j - 1);
}
}
}
return items;
};
console.log(bubbleSort(arr));
코드 설명
- swap 함수: 임시 변수(temp)를 활용해 배열 내 두 위치의 값을 서로 바꿉니다.
- bubbleSort 함수: 이중 for문으로 배열을 순회하며 인접한 요소(items[j]와 items[j-1])를 비교하고, 순서가 잘못된 경우 swap 함수를 호출해 교환합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ 2, 4, 4, 4, 7, 8, 8, 8, 23, 23, 45, 56 ]
마무리 및 참고 사항
버블 정렬은 구현이 매우 간단하지만 시간 복잡도가 O(n²)로 비효율적이기 때문에 대규모 데이터에는 적합하지 않습니다. 주로 알고리즘 학습이나 소규모 데이터 정렬에 활용되며, 실무에서는 퀵 정렬, 병합 정렬 등 더 효율적인 정렬 알고리즘이 일반적으로 사용됩니다.