[Javascript] 정렬(2) - 버블 정렬 (Bubble sort)

1. 버블 정렬(Bubble Sort)

• 단순히 인접한 두 원소를 확인하여, 정렬이 안되어 있다면 위치를 서로 변경
• 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름
• 시간 복잡도 O(N²)로 비효율적인 정렬 알고리즘 중 하나

 

1-1. 동작방식

• 각 단계에서는 인접한 두 개의 원소를 비교하여, 필요시 위치를 변경
• 첫째와 둘째를 비교, 둘째와 셋째를 비교하는 방식
• 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동
• 따라서, 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외

* 각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정하는 것으로 이해할 수 있다.

 

1-2. 시간 복잡도

• 최악의 경우 시간 복잡도 O(N²)을 보장
• 이미 정렬된 배열에 대해서 모든 비교가 필요하므로, 굉장히 비효율적인 정렬 알고리즘 중 하나

 

ex)정렬할 배열

 

소스코드 예시

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

let check = [3, 6, 5, 8, 10];
bubbleSortDesc(check);

console.log(check); // [10, 8, 6, 5, 3]

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

let check2 = [3, 6, 5, 8, 10];
bubbleSortAsc(check2);

console.log(check2); // [3, 5, 6, 8, 10]

 

2023.11.27 - [Javascript/코딩테스트-알고리즘] - [Javascript] 정렬(1) - 선택 정렬(sorting)