코딩테스트의 필수 알고리즘, 버블 소트에 대해 알아보겠습니다.
1. 문제 정의
배열을 입력받아 해당 배열을 오름차순으로 정렬하는 버블 소트(Bubble Sort) 알고리즘을 구현하시오.
버블 소트는 인접한 두 원소를 비교하여 정렬하는 방식으로 작동하며, 가장 큰 원소가 배열의 끝으로 이동하는 과정을 반복합니다.
입력 형식
입력은 정수 배열이며, 배열의 길이는 1 이상 1000 이하입니다. 각 원소는 -10,000 이상 10,000 이하의 값을 가질 수 있습니다.
출력 형식
오름차순으로 정렬된 배열을 반환합니다.
2. 문제 접근법
버블 소트는 매우 직관적인 정렬 알고리즘입니다. 기본적인 접근법은 두 개의 인접한 요소를 비교하고,
정렬되어 있지 않다면 교환하여 배열에서 반복적으로 정렬을 수행하는 것입니다. 이 과정은 배열의 크기만큼 반복되며,
더 이상 교환이 발생하지 않을 때까지 계속 진행됩니다. 이렇게 하면 각 단계에서 가장 큰 값이 배열의 끝으로 이동하게 됩니다.
2.1. 알고리즘 단계
- 배열의 길이를 구합니다.
- 두 개의 인덱스를 사용하여 배열의 요소를 비교합니다.
- 인접한 요소가 정렬되지 않았다면 교환합니다.
- 한 번의 전체 순회에서 교환이 발생하지 않으면 정렬이 완료된 것으로 간주합니다.
- 위 과정을 반복하여 최종적으로 오름차순으로 정렬된 배열을 반환합니다.
3. 버블 소트 코드 구현
이제 위의 알고리즘을 자바스크립트로 구현해 보겠습니다. 기본적인 버블 소트 함수는 다음과 같습니다.
// 버블 소트 함수 구현
function bubbleSort(arr) {
let n = arr.length; // 배열의 길이를 저장
// 배열을 반복하여 정렬
for (let i = 0; i < n - 1; i++) {
let swapped = false; // 교환 여부를 확인할 변수
// 인접한 요소 비교 및 교환
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 교환
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 교환이 발생했음을 기록
}
}
// 더 이상 교환이 발생하지 않으면 종료
if (!swapped) break;
}
return arr; // 정렬된 배열 반환
}
// 테스트
let testArray = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(testArray)); // [11, 12, 22, 25, 34, 64, 90]
4. 시간 복잡도 분석
버블 소트 알고리즘의 시간 복잡도는 최악의 경우 O(n²)입니다. 이는 두 개의 중첩 루프가 각각 배열의 길이에 비례하기 때문입니다.
최선의 경우(이미 정렬된 배열)는 O(n)입니다. 이 경우는 교환이 발생하지 않아 첫 단계에서 바로 종료됩니다.
버블 소트는 일반적으로 비효율적이며, 실무에서 큰 데이터셋을 정렬할 때는 다른 알고리즘(예: 퀵 소트, 병합 정렬 등)을 사용하는 것이 좋습니다.
4.1. 공간 복잡도
버블 소트의 공간 복잡도는 O(1)입니다. 불필요한 추가 메모리를 사용하는 것이 아니고,
주어진 배열 내에서 정렬을 수행하기 때문입니다.
5. 버블 소트의 장단점
장점
- 알고리즘이 간단해 이해하기 쉽다.
- 자체적인 요구사항이 없어 추가적인 메모리 관리가 필요 없다.
- 소규모 데이터셋에 대해서는 효과적으로 작동한다.
단점
- 시간 복잡도가 비효율적이다 (O(n²)).
- 정렬이 잘 되어 있는 경우에도 전체 반복을 수행해야 하므로 효율성이 떨어진다.
- 대량의 데이터셋을 정렬할 때는 비효율적이다.
6. 결론
이번 강좌에서는 자바스크립트를 사용하여 버블 소트 알고리즘을 구현해 보았습니다.
버블 소트는 그 구조적 단순성 덕분에 교육적 목적에서는 유용하지만, 실제 프로덕션 환경에서는 다른 더 효율적인 알고리즘을 사용하는 것이 바람직합니다.
앞으로 더 복잡한 알고리즘과 데이터 구조에 대해 탐구하면서 코딩 능력을 한층 더 발전시킬 수 있길 바랍니다.