[JS] 버블 정렬 (Bubble Sort) / 버블 정렬, 최적화 버블 정렬, 내장 sort()

🚀 문제

주어진 배열을 버블 정렬 (Bubble Sort) 알고리즘을 이용하여 오름차순으로 정렬하시오.

function bubbleSort(arr) {
  // 여기에 코드 작성
}

console.log(bubbleSort([5, 3, 8, 4, 2])); // [2, 3, 4, 5, 8]

---

🔹 코드

function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - (i + 1); j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
            console.log(arr);
        }
    }
    return arr;  // 정렬된 배열 반환
}

console.log(bubbleSort([5, 3, 8, 4, 2])); 
// 출력: [2, 3, 4, 5, 8]

🔎 풀이 과정

1️⃣ 문제 접근 방식

• 버블 정렬은 인접한 두 요소를 비교하면서 정렬하는 방식
• 큰 숫자가 오른쪽으로 "버블(거품)"처럼 이동함
• 내부 반복문을 돌면서 큰 값을 오른쪽으로 하나씩 이동시키는 것이 핵심
• 반복문이 끝나면 가장 큰 값이 배열 끝으로 정렬됨

---

🚀 시간 복잡도 & 최적화

 

방법	코드	시간 복잡도	공간 복잡도	장점	단점
1. 기본 버블 정렬 (현재 코드)	✅ O(n²)	O(1)	구현이 간단함	속도가 느림
2. 최적화 버블 정렬 (불필요한 반복 제거)	✅ O(n²) → O(n) (거의 정렬된 경우)	O(1)	일부 경우 빠름	여전히 비효율적
3. JavaScript 내장 sort()	arr.sort((a, b) => a - b)	O(n log n)	O(n) (내부 정렬 알고리즘)	빠름	내부 구현이 복잡함

---

📌 1️⃣ 기본 버블 정렬 → O(n²)

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

console.log(bubbleSort([5, 3, 8, 4, 2])); 
// [2, 3, 4, 5, 8]

✅ 성능 분석

• 시간 복잡도: O(n²) → 모든 요소를 비교해야 함
• 공간 복잡도: O(1) → 추가 메모리 사용 없음
• 장점: 구현이 매우 직관적
• 단점: 속도가 느림 (큰 배열에 비효율적)

---

📌 2️⃣ 최적화된 버블 정렬 → O(n²) → O(n) (이미 정렬된 경우 빠름)

function optimizedBubbleSort(arr) {
    let swapped;  // 교환 여부 체크
    for (let i = 0; i < arr.length - 1; i++) {
        swapped = false;
        for (let j = 0; j < arr.length - (i + 1); j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break;  // 교환이 없으면 이미 정렬됨
    }
    return arr;
}

console.log(optimizedBubbleSort([5, 3, 8, 4, 2])); 
// [2, 3, 4, 5, 8]

✅ 성능 분석

• 시간 복잡도:
  • 최악: O(n²) (완전히 무작위 배열)
  • 최선: O(n) (이미 정렬된 배열)
• 공간 복잡도: O(1)
• 장점: 정렬이 되어 있는 경우 빠름
• 단점: 여전히 O(n²) 성능 문제 존재

---

📌 3️⃣ JavaScript 내장 sort() → O(n log n)

const sortedArray = [5, 3, 8, 4, 2].sort((a, b) => a - b);
console.log(sortedArray); 
// [2, 3, 4, 5, 8]

✅ 성능 분석

• 시간 복잡도: O(n log n) (빠름)
• 공간 복잡도: O(n) (내부적으로 추가 배열 사용 가능)
• 장점: 빠르고 간단함
• 단점: 내부 정렬 알고리즘이 명확하지 않음

---

🏆 결론: 어떤 방법을 선택해야 할까?

방법	추천 상황
버블 정렬 (O(n²))	코딩 테스트, 학습 목적 (기본 정렬 알고리즘 이해)
최적화 버블 정렬 (O(n)~O(n²))	거의 정렬된 배열이 주어진 경우
내장 sort() (O(n log n))	실전 개발에서 빠르게 정렬할 때

✔ 실전에서는 sort()를 쓰고, 코딩 테스트에서는 최적화된 버블 정렬을 추천! 🚀