📅 2025-10-31

➡️ 알고리즘 정렬에 대해 새롭게 알게 된 것 또는 헷갈리는 부분 정리

---

🔎 학습 리마인드

📌 정렬 알고리즘

• 주어진 데이터를 일정 순서(오름/내림차순)로 재배열하는 과정
• 정렬은 데이터 처리 및 검색의 효율성을 높이는데 필수적임

오름차순

const nums = [5, 2, 9, 1];
nums.sort((a, b) => a - b);  //1,2,5,9

내림차순

const nums = [5, 2, 9, 1];
nums.sort((a, b) => b - a);  // 9, 5, 2, 1

문자열 정렬 (알파벳순)

const names = ["철수", "지민", "영희"];
names.sort();  // ["영희", "지민", "철수"]

💡 버블 정렬 (Bubble Sort)

• 두 인접한 데이터를 비교하며 큰 값을 뒤로 보내는 과정을 반복하여 배열 정렬
• 정렬될 때까지 여러 번 반복
• 한 번 순회할 때마다 가장 큰 값이 뒤로 이동
• 시간복잡도 O($n^2$)
• 예) [5, 2, 4, 1] → [2, 5, 4, 1] → [2, 4, 5, 1] → [2, 4, 1, 5] → 반복하면 [1, 2, 4, 5]

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      const prev = arr[j];                   // 현재 값
      const next = arr[j + 1];               // 다음 값
      if (prev > next) {                     // 앞에 있는 값이 뒤에 있는 값보다 크다면
        [arr[j], arr[j + 1]] = [next, prev]; // 자리를 바꿔준다
      }
    }
  }
  return arr;
}

🔗 Brute Force - Bubble Sort

💡 선택 정렬 (Selection Sort)

• 배열에서 가장 작은 값을 찾아 첫 번째 위치에 배치하는 방식으로 정렬
• 시간복잡도 O($n^2$)

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

  for (let i = 0; i < n - 1; i++) {
    
    let minIndex = i;

		// 현재 정렬되지 않은 부분에서 최소값의 인덱스를 찾음
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) { 
        minIndex = j;
      }
    }

    // 현재 위치와 최소값의 위치를 교환
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

🔗 Divide and Conquer - Merge Sort

💡 퀵 정렬 (Quick Sort)

• 분할 정복 방식을 사용하는 고급 정렬 알고리즘
• 기준이 되는 피벗(pivot)을 하나 정함
  • 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽
  • 이걸 계속 재귀적으로 정렬하는 방식
• 예) [5, 3, 8, 4, 2] → 피벗: 5 → [3, 4, 2], 5, [8] → [2, 3, 4], 5, [8] → [2, 3, 4, 5, 8]

function quickSort(arr) {

  if (arr.length <= 1) return arr;    // 배열의 길이가 1 이하라면 더 이상 정렬할 게 없음

  
  const pivot = arr[0];      // 피벗(pivot) 선택: 기준값
  const rest = arr.slice(1); // 피벗을 제외한 나머지 요소들로 배열 분리
 
  const left = [];   // 피벗보다 작은 값들(left)과 큰 값들(right)을 각각 담을 배열
  const right = [];
  
  for (let i = 0; i < rest.length; i++) {  //모든 요소를 순회하면서 피벗과 비교
    const current = rest[i];   // 현재 비교 중인 값
    if (current < pivot) {
      left.push(current);      // 피벗보다 작으면 왼쪽으로
    } else {
      right.push(current);     // 피벗보다 크거나 같으면 오른쪽으로
    }
  }

  console.log(`pivot: ${pivot}, left: [${left}], right: [${right}]`);

  // 왼쪽/오른쪽 각각 다시 정렬하고, 합쳐서 반환
  const sortedLeft = quickSort(left);
  const sortedRight = quickSort(right);

  // 병합 (왼쪽 + pivot + 오른쪽)
  return [...sortedLeft, pivot, ...sortedRight];
}

🔗 Divide and Conquer - Quicksort

💡 병합 정렬 (Merge Sort)

• 분할 정복 전략을 사용하는 정렬 알고리즘
• 큰 문제를 작은 부분으로 쪼갠 뒤, 각각을 정렬하고 병합하여 전체를 정렬
  • 큰 배열을 계속 반으로 나눔
  • 가장 작은 배열(1개짜리)까지 쪼갬
  • 그런 다음, 두 개씩 정렬하면서 합쳐 나감!
• 시간 복잡도 O(n long n)
• 안정 정렬 (같은 값의 순서 유지)

예) [5, 3, 8, 4] → [5, 3], [8, 4] → [3, 5], [4, 8] → [3, 4, 5, 8]

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);   // 정렬된 두 배열을 병합
}

function merge(left, right) {
  const result = [];

  // 두 배열이 모두 요소를 가지고 있을 때 비교하며 병합
  while (left.length && right.length) {
    // 왼쪽 첫 번째 값이 더 작으면 결과 배열에 추가
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  // 남은 요소들(왼쪽이나 오른쪽 중 하나만 남을 수 있음)을 합침
  return [...result, ...left, ...right];
}

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

---

💡 요약 정리

[버블 정렬]   인접한 값끼리 비교 → 큰 값을 뒤로
[선택 정렬]   전체에서 최소값 찾아 앞으로
[퀵 정렬]     피벗 기준으로 좌/우 분할 후 재귀
[병합 정렬]   분할 → 각각 정렬 → 병합

알고리즘	평균 시간복잡도	최악 시간복잡도	안정 정렬	특징
버블 정렬	O(n²)	O(n²)	O	구현 쉬움, 비효율적
선택 정렬	O(n²)	O(n²)	X	교환 횟수 적음
퀵 정렬	O(n log n)	O(n²)	X	평균적으로 매우 빠름
병합 정렬	O(n log n)	O(n log n)	O	메모리 사용 많음

---