Blog

1. 알고리즘 소개 및 개념

배열 정렬 알고리즘 성능 비교는 프로그래밍에서 가장 기본이 되면서도 중요한 주제입니다. 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등 다양한 정렬 알고리즘이 존재하며, 각각의 특성과 성능이 다릅니다. 데이터의 크기, 초기 상태, 메모리 제약에 따라 최적의 알고리즘을 선택하는 것이 중요합니다. 이 가이드에서는 주요 정렬 알고리즘들의 동작 원리와 시간 복잡도를 비교 분석하고, 실제 구현 방법과 최적화 기법을 상세히 다룹니다. 각 알고리즘의 장단점을 이해하면 실무와 코딩테스트에서 상황에 맞는 최적의 선택을 할 수 있습니다.

2. 동작 원리 상세 설명

버블 정렬(Bubble Sort): 인접한 두 원소를 비교하며 큰 값을 뒤로 보내는 과정을 반복합니다. 매 패스마다 가장 큰 값이 맨 뒤로 이동하여 거품이 올라가는 것처럼 보입니다.

선택 정렬(Selection Sort): 매번 최솟값을 찾아 정렬되지 않은 부분의 맨 앞과 교환합니다. 선택된 원소가 제자리를 찾아가는 방식입니다.

삽입 정렬(Insertion Sort): 정렬된 부분에 새로운 원소를 적절한 위치에 삽입합니다. 카드를 정렬하는 것과 유사한 방식으로 동작합니다.

병합 정렬(Merge Sort): 분할 정복 기법을 사용하여 배열을 절반으로 나누고, 각각을 정렬한 후 병합합니다. 안정적인 O(n log n) 성능을 보장합니다.

퀵 정렬(Quick Sort): 피벗을 선택하여 작은 값과 큰 값으로 분할하고 재귀적으로 정렬합니다. 평균적으로 가장 빠른 성능을 보입니다.

힙 정렬(Heap Sort): 힙 자료구조를 이용하여 최댓값을 추출하며 정렬합니다. 추가 메모리가 필요 없는 제자리 정렬입니다.

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

배열 정렬 알고리즘 성능 비교에서 중요한 점은 데이터의 특성에 따라 최적의 알고리즘이 다르다는 것입니다. 거의 정렬된 데이터에는 삽입 정렬이, 대용량 데이터에는 병합 정렬이나 퀵 정렬이 효율적입니다.

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 mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  // 배열을 절반으로 분할
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // 재귀적으로 정렬 후 병합
  return merge(mergeSort(left), mergeSort(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]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  
  // 남은 원소 추가
  return result.concat(left.slice(i)).concat(right.slice(j));
}

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

4.3 퀵 정렬 구현

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // 피벗 기준으로 분할
    const pivotIndex = partition(arr, left, right);
    
    // 재귀적으로 정렬
    quickSort(arr, left, pivotIndex - 1);
    quickSort(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([10, 7, 8, 9, 1, 5]));
// [1, 5, 7, 8, 9, 10]

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. 최적화 방법

하이브리드 정렬: 데이터 크기에 따라 알고리즘을 전환합니다. 작은 배열(n < 10)에는 삽입 정렬을, 큰 배열에는 퀵 정렬이나 병합 정렬을 사용하는 것이 효율적입니다.

function hybridSort(arr) {
  if (arr.length < 10) {
    return insertionSort(arr);
  }
  return quickSort(arr);
}

3-way 퀵 정렬: 중복 값이 많은 경우 피벗과 같은 값들을 따로 처리하여 성능을 향상시킵니다.

인트로 정렬(Introsort): 퀵 정렬로 시작하되 재귀 깊이가 깊어지면 힙 정렬로 전환하여 최악의 경우를 방지합니다. C++ STL의 sort()가 이 방식을 사용합니다.

팀 정렬(Timsort): 병합 정렬과 삽입 정렬을 결합한 알고리즘으로, 실제 데이터의 부분 정렬을 활용합니다. Python과 Java의 기본 정렬 알고리즘입니다.

병렬 처리: 병합 정렬이나 퀵 정렬의 분할 단계를 병렬로 처리하여 멀티코어 환경에서 성능을 극대화할 수 있습니다.

6. 실전 활용 예제

배열 정렬 알고리즘 성능 비교를 실전에 적용한 벤치마크 예제입니다.

function performanceBenchmark() {
  const sizes = [100, 1000, 5000];
  const algorithms = {
    '버블 정렬': bubbleSort,
    '병합 정렬': mergeSort,
    '퀵 정렬': quickSort,
    '힙 정렬': heapSort
  };
  
  sizes.forEach(size => {
    const testData = Array.from({length: size}, () => Math.floor(Math.random() * 1000));
    console.log(`\n데이터 크기: ${size}`);
    
    Object.entries(algorithms).forEach(([name, fn]) => {
      const arr = [...testData];
      const start = performance.now();
      fn(arr);
      const end = performance.now();
      console.log(`${name}: ${(end - start).toFixed(4)}ms`);
    });
  });
}

performanceBenchmark();

배열 정렬 알고리즘 성능 비교를 통해 각 알고리즘의 특성을 이해하고 상황에 맞는 최적의 선택을 할 수 있습니다. 코딩테스트와 실무에서 효율적인 정렬 전략을 세우는 데 이 지식을 활용하시기 바랍니다.