배열 정렬 알고리즘 성능 비교 – 개념부터 구현까지 완벽 마스터

배열 정렬 알고리즘 성능 비교는 개발자라면 반드시 이해해야 할 핵심 주제입니다. 다양한 정렬 알고리즘(버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬)의 시간 복잡도와 공간 복잡도를 비교 분석하여 상황에 맞는 최적의 정렬 방법을 선택할 수 있습니다. 이 가이드에서는 각 알고리즘의 동작 원리부터 실전 구현, 성능 측정까지 상세히 다룹니다.

1. 정렬 알고리즘 소개 및 개념

정렬 알고리즘은 데이터를 특정 순서로 배열하는 방법론입니다. 각 알고리즘은 서로 다른 접근 방식과 성능 특성을 가지고 있습니다.

• 버블 정렬(Bubble Sort): 인접한 두 원소를 비교하며 정렬하는 가장 단순한 알고리즘
• 선택 정렬(Selection Sort): 최솟값을 찾아 맨 앞과 교환하는 방식
• 삽입 정렬(Insertion Sort): 각 원소를 적절한 위치에 삽입하는 방식
• 퀵 정렬(Quick Sort): 피벗을 기준으로 분할 정복하는 효율적인 알고리즘
• 병합 정렬(Merge Sort): 배열을 분할 후 병합하며 정렬하는 안정적인 알고리즘
• 힙 정렬(Heap Sort): 힙 자료구조를 활용한 정렬 방식

배열 정렬 알고리즘 성능 비교를 통해 데이터 크기, 데이터 특성, 메모리 제약 등에 따라 최적의 알고리즘을 선택할 수 있습니다.

2. 동작 원리 상세 설명

버블 정렬

배열의 끝에서부터 인접한 두 원소를 비교하여 큰 값을 뒤로 보냅니다. 한 번의 순회가 끝나면 가장 큰 값이 맨 뒤에 위치하게 됩니다. 이 과정을 배열이 정렬될 때까지 반복합니다.

퀵 정렬

피벗(pivot)을 선택하여 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다. 분할된 각 부분에 대해 재귀적으로 동일한 작업을 수행하여 정렬을 완성합니다. 평균적으로 가장 빠른 성능을 보입니다.

병합 정렬

배열을 절반으로 나누어 각각을 재귀적으로 정렬한 후, 정렬된 두 배열을 하나로 병합합니다. 분할 단계에서는 배열을 계속 반으로 나누고, 병합 단계에서는 정렬하며 합칩니다. 안정 정렬이며 최악의 경우에도 O(n log n)을 보장합니다.

힙 정렬

배열을 최대 힙 구조로 변환한 후, 루트(최댓값)를 배열 끝과 교환하고 힙 크기를 줄입니다. 힙을 재구성하는 과정을 반복하여 정렬을 완성합니다.

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

성능 비교 포인트:

• 작은 데이터셋(<50): 삽입 정렬이 효율적
• 거의 정렬된 데이터: 삽입 정렬 또는 버블 정렬
• 대용량 데이터: 퀵 정렬, 병합 정렬, 힙 정렬
• 메모리 제약: 힙 정렬, 퀵 정렬 (in-place)
• 안정성 필요: 병합 정렬, 삽입 정렬

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;
}

4.2 퀵 정렬 구현

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;
}

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.concat(left.slice(i)).concat(right.slice(j));
}

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);
  }
}

5. 최적화 방법

퀵 정렬 최적화

• 3-way 파티셔닝: 중복 값이 많을 때 효과적
• 중간값 피벗 선택: 첫 번째, 중간, 마지막 값 중 중간값을 피벗으로 선택
• 작은 배열에서 삽입 정렬 사용: 크기가 10 이하면 삽입 정렬로 전환

function optimizedQuickSort(arr, left = 0, right = arr.length - 1) {
  // 작은 배열은 삽입 정렬
  if (right - left < 10) {
    return insertionSort(arr, left, right);
  }
  
  if (left < right) {
    const pivotIndex = medianOfThree(arr, left, right);
    const pivot = partition(arr, left, right, pivotIndex);
    optimizedQuickSort(arr, left, pivot - 1);
    optimizedQuickSort(arr, pivot + 1, right);
  }
  return arr;
}

function medianOfThree(arr, left, right) {
  const mid = Math.floor((left + right) / 2);
  if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
  if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
  if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
  return mid;
}

병합 정렬 최적화

• In-place 병합: 추가 메모리 사용 최소화
• 작은 부분 배열에서 삽입 정렬: 재귀 깊이 감소

6. 실전 활용 예제 - 성능 측정

function compareAlgorithms() {
  const testData = Array.from({length: 10000}, () => Math.floor(Math.random() * 10000));
  
  const algorithms = [
    { name: '퀵 정렬', fn: quickSort },
    { name: '병합 정렬', fn: mergeSort },
    { name: '힙 정렬', fn: heapSort },
    { name: '버블 정렬', fn: bubbleSort }
  ];
  
  algorithms.forEach(({ name, fn }) => {
    const data = [...testData];
    const start = performance.now();
    fn(data);
    const end = performance.now();
    console.log(`${name}: ${(end - start).toFixed(2)}ms`);
  });
}

compareAlgorithms();

실행 결과 예시 (10,000개 원소):

• 퀵 정렬: 12.5ms
• 병합 정렬: 18.3ms
• 힙 정렬: 25.7ms
• 버블 정렬: 1850.2ms

결론

배열 정렬 알고리즘 성능 비교를 통해 각 알고리즘의 특성을 이해하고 상황에 맞는 최적의 선택을 할 수 있습니다. 일반적으로 대용량 데이터에는 퀵 정렬이나 병합 정렬을 사용하고, 작은 데이터나 거의 정렬된 데이터에는 삽입 정렬을 사용하는 것이 효율적입니다. 안정성이 중요하다면 병합 정렬을, 메모리가 제한적이라면 힙 정렬이나 퀵 정렬을 선택하세요.