버블 정렬

버블 정렬

숫자를 한번에 하나씩 비교해서 더 큰 숫자가 뒤로 이동하는 정렬 알고리즘이다.
루프를 돌면서 각 요소를 다음 요소와 비교하고 요소가 비교 대상인 다음 요소보다 크면 서로 위치를 바꾼다. 전체 요소가 오름차순으로 정렬될 때까지 반복하고 반복을 할 때마다 정렬해야 할 요소의 수는 감소한다.
일반적으로 버블 정렬의 시간 복잡도는 중첩 루프가 있기 때문에 O(n^2)이다. 예외적으로 데이터가 거의 정렬이 끝난 상태에서 버블 정렬이 실행된다면 O(n)이다.

swap(위치 교환)

버블 정렬은 두 요소를 비교하고 기준에 따라 두 요소의 위치를 교환한다.

function swap(arr, idx1, idx2) {
    let temp = arr[idx1]
    arr[idx1] = arr[idx2]
    arr[idx2] = temp
}
// 또는
function anotherSwap(arr, idx1, idx2){
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
}

버블 정렬 함수

function bubbleSort(arr){
    const swap = (arr, idx1, idx2) => [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
   
    for(let i = arr.length; i > 0; i--){
        // 비교가 끝난 마지막 요소 한 개는 빼고 진행
        for(let j = 0; j < i - 1; j++){
            if(arr[j] > arr[j + 1]) {
                // 앞 수가 다음 수보다 크면 위치 교환
                swap(arr, j, j + 1)
            }
        }
    }
    return arr;
}

버블 정렬 최적화

위 코드는 전체 요소가 오름차순으로 이미 정렬이 끝났음에도 마지막 요소까지 비교를 계속해서 진행하기 때문에 성능이 떨어진다.
교환 유무를 표시하는 noSwaps라는 변수를 이용해 더이상의 교환이 진행되지 않았을 때 함수를 종료하는 방법으로 성능 문제를 해결할 수 있다. 버블 정렬 함수를 최적화하는 코드는 다음과 같다.

function betterBubbleSort(arr){
    const swap = (arr, idx1, idx2) => [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
    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]) {
                // 앞 수가 다음 수보다 크면 위치 교환
                swap(arr, j, j + 1);
                noSwaps = false;
            }
        }
        // 교환된 요소가 없다면 정렬이 완료된 것으로 간주하고 break
        if(noSwaps) break;
    }
    return arr;
}

---

✍️ <JavaScript 알고리즘 & 자료구조 마스터클래스> 강의를 들으며 알게 된 내용을 정리하였습니다.