출처: Wikipedia

버블 정렬은 서로 인접한 두 개의 요소를 차례로 비교해가며 정렬이 필요한 경우 두 개의 요소를 스왑(서로의 위치를 변경)하는 형태로 정렬을 해나갑니다.

이렇게 순환과정에서 두개씩 비교해 나가는 모습이 거품과 같다고 하여 버블 정렬이라는 이름을 가지게 되었습니다.

직관적이며 구현이 쉽다는 장점은 있지만 그만큼 정렬 알고리즘 중 성능이 낮은편에 속합니다.

구현

아래 로직은 오름차순 정렬을 기준으로 작성하였습니다.

// 오름차순 기준 정렬
function bubbleSort(arr) {
    const n = arr.length;
    let temp;
    
    for(let i = 0; i < n-1; i++) {
		let swapped = false;

        // -i를 하는 이유는 최대값부터 정렬되기 때문에 이미 정렬이 완료된 요소에 접근 할 필요 X
        for(let j = 0; j < n-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;

                // 구조 분해 할당을 활용한 swap도 가능하다.
                // [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
        // swap이 한번도 일어나지 않았다는 건 이미 정렬된 상태라는것이므로 함수 종료
        if (!swapped) return arr;
    }
    
    return arr;
}

console.log(bubbleSort([5, 2, 4, 1, 3]));

JS에서는 구조분해할당을 활용해 값을 swap할 수 있으며
만약, 구조분해할당이 불가능한 환경이라면 위 코드처럼 값을 임시적으로 저장하기 위한 temp 변수를 선언해 값을 교체합니다.

버블 정렬은 최선의 경우 Ω(n), 평균과 최악은O(n^2)의 시간 복잡도를 가지며
최선의 경우는 이미 정렬이 완료된 상태인 경우로 위 로직에서 swapped 변수에 의해 바로 리턴 처리됩니다.