[자료 구조와 알고리즘] 정렬 - 버블 정렬

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

정렬 - 버블 정렬

 

 

 

 

📍 버블 정렬(Bubble Sort)

👉🏻 가장 쉽게 생각할 수 있는 정렬 중 하나로 구현이 쉬우나 성능이 좋지는 않음

 

[4, 2, 3, 1]

// 앞에 있는 숫자와 그 뒤의 숫자를 비교해서 조건에 따라 자리를 바꿈
 _  _
[2, 4, 3, 1]
    _  _
[2, 3, 4, 1]
       _  _
[2, 3, 1, 4]

// 4(마지막 원소) 자리가 고정되었음(정렬 완료)

 _  _
[2, 3, 1] // 배열 유지
    _  _
[2, 1, 3]

// 3(마지막 원소) 자리가 고정되었음
 _  _
[1, 2]

// 남은 원소는 1 하나이므로 정렬 끝

 

 

 

📍 버블 정렬의 구현

[ bubble_sort.mjs ]

function BubbleSort(arr) {
    // 배열이 n개라면 n-1만큼 정렬해야 함
    for(let i = 0; i < arr.length - 1; i++) {
        // 하나의 원소는 원소의 개수에서 -1만큼 정렬해야 함
        for(let j = 0; j < (arr.length - i - 1); j++) {
            if(arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

let arr = [4, 2, 3, 1];

console.log("===== 정렬 전 =====");
console.log(arr);

BubbleSort(arr);

console.log("===== 정렬 후 =====");
console.log(arr);

 

 

 

📍 버블 정렬의 성능(빅 오 ver.)

👉🏻 길이 n 배열에서 반복문을 한 번 거칠 때마다 마지막 원소가 정렬됨

👉🏻 등차수열의 합의 모습이 됨 (n - 1) + (n - 2) + (n -3) + ... + 2 + 1

 

👉🏻 O(n^2) 

 

 

📍 버블 정렬의 장단점

👉🏻 장점: 이해와 구현 간단함

 

👉🏻 단점: 성능이 좋지 않음