Blog

1. 알고리즘 소개 및 개념

배열 정렬 알고리즘 성능 비교는 프로그래밍에서 가장 기본적이면서도 중요한 주제입니다. 정렬 알고리즘은 데이터를 특정 순서로 배열하는 방법으로, 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort) 등 다양한 방식이 존재합니다. 각 알고리즘은 시간 복잡도, 공간 복잡도, 안정성 측면에서 서로 다른 특성을 가지고 있어, 상황에 맞는 최적의 알고리즘을 선택하는 것이 중요합니다. 이 글에서는 주요 정렬 알고리즘의 성능을 비교 분석하고 실전 구현 방법을 상세히 다룹니다.

2. 동작 원리 상세 설명

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 방식으로, 가장 큰 값이 매 회차마다 끝으로 이동합니다. 선택 정렬은 전체 배열에서 최솟값을 찾아 맨 앞과 교환하는 과정을 반복합니다. 삽입 정렬은 배열을 정렬된 부분과 미정렬 부분으로 나누어, 미정렬 원소를 정렬된 부분의 적절한 위치에 삽입합니다.

병합 정렬은 분할 정복 방식으로 배열을 절반씩 나누어 정렬한 후 병합합니다. 퀵 정렬은 피벗을 기준으로 작은 값과 큰 값을 분할하여 재귀적으로 정렬합니다. 힙 정렬은 힙 자료구조를 이용해 최댓값을 반복적으로 추출하여 정렬합니다. 각 알고리즘의 동작 방식을 이해하는 것이 배열 정렬 알고리즘 성능 비교의 핵심입니다.

3. 시간/공간 복잡도 분석

배열 정렬 알고리즘 성능 비교 시 시간 복잡도가 O(n log n)인 병합, 퀵, 힙 정렬이 대용량 데이터에 적합하며, O(n²) 알고리즘은 소규모 데이터나 거의 정렬된 데이터에 효율적입니다.

4. 단계별 구현 과정

4.1 버블 정렬 구현

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; 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(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

4.2 퀵 정렬 구현

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

// 인플레이스 퀵 정렬 (공간 최적화)
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSortInPlace(arr, left, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left - 1;
  
  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));
// [1, 1, 2, 3, 6, 8, 10]

4.3 병합 정렬 구현

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 = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return [...result, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

4.4 힙 정렬 구현

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(heapSort([12, 11, 13, 5, 6, 7]));
// [5, 6, 7, 11, 12, 13]

5. 최적화 방법

하이브리드 정렬: 대부분의 현대 언어는 작은 배열에 삽입 정렬, 큰 배열에 퀵 정렬을 사용하는 하이브리드 방식을 채택합니다. JavaScript의 Array.sort()는 Tim Sort(병합+삽입)를 사용합니다.

function hybridSort(arr, threshold = 10) {
  if (arr.length <= threshold) {
    return insertionSort(arr);
  }
  return quickSortInPlace(arr);
}

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

피벗 선택 최적화: 퀵 정렬에서 첫 번째, 중간, 마지막 요소의 중앙값을 피벗으로 선택하면 최악의 경우를 방지할 수 있습니다. 메모리 최적화: 인플레이스 정렬을 사용하여 추가 메모리 사용을 최소화합니다.

6. 실전 활용 예제

// 성능 비교 벤치마크
function benchmark(sortFn, arr, name) {
  const start = performance.now();
  sortFn([...arr]);
  const end = performance.now();
  console.log(`${name}: ${(end - start).toFixed(2)}ms`);
}

const testData = Array.from({length: 10000}, () => Math.floor(Math.random() * 10000));

benchmark(bubbleSort, testData, 'Bubble Sort');
benchmark(quickSort, testData, 'Quick Sort');
benchmark(mergeSort, testData, 'Merge Sort');
benchmark(heapSort, testData, 'Heap Sort');

// 실제 사용 예: 객체 배열 정렬
const users = [
  {name: 'Alice', age: 25},
  {name: 'Bob', age: 30},
  {name: 'Charlie', age: 20}
];

// 나이순 정렬 (내장 sort 사용)
users.sort((a, b) => a.age - b.age);
console.log(users);

배열 정렬 알고리즘 성능 비교를 통해 각 상황에 맞는 최적의 알고리즘을 선택할 수 있습니다. 소규모 데이터나 거의 정렬된 데이터는 삽입 정렬, 일반적인 경우는 퀵 정렬, 안정성이 필요하면 병합 정렬, 메모리 제약이 있으면 힙 정렬을 사용하는 것이 효과적입니다.