흩어진 데이터를, 순서대로 줄 세우기

🔎 왜 정렬을 할까? 정렬 자체가 목적인 경우도 있지만, 진짜 이유는 정렬돼 있으면 그다음 일이 빨라지기 때문이에요.
대표적으로 탐색이 빨라져요. 정렬된 배열에서는 이진 탐색으로 O(log n)만에 찾을 수 있어요(정렬 안 된 배열은 하나씩 봐서 O(n)). 💡 "먼저 정렬해두고, 그다음 빠르게 처리한다"는 흐름은 코테에서 정말 자주 나오는 패턴이에요.

🫧 버블 정렬 (Bubble Sort) 인접한 두 값을 비교해서, 순서가 틀리면 교환해요. 이 과정을 반복하면 큰 값이 거품처럼 뒤로 밀려가요.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {       // n번
    for (let j = 0; j < arr.length - 1 - i; j++) { // 안에서 또 n번
      if (arr[j] > arr[j + 1]) {                    // 인접한 둘 비교
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 교환
      }
    }
  }
  return arr;
}

반복문이 두 겹이라 n × n → O(n²).

🎯 선택 정렬 (Selection Sort) 남은 부분에서 최솟값을 찾아 맨 앞으로 보내요. 이걸 반복하면 앞에서부터 차곡차곡 정렬돼요.
"가장 작은 걸 골라 앞에, 그다음 작은 걸 그다음에…" — 이름 그대로 고르는(select) 정렬이에요. 역시 O(n²).

🃏 삽입 정렬 (Insertion Sort) 앞쪽은 이미 정렬됐다고 보고, 새 값을 정렬된 부분의 알맞은 자리에 끼워넣어요. 카드 게임에서 손패를 정리하는 방식과 똑같아요.
데이터가 거의 정렬돼 있으면 아주 빠르지만, 최악의 경우는 O(n²).

🧩 병합 정렬 (Merge Sort) — 분할 정복 배열을 반으로 계속 쪼갠 뒤, 각각을 정렬하고 다시 합치면서(merge) 순서를 맞춰요. 이렇게 큰 문제를 작은 문제로 나눠 푸는 방식을 분할 정복(Divide and Conquer)이라고 해요.

// 개념만: 반으로 쪼개고(분할) → 각각 정렬 → 합치기(정복)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;      // 더 못 쪼개면 그대로
  const mid = Math.floor(arr.length / 2);
  const left  = mergeSort(arr.slice(0, mid));  // 왼쪽 반
  const right = mergeSort(arr.slice(mid));      // 오른쪽 반
  return merge(left, right);            // 정렬된 둘을 합치기
}

쪼개는 깊이가 log n이고 각 단계마다 n만큼 합치므로 O(n log n).

⚡ 퀵 정렬 (Quick Sort) — 기준값으로 가르기 기준값(pivot) 하나를 정해, 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눠요. 그런 다음 양쪽을 같은 방식으로 또 정렬해요.
평균 O(n log n)으로 매우 빠르지만, pivot을 나쁘게 고르면 최악 O(n²)이 될 수도 있어요. 💡 병합·퀵 모두 "큰 문제를 절반씩 쪼갠다"는 아이디어라 log n이 등장해요. 구현 세부는 나중에, 지금은 큰 그림만 잡으면 충분해요.

🔒 안정 vs 불안정 점수가 같은 A(90), B(90)이 원래 A → B 순서로 있었다고 해봐요.
안정 정렬: 정렬 후에도 같은 90끼리는 A → B 순서 유지.
불안정 정렬: 같은 90끼리 순서가 바뀔 수도 있음. 💡 "이름순 정렬 → 다시 점수순 정렬" 같은 2차 정렬에서 이전 순서를 지켜야 할 때 안정성이 중요해요. 병합 정렬은 안정, 퀵 정렬은 보통 불안정이에요.

⚠️ JS sort의 함정 — 기본은 "문자열" 비교 JS arr.sort()는 기본적으로 원소를 문자열로 바꿔 사전순으로 비교해요. 그래서 숫자를 그냥 정렬하면 엉뚱한 결과가 나와요.

[10, 2, 1].sort();            // ["1","10","2"]처럼 → [1, 10, 2] 😱
[10, 2, 1].sort((a, b) => a - b); // 오름차순 → [1, 2, 10] ✅
[10, 2, 1].sort((a, b) => b - a); // 내림차순 → [10, 2, 1]

숫자를 정렬할 땐 비교함수 (a, b) => a - b를 꼭 넘겨야 해요. a - b가 음수면 a가 앞, 양수면 b가 앞이에요.