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

정렬이란?

정렬이란 컬렉션(ex: 배열)의 항목을 재배열하는 과정을 의미합니다.

 

왜 배워야 하나?

• 정렬은 프로그래밍에서 매우 흔하게 사용됩니다.
• 데이터를 정렬할 수 있는 방법은 많고, 각각 장단점이 있습니다.
• 특정 상황에서 더 빠른 알고리즘이 있습니다.

 

목표

• 버블 정렬
• 선택 정렬
• 삽입 정렬

 

기본 내장 JS 정렬

array 내장 sort

MDN을 살펴보면 문자열은 A, B, C, D 순으로 나오지만 숫자는 오름차순이 아닌 것을 알 수 있습니다. 그 이유는 기본 정렬 순서가 문자열 유니코드에 따르기 때문입니다.

하지만 정렬 방식, 정렬의 기준이 되는 속성, 비교 대상을 실제로 지정할 수 있다면 다른 결과를 낼 수 있습니다.

 

버블 정렬 개요

버블 정렬의 개념은 예를 들어 배열을 오름차순으로 정렬한다면, 더 큰 숫자가 한 번에 하나씩 뒤로 이동한다는 것입니다.

예시:

[5, 3, 4, 1, 2]
[3, 5, 4, 1, 2]
[3, 4, 5, 1, 2]
[3, 4, 1, 5, 2]
[3, 4, 1, 2, 5]
...
[1, 2, 3, 4, 5]가 될 때까지 반복

 

반복을 거듭하면서 정렬해야 하는 항목의 수가 감소합니다. 교환을 해야 할 때 사용해야 하는 방법은 아래와 같습니다.

 

// ES5
function swap(arr, idx1, idx2) {
    var temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}

// ES2015
const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

버블 정렬은 단순한 구조로 인해 쉽게 이해할 수 있는 알고리즘입니다. 하지만 성능 면에서는 비효율적입니다. 특히 배열의 크기가 커질수록 성능이 급격히 저하됩니다. 버블 정렬은 안정 정렬(stable sort)로 동일한 값의 요소들이 원래의 순서를 유지한다는 장점이 있습니다. 또한, 내부 정렬(in-place sort)로 추가적인 메모리 공간을 거의 사용하지 않습니다.

 

버블 정렬 의사코드

1. i라는 변수를 사용하여 배열의 끝에서 시작하여 처음까지 반복합니다.
2. 내부 반복문에서는 j라는 변수를 사용하여 처음부터 i-1까지 반복합니다.
3. 만약 arr[j]가 arr[j+1]보다 크다면, 두 값을 서로 교환(swap)합니다.
4. 정렬된 배열을 반환합니다.

 

버블 정렬 구현

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

버블 정렬을 구현한 위의 예시는 기본적인 구조를 보여줍니다. 배열의 끝에서부터 처음까지 반복하면서 각 요소를 비교하고 필요한 경우 교환합니다. 하지만 이렇게 구현된 버블 정렬은 이미 정렬이 완료된 경우에도 배열 끝까지 계속 탐색을 하며 비효율적입니다.

 

버블 정렬 최적화

버블 정렬의 성능을 향상시키기 위해 몇 가지 최적화 기법을 사용할 수 있습니다. 그 중 하나는 루프가 마지막으로 실행됐을 때 교환이 있었는지를 확인하는 것입니다. 만약 교환이 없었다면 배열은 이미 정렬된 상태이므로 반복을 중지할 수 있습니다.

function bubbleSort(arr) {
    let noSwaps;
    for(let i = arr.length; i > 0; i--) {
        noSwaps = true;
        for(let j = 0; j < i - 1; j++) {
            if(arr[j] > arr[j+1]) {
                const temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                noSwaps = false;
            }
        }
        if(noSwaps) break;
    }
    return arr;
}

이 최적화된 버블 정렬 구현은 불필요한 반복을 줄여 성능을 향상시킵니다. 루프가 실행될 때 교환이 없었다면, 배열이 이미 정렬된 상태이므로 더 이상의 반복을 중지할 수 있습니다.

 

버블 정렬의 특성

버블 정렬은 간단하지만 비효율적인 정렬 알고리즘입니다. 실제 사용보다는 교육 목적으로 많이 사용됩니다. 이 알고리즘을 이해하면 더 복잡한 정렬 알고리즘을 배우는 데 도움이 됩니다. 또한, 안정 정렬 알고리즘으로 동일한 값의 순서가 유지됩니다.

 

안정 정렬 (Stable Sort)

버블 정렬은 안정 정렬 알고리즘입니다. 이는 동일한 값의 요소들이 원래의 순서를 유지한다는 것을 의미합니다. 예를 들어, 객체 배열을 특정 키로 정렬할 때, 같은 키 값을 가진 객체들이 버블 정렬을 통해서도 순서가 바뀌지 않습니다.

 

내부 정렬 (In-place Sort)

버블 정렬은 추가적인 메모리 공간을 거의 사용하지 않는 내부 정렬 알고리즘입니다. 배열 자체에서 직접 교환 작업을 수행하기 때문에, 메모리 사용량이 매우 적습니다.

 

단점

• 성능이 좋지 않습니다. 특히, 배열의 크기가 클수록 시간 복잡도 O(n^2)로 인해 성능이 급격히 저하됩니다.
• 큰 배열을 정렬하는 데 적합하지 않습니다.

 

버블 정렬의 실제 사용 사례

버블 정렬은 대부분의 경우 비효율적이지만, 간단한 구현과 이해하기 쉬운 알고리즘 구조로 인해 교육 목적으로 자주 사용됩니다. 예를 들어, 알고리즘과 자료 구조를 처음 배우는 학생들에게 버블 정렬은 기본적인 정렬 개념을 이해하는 데 큰 도움이 됩니다.

 

버블 정렬의 빅오 복잡도

• 평균 및 최악의 경우: O(n^2)
• 최상의 경우: O(n) (이미 정렬된 경우)

 

추가 리소스

• Visualgo: 다양한 알고리즘을 시각적으로 볼 수 있는 사이트입니다.