거품 정렬 구현해보기(Bubble Sort)

거품 정렬이란?

서로 인접한 두 원소를 비교하면서 정렬하는 알고리즘

평균 시간 복잡도

O(n^2)

장점

인접한 값에 대해서 계속 비교하는 방식이기에 구현이 쉬우며, 코드가 직관적입니다.

N개 원소에 대해 원소를 하나씩 비교하기에 정밀 비교가 가능하다.

배열 내에서 교환하는 방식(제자리 정렬, In-place Sort)이므로 다른 메모리 공간을 필요로 하지 않는다.

중복된 원소의 순서가 정렬 후에도 유지되므로 stable 하다.

단점

시간 복잡도가 O(n^2) 이기에 정렬하기에 너무 느린 속도를 가지고 있다.

정렬이 되어있지 않은 원소를 정렬하기 위해서 교환 연산(swap)이 많이 일어난다.

동작 방식

1. 인접한 값 비교 ⇒ 큰 값 교환
2. index를 N 반복
3. N 차례가 N - 1

class BubbleSort {
    sort(data) {
        let len = data.length;
        for (let i = 0; i < len; i++) {
            for (let j = 0; j < len - i; j++) {
                if (data[j] > data[j + 1]) {
                    // js ES6 구조 분해 할당 구문
                    [data[j], data[j + 1]] =[data[j + 1], data[j]];
                }
            }
        }
        return data;
    }
}