버블 정렬 (Bubble Sort)

if (arr[j] > arr[j + 1]) {
  // 왼쪽이 오른쪽보다 크면...
}

[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

for (let j = 0; j < arr.length - 1; j++) {
  // 처음부터 끝까지
}

for (let i = 0; i < arr.length; i++) {
  // n번 반복
}

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 원소 교환
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

// 사용 예시
const numbers = [5, 2, 8, 1, 9];
console.log(bubbleSort(numbers));  // [1, 2, 5, 8, 9]

// ❌ 최적화 전: 항상 n² 비교
for (let j = 0; j < n - 1; j++)

// ✅ 최적화 후: 이미 정렬된 부분 제외
for (let j = 0; j < n - i - 1; j++)

// ✅ 추가 최적화: 조기 종료
if (!swapped) break;  // 이미 정렬됨!

// 디버깅용 버전
function bubbleSortDebug(arr) {
  console.log('시작:', arr);
  const n = arr.length;

  for (let i = 0; i < n; i++) {
    console.log(`\n패스 ${i + 1}:`);
    let swapped = false;

    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        console.log(`  교환: [${arr[j]}, ${arr[j + 1]}] → [${arr[j + 1]}, ${arr[j]}]`);
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    console.log(`  결과: [${arr}]`);
    if (!swapped) {
      console.log(`  ✅ 정렬 완료! (조기 종료)`);
      break;
    }
  }

  return arr;
}

// 실행해보기
bubbleSortDebug([5, 2, 8, 1, 9]);

for (let i = 0; i < n; i++) {           // n번
  for (let j = 0; j < n - i - 1; j++) { // n-1, n-2, ..., 1번
    // 비교 및 교환
  }
}

// ❌ 나쁜 예: 새 배열 생성 → O(n) 공간
const sorted = [...arr].sort();

// ✅ 좋은 예: 제자리 교환 → O(1) 공간
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

// 10줄로 끝!
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n - 1; j++) {
    if (arr[j] > arr[j + 1]) {
      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
  }
}

const students = [
  { name: 'Alice', score: 80 },
  { name: 'Bob', score: 80 },
  { name: 'Charlie', score: 90 }
];

// 점수로 정렬 후에도 Alice가 Bob보다 앞에 있음

// 100개 원소를 정렬하면...
// 버블 정렬: ~4,950번 비교
// 퀵 정렬: ~664번 비교

// 약 7.5배 차이!

// ❌ 절대 이렇게 쓰지 마세요
bubbleSort(largeArray);

// ✅ 내장 정렬 사용
largeArray.sort();

// 10개 정도는 삽입 정렬이 더 빠름
const small = [5, 2, 8, 1, 9];
insertionSort(small);  // 더 효율적

// 알고리즘 수업 첫 시간
console.log('정렬이란 이런 거예요!');

const tiny = [3, 1, 2];
// 이 정도는 버블 정렬도 괜찮음

const almostSorted = [1, 2, 3, 5, 4];  // 마지막만 안 맞음
// 한 번의 패스로 끝! O(n)

// ❌ 절대 금지
const users = await fetchUsers();  // 10,000개
bubbleSort(users);

// ✅ 항상 이렇게
users.sort((a, b) => a.name.localeCompare(b.name));

// 100,000개 이상이면 버블 정렬은 재앙
const bigData = generateData(100000);
// 퀵 정렬, 병합 정렬 사용!

// ❌ 잘못된 코드
for (let j = 0; j < n; j++) {  // n까지 가면 arr[n]은 undefined!
  if (arr[j] > arr[j + 1]) {
    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
  }
}

// ✅ 올바른 코드
for (let j = 0; j < n - 1; j++) {  // n-1까지만

// ❌ 원본이 변경됨
const original = [5, 2, 8];
bubbleSort(original);
console.log(original);  // [2, 5, 8] - 변경됨!

// ✅ 원본 보호
const original = [5, 2, 8];
const sorted = bubbleSort([...original]);
console.log(original);  // [5, 2, 8] - 안전!

// ❌ 조건이 잘못되면 무한 루프
for (let i = 0; i <= n; i++) {  // i < n이어야 함
  for (let j = 0; j <= n - 1; j++) {  // j < n-1이어야 함

// 버블 정렬: 인접한 원소 비교
[5, 2, 8, 1] → [2, 5, 1, 8] → ...

// 선택 정렬: 최소값을 찾아 앞으로
[5, 2, 8, 1] → [1, 2, 8, 5] → ...

// 버블: 끝에서부터 정렬
[5, 2, 8, 1, 9] → [..., 8, 9] → [..., 2, 8, 9]

// 삽입: 앞에서부터 정렬
[5, 2, 8, 1, 9] → [2, 5, ...] → [2, 5, 8, ...]

// 버블 정렬을 직접 구현해보세요
function bubbleSort(arr) {
  // 여기에 코드 작성
}

console.log(bubbleSort([5, 2, 8, 1, 9]));
// 기대 결과: [1, 2, 5, 8, 9]

// 큰 것부터 작은 순서로 정렬
function bubbleSortDesc(arr) {
  // 힌트: 비교 조건만 바꾸면 됩니다
}

console.log(bubbleSortDesc([5, 2, 8, 1, 9]));
// 기대 결과: [9, 8, 5, 2, 1]

// 나이순으로 정렬
const people = [
  { name: 'Alice', age: 25 },
  { name: 'Bob', age: 20 },
  { name: 'Charlie', age: 30 }
];

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