17주차 (2)

BigO에 대해 설명해주세요

 

Big-O 표기법 (시간 복잡도)

Big-O 표기법은 알고리즘의 성능을 입력 크기(n)가 커질 때의 "최악의 경우" 실행 시간을 분석하는 방법입니다.

• O(1): 입력 크기에 상관없이 항상 일정한 시간이 소요됨
• O(n): 입력 크기에 비례하는 시간이 소요됨
• O(n²): 이중 반복문 등으로 인해 입력 크기의 제곱에 비례하는 시간이 소요됨
• O(n log n): 분할 정복 알고리즘(예: 병합 정렬, 퀵 정렬, 힙 정렬) 등에서 나타나는 시간 복잡도

 

다음의 정렬을 설명하고 본인이 가장 편한 언어를 사용하여 로직을 구현해주세요

• 선택 정렬(Selection Sort)

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // ES6 문법으로 swap
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

// 예시
console.log("Selection Sort:", selectionSort([64, 25, 12, 22, 11]));

• 버블 정렬(Bubble Sort)

function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n; i++) {
    // 마지막 i개는 이미 정렬됨
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// 예시
console.log("Bubble Sort:", bubbleSort([64, 34, 25, 12, 22, 11, 90]));

• 병합 정렬(Merge Sort)

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 merged = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      merged.push(left[i++]);
    } else {
      merged.push(right[j++]);
    }
  }
  // 남은 원소들 추가
  return merged.concat(left.slice(i)).concat(right.slice(j));
}

// 예시
console.log("Merge Sort:", mergeSort([38, 27, 43, 3, 9, 82, 10]));

• 삽입 정렬(Insertion Sort)

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    // key보다 큰 원소들을 오른쪽으로 이동
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

// 예시
console.log("Insertion Sort:", insertionSort([12, 11, 13, 5, 6]));

• 퀵 정렬(Quick Sort)

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const less = arr.slice(1).filter(x => x <= pivot);
  const greater = arr.slice(1).filter(x => x > pivot);

  return quickSort(less).concat(pivot, quickSort(greater));
}

// 예시
console.log("Quick Sort:", quickSort([10, 7, 8, 9, 1, 5]));

• 힙 정렬(Heap Sort)

function heapSort(arr) {
  const n = arr.length;
  
  // 최대 힙 구성
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 하나씩 원소를 추출하여 정렬
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

// 예시
console.log("Heap Sort:", heapSort([12, 11, 13, 5, 6, 7]));