정렬 알고리즘 (2) - 버블 정렬

강의: 구름에듀 "안경잡이개발자가 알려주는 실전 알고리즘 강좌"
링크: 안경잡이개발자가 알려주는 실전 알고리즘 강좌
(강의는 알고리즘 풀이를 C/C++ 언어로 진행합니다.)

내용 정리 출처: [JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기 (Bubble Sort, Insertion Sort, Selection Sort in JavaScript)

정렬 알고리즘

대체로 알고리즘을 공부할 때 가장 먼저 나오는 개념이 정렬 알고리즘인 이유는 효율성의 차이를 가장 극명하게 보여주기 때문

버블 정렬

옆에 있는 값과 비교하여 더 작은 값을 앞으로 보내는 알고리즘

의사코드를 작성한다면?

인덱스가 0인 요소와 인덱스가 1인 요소를 비교하여 더 작은 값을 앞으로 보낸다.
인덱스가 1인 요소와 인덱스가 2인 요소를 비교하여 더 작은 값을 앞으로 보낸다.
...
인덱스가 8인 요소와 인덱스가 9인 요소를 비교하여 더 작은 값을 앞으로 보낸다.
(-> 가장 큰 수가 가장 뒤로 이동, 즉 인덱스가 9인 요소는 건들필요 없음)
인덱스가 0인 요소와 인덱스가 1인 요소를 비교하여 더 작은 값을 앞으로 보낸다.
인덱스가 1인 요소와 인덱스가 2인 요소를 비교하여 더 작은 값을 앞으로 보낸다.
...
인덱스가 7인 요소와 인덱스가 8인 요소를 비교하여 더 작은 값을 앞으로 보낸다.
(-> 가장 큰 수가 가장 뒤로 이동, 즉 인덱스가 8인 요소는 건들필요 없음)
마지막까지 반복,,,

코드로 작성한다면?

function swap (i, j, arr) {
    const temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

function solution (arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(j, j + 1, arr);
            }
        }
    }
    
    return arr;
}

console.log(solution(arr1));

여기서 불필요한 비교를 줄이기!
i 변수를 가진 for문이 실행되고 그 안에 j 변수를 가진 for문이 실행될 때,
만약 j 변수를 가진 for 문에서 한번도 swap 함수가 호출이 안됐다면 이미 정렬되어 있음을 알 수 있다.

function swap (i, j, arr) {
    const temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

function solution (arr) {
    for (let i = 0; i < arr.length; i++) {
        // swap 함수가 호출됐는지 안됐는지 확인하는 조건
        let isSwapped = false;

        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                isSwapped = true;
                swap(j, j + 1, arr);
            }
        }

        // 만약 swap 함수가 호출되지 않았다면 for문 중지
        if (!isSwapped) {
            break;
        }
    }
    
    return arr;
}

console.log(solution(arr1));

시간 복잡도

BigO

• Worst Case(정렬이 하나도 안되어있는 경우): O(N^2)
• Best Case(이미 정렬이 되어있는 경우): O(N)

장점

• 버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약
• 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용 가능
• 버블 정렬은 중복 데이터가 있을 경우 데이터의 위치를 교환하지 않고 지나가기 때문에 stable한 정렬

단점

• 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점