알고리즘 : 버블정렬(Bubble Sort)

버블정렬(Bubble Sort) 이란?

버블 정렬은 정렬 알고리즘 중 가장 기본적인 정렬 알고리즘으로 서로 인접한 두 원소를 비교하여 정렬하는 방식입니다. 큰 값이 마치 거품처럼 한 칸씩 오른쪽으로 이동하면서 정렬되어 버블 정렬이라고 불립니다.

 

버블정렬은 구현이 매우 단순하고 이해하기 쉽고, 정렬하는 과정이 시각적으로 이해하기 쉽습니다.

그러나 시간 복잡도가 O(n²)로 효율성이 떨어지며, 배열의 크기가 커질수록 성능이 급격히 저하되는 단점을 가지고 있습니다.

function bubbleSort(array) {
    for (let i = 0; i < array.length; i++) { // O(n)
        for (let j = 1; j < array.length; j++) { // O(n)
            if (array[j - 1] > array[j]) {
            const temp = array[j-1]
            array[j-1] = array[j]
            array[j] = temp
        }
    }
}

bubbleSort([5,4,3,2,1])

 

만약 [5,4,3,2,1] 이라는 배열을 정렬시킨다고 가정했을 때 다음과 같은 과정을 진행하게 됩니다.

 

1. i=0일 때 (첫 번째 순회)

• j=1: [5,4,3,2,1] → [4,5,3,2,1] (5와 4 비교 후 교환)
• j=2: [4,5,3,2,1] → [4,3,5,2,1] (5와 3 비교 후 교환)
• j=3: [4,3,5,2,1] → [4,3,2,5,1] (5와 2 비교 후 교환)
• j=4: [4,3,2,5,1] → [4,3,2,1,5] (5와 1 비교 후 교환)

2. i=1일 때 (두 번째 순회)

• j=1: [4,3,2,1,5] → [3,4,2,1,5] (4와 3 비교 후 교환)
• j=2: [3,4,2,1,5] → [3,2,4,1,5] (4와 2 비교 후 교환)
• j=3: [3,2,4,1,5] → [3,2,1,4,5] (4와 1 비교 후 교환)
• j=4: [3,2,1,4,5] (4와 5 비교, 교환 없음)

3. i=2일 때 (세 번째 순회)

• j=1: [3,2,1,4,5] → [2,3,1,4,5] (3과 2 비교 후 교환)
• j=2: [2,3,1,4,5] → [2,1,3,4,5] (3과 1 비교 후 교환)
• j=3,4: [2,1,3,4,5] (변화 없음)

4. i=3일 때 (네 번째 순회)

• j=1: [2,1,3,4,5] → [1,2,3,4,5] (2와 1 비교 후 교환)
• j=2,3,4: [1,2,3,4,5] (변화 없음)

5. i=4일 때 (마지막 순회)

• j=1,2,3,4: [1,2,3,4,5] (이미 정렬되어 있어 변화 없음)

최종 결과: [1,2,3,4,5]

 

위와 같은 과정을 통해 배열의 요소를 정렬시키게 됩니다.