JavaScript 버블 정렬(Bubble Sort)로 배열 정렬하는 방법

버블 정렬은 가장 기본적인 정렬 알고리즘 중 하나로, 인접한 두 요소를 반복적으로 비교하면서 순서가 잘못된 경우 서로 교환(swap)하는 방식으로 배열을 오름차순 또는 내림차순으로 정렬합니다.

이번 글에서는 리터럴 값으로 이루어진 배열을 입력받아 버블 정렬을 사용해 정렬하는 JavaScript 함수를 작성해 보겠습니다.

구현 코드

먼저 두 요소의 위치를 바꾸는 swap 헬퍼 함수를 만들고, 이를 활용해 bubbleSort 함수를 구현합니다.

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));

코드 설명

1. swap 함수

swap 함수는 임시 변수 temp를 활용해 배열 내 두 인덱스의 값을 안전하게 교환합니다. 자바스크립트에서는 구조 분해 할당을 사용해 [a, b] = [b, a] 형태로 더 간결하게 작성할 수도 있습니다.

2. bubbleSort 함수

바깥쪽 루프는 배열의 끝부터 시작까지 순회하고, 안쪽 루프는 인접한 두 요소를 비교합니다. 앞의 값이 뒤의 값보다 크면(내림차순 비교 조건) 두 요소를 교환하여 큰 값이 점점 뒤로 밀려나도록 합니다. 모든 순회가 끝나면 정렬된 배열이 반환됩니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[
    2, 4, 4, 4, 7,
    8, 8, 8, 23, 23,
    45, 56
]

입력 배열이 성공적으로 오름차순으로 정렬된 것을 확인할 수 있습니다.

성능 참고 사항

버블 정렬의 시간 복잡도는 최악 및 평균 경우 O(n²), 최선의 경우(이미 정렬된 배열) O(n)입니다. 학습 목적에는 적합하지만, 실제 프로덕션 환경에서는 내장 메서드인 Array.prototype.sort()를 사용하거나 퀵 정렬, 병합 정렬 같은 더 효율적인 알고리즘(O(n log n))을 활용하는 것이 좋습니다.