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

 

버블 정렬 (Bubble Sort)

: 데이터를 옆 데이터와 비교하고, 자리를 바꾸어가며 정렬하는 방식

• 버블 정렬은 배열의 무작위로 섞인 숫자를 정렬하는 방법 중 하나
• 구현이 쉽지만 성능은 좋지 않음
• 앞 숫자와 그 뒷 숫자를 비교해서 자리를 바꾸며 정렬을 수행
  
  • 한 번 반복이 끝날 때마다 제일 큰 숫자가 제일 오른쪽에 정착함
    

    

 

 

 

버블 정렬의 성능

• 시간 복잡도: O(n²)
• 성능이 좋지 않음
  → 요소가 많아질수록 느려짐

 

 

 

버블 정렬의 장단점

장점

• 이해와 구현이 매우 간단함

 

단점

• 성능이 O(n²)으로 별로 좋지 않음
  
• 실무에서는 거의 사용되지 않음

 

 

 

예시: 숫자가 무작위로 들어있는 배열 정렬하기([4, 2, 3, 1])

• 배열의 원소가 4개라면, 자리 교체는 최대 3번 일어나기 때문에 → 배열의 길이보다 1 작은 횟수만큼 반복 필요
• 첫 번째 반복문에서 3개(n - 1)의 원소를 비교하고, 가장 큰 수(4)가 자리를 찾음
• 두 번째 반복문에서 2개(n - 2)의 원소를 비교하고, 가장 큰 수(3)가 자리를 찾음
• 세 번째 반복문에서 1개(n - 3)의 원소를 비교하고, 가장 큰 수(2)가 자리를 찾음

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

function BubbleSort(arr){
    for(let i = 0; i < arr.length - 1; i++){  // 👉 바깥 반복문(전체 회전 ⇒ 3번 반복)
        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;
            }
        }
    }
}

console.log("===== 정렬 전 =====");
console.log(arr); // [ 4, 2, 3, 1 ]

BubbleSort(arr);

console.log("===== 정렬 후 =====");
console.log(arr); // [ 1, 2, 3, 4 ]

 

실행 흐름

• 1회전 (i = 0) 👉 바깥 반복문
  
  • j = 0 ⇒ 4(arr[0]) > 2(arr[1]) → 자리 바꿈 → [2, 4, 3, 1]
  • j = 1 ⇒ 4(arr[1]) > 3(arr[2]) → 자리 바꿈 → [2, 3, 4, 1]
  • j = 2 ⇒ 4(arr[2]) > 1(arr[3]) → 자리 바꿈 → [2, 3, 1, 4]
    ➡️ 가장 큰 숫자 4가 맨 끝으로 이동
• 2회전 (i = 1) 👉 바깥 반복문
  
  • j = 0 ⇒ 2(arr[0]) < 3(arr[1]) → 그대로
  • j = 1 ⇒ 3(arr[1]) > 1(arr[2]) → 자리 바꿈 → [2, 1, 3, 4]
    ➡️ 그다음 큰 숫자 3가 그 앞자리로 이동
• 3회전 (i = 2) 👉 바깥 반복문
  
  • j = 0 ⇒ 2(arr[0]) > 1(arr[1]) → 자리 바꿈 → [1, 2, 3, 4]
    ➡️ 2는 제자리