오늘은 자바스크립트에서 가장 기초적인 정렬 알고리즘 중 하나인 버블 정렬(Bubble Sort)에 대해 알아보겠습니다. 버블 정렬은 간단하지만 비효율적인 정렬 알고리즘으로, 주로 교육적인 목적이나 알고리즘의 기초를 배우기 위해 사용됩니다.
버블 정렬 개요
버블 정렬은 주어진 리스트를 반복적으로 탐색하면서, 인접한 두 요소를 비교하고 그 순서를 바꾸는 방식으로 작동합니다. 이 과정은 리스트가 정렬되었다고 판단될 때까지 계속 진행됩니다. 최악의 경우 시간 복잡도는 O(n^2)입니다.
작동 원리
버블 정렬의 기본적인 작동 방식은 다음과 같습니다:
- 리스트의 첫 번째 요소부터 시작하여 두 개의 인접한 요소를 비교합니다.
- 왼쪽 요소가 오른쪽 요소보다 크다면, 두 요소의 위치를 바꿉니다.
- 리스트의 끝까지 이 과정을 반복합니다. 이 과정을 한 번 수행하면 가장 큰 요소가 마지막으로 이동하게 됩니다.
- 위 과정(1-3)을 남은 요소에 대해 반복합니다.
문제 정의
문제 설명
배열 arr가 주어집니다. 이 배열을 버블 정렬 알고리즘을 사용하여 오름차순으로 정렬한 후, 정렬된 배열을 반환하는 함수를 작성하세요.
입력 예시
arr = [64, 34, 25, 12, 22, 11, 90]출력 예시
[11, 12, 22, 25, 34, 64, 90]문제 풀이 과정
1단계: 함수 정의
먼저 버블 정렬을 수행할 함수를 정의합니다. 함수 이름은 bubbleSort로 하겠습니다. 입력으로는 배열을 받도록 합니다.
2단계: 이중 반복문 사용
버블 정렬은 이중 반복문을 사용하여 구현합니다. 외부 반복문은 배열의 마지막 요소까지 진행하고, 내부 반복문은 두 인접한 요소를 비교하여 정렬합니다.
3단계: 요소 비교 및 교환 로직 구현
내부 반복문에서 인접한 두 요소를 비교하고, 그 순서를 바꿉니다. 이를 위해 간단한 조건문을 사용합니다.
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 요소 교환
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}4단계: 유틸리티 함수 추가 (선택 사항)
정렬된 결과를 확인하기 위해 배열을 출력하는 유틸리티 함수를 작성할 수 있습니다. 간단한 console.log를 활용하여 결과를 확인할 수 있습니다.
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]버블 정렬의 시간복잡도
버블 정렬의 시간복잡도는 최악의 경우 O(n^2)입니다. 이는 전체 배열을 두 번 반복하기 때문입니다. 최선의 경우 (이미 정렬된 경우)에도 O(n)이지만, 일반적으로는 비효율적입니다.
공간 복잡도는 O(1)로, 추가로 사용하는 메모리가 상수이기 때문에 효율적입니다.
버블 정렬의 의미와 활용
버블 정렬은 그 단순한 구현 덕분에 알고리즘을 배우는 데에 적합합니다. 하지만 실제 산업 현장에서는 그 성능이 비교적 떨어져, 다른 정렬 알고리즘이 선호됩니다. 하지만 알고리즘 공부를 하면서 이해할 수 있는 중요한 기본 개념입니다.
결론
이번 글에서는 자바스크립트로 버블 정렬을 구현하는 방법에 대해 배웠습니다. 기초적인 정렬 알고리즘을 이해하고, 이를 통해 더 복잡한 알고리즘을 배우는 발판을 마련할 수 있기를 바랍니다. 질문이나 필요한 추가 정보가 있다면 댓글로 남겨주세요!