버블 정렬(Bubble Sort)

특징

• '붙어있는 두 개의 데이터를 비교해서 크기가 순서대로가 아니면 바꾼다'는 아이디어에서 시작된 알고리즘입니다.
• 가장 앞에서 뒤로 비교-교환을 수행하면 큰 숫자가 오른쪽으로 이동하는 모습을 볼 수 있습니다. 이 모습이 수면 위로 거품이 올라오는 것과 흡사해서 버블(거품)정렬이라 불립니다.
• 선택 정렬과 마찬가지로 데이터를 비교-교환하며 정렬되기 때문에 비교 정렬로 분류됩니다.

효율

• 시간복잡도 - O(N²)
  • 선택 정렬과 시간복잡도는 같지만, 실제 수행 시간이 더 깁니다. 이는 선택 정렬에 비해 교환(swap)이 더 자주 수행되기 때문입니다. 이때문에 정렬 알고리즘 중 가장 비효율적이라고 평가됩니다.
  • 최선, 평균, 최악의 경우 모두 시간 복잡도가 동일합니다(무조건 2개의 데이터를 비교하므로).
• 공간복잡도 - O(N)

구현

function bubbleSort(input) {
    for (let i = 0; i < input.length - 1; i++) {
        let j = 1;
        while (j < input.length) {
            // 인접한 두 데이터가 순차적이지 않다면 교환(swap)
            if (input[j - 1] > input[j]) {
                let temp = input[j - 1];
                input[j - 1] = input[j];
                input[j] = temp;
                console.log(...input);
            }
            j++;
        }
    }
}

let sample = [7, 3, 2, 8, 9, 4, 6, 1, 5];
bubbleSort(sample);
/* 정렬 과정 출력
3 7 2 8 9 4 6 1 5
3 2 7 8 9 4 6 1 5
3 2 7 8 4 9 6 1 5
3 2 7 8 4 6 9 1 5
3 2 7 8 4 6 1 9 5
3 2 7 8 4 6 1 5 9
2 3 7 8 4 6 1 5 9
2 3 7 4 8 6 1 5 9
2 3 7 4 6 8 1 5 9
2 3 7 4 6 1 8 5 9
2 3 7 4 6 1 5 8 9
2 3 4 7 6 1 5 8 9
2 3 4 6 7 1 5 8 9
2 3 4 6 1 7 5 8 9
2 3 4 6 1 5 7 8 9
2 3 4 1 6 5 7 8 9
2 3 4 1 5 6 7 8 9
2 3 1 4 5 6 7 8 9
2 1 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
*/

 

구현은 선택 정렬보다 쉽지만 교환이 더 자주 수행되서 효율이 떨어져 보입니다.