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

배열 정렬 알고리즘 성능 비교는 소프트웨어 개발과 코딩 테스트에서 가장 중요한 주제 중 하나입니다. 다양한 정렬 알고리즘의 성능 특성을 이해하면 상황에 맞는 최적의 알고리즘을 선택할 수 있습니다. 이 가이드에서는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등 주요 정렬 알고리즘의 성능을 비교 분석하고, 각각의 특징과 활용 시나리오를 상세히 살펴보겠습니다.

1. 알고리즘 소개 및 개념

정렬 알고리즘은 데이터를 특정 순서(오름차순 또는 내림차순)로 배열하는 알고리즘입니다. 각 정렬 알고리즘은 고유한 접근 방식과 성능 특성을 가지고 있습니다.

• 버블 정렬(Bubble Sort): 인접한 두 요소를 비교하며 정렬하는 가장 단순한 알고리즘
• 선택 정렬(Selection Sort): 매 단계마다 최솟값을 찾아 정렬하는 알고리즘
• 삽입 정렬(Insertion Sort): 각 요소를 적절한 위치에 삽입하는 알고리즘
• 병합 정렬(Merge Sort): 분할 정복 기법을 사용하는 효율적인 알고리즘
• 퀵 정렬(Quick Sort): 피벗을 기준으로 분할하는 빠른 알고리즘
• 힙 정렬(Heap Sort): 힙 자료구조를 활용한 안정적인 알고리즘

배열 정렬 알고리즘 성능 비교를 통해 각 알고리즘의 시간 복잡도, 공간 복잡도, 안정성을 파악할 수 있습니다.

2. 동작 원리 상세 설명

버블 정렬 (Bubble Sort)

배열을 순회하며 인접한 두 요소를 비교하고, 순서가 잘못되어 있으면 교환합니다. 매 패스마다 가장 큰 값이 배열의 끝으로 이동하며, 이 과정을 배열이 정렬될 때까지 반복합니다.

선택 정렬 (Selection Sort)

정렬되지 않은 부분에서 최솟값을 찾아 정렬되지 않은 부분의 첫 번째 요소와 교환합니다. 이 과정을 배열의 크기만큼 반복하여 전체를 정렬합니다.

삽입 정렬 (Insertion Sort)

두 번째 요소부터 시작하여 앞의 정렬된 부분과 비교하며 적절한 위치에 삽입합니다. 카드를 정렬하는 방식과 유사하며, 거의 정렬된 데이터에 매우 효율적입니다.

병합 정렬 (Merge Sort)

배열을 절반으로 나누고 각각을 재귀적으로 정렬한 후, 정렬된 두 배열을 병합합니다. 분할 정복(Divide and Conquer) 전략을 사용하여 안정적인 O(n log n) 성능을 보장합니다.

퀵 정렬 (Quick Sort)

피벗을 선택하고 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분할합니다. 각 부분을 재귀적으로 정렬하여 전체를 정렬하며, 평균적으로 가장 빠른 정렬 알고리즘입니다.

힙 정렬 (Heap Sort)

배열을 최대 힙으로 구성한 후, 루트 노드(최댓값)를 배열의 끝으로 이동시키고 힙을 재구성합니다. 이 과정을 반복하여 정렬을 완성합니다.

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

공간 복잡도: 버블, 선택, 삽입, 힙 정렬은 제자리 정렬(in-place)로 추가 메모리가 거의 필요 없습니다. 병합 정렬은 O(n)의 추가 공간이 필요하며, 퀵 정렬은 재귀 호출 스택으로 O(log 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;
}

// 사용 예제
const arr1 = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort([...arr1])); // [11, 12, 22, 25, 34, 64, 90]

4.2 선택 정렬 구현

function selectionSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    
    // 최솟값 찾기
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    // 최솟값을 현재 위치와 교환
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  
  return arr;
}

const arr2 = [64, 25, 12, 22, 11];
console.log(selectionSort([...arr2])); // [11, 12, 22, 25, 64]

4.3 삽입 정렬 구현

function insertionSort(arr) {
  const n = arr.length;
  
  for (let i = 1; i < n; 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;
}

const arr3 = [12, 11, 13, 5, 6];
console.log(insertionSort([...arr3])); // [5, 6, 11, 12, 13]

4.4 병합 정렬 구현

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

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

4.5 퀵 정렬 구현

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

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

const arr5 = [10, 7, 8, 9, 1, 5];
console.log(quickSort([...arr5])); // [1, 5, 7, 8, 9, 10]

4.6 힙 정렬 구현

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

const arr6 = [12, 11, 13, 5, 6, 7];
console.log(heapSort([...arr6])); // [5, 6, 7, 11, 12, 13]

5. 최적화 방법

버블 정렬 최적화

조기 종료 플래그(swapped)를 사용하여 이미 정렬된 배열의 경우 O(n) 시간에 완료할 수 있습니다. 양방향 버블 정렬(칵테일 정렬)을 사용하면 일부 케이스에서 성능을 개선할 수 있습니다.

삽입 정렬 최적화

이진 검색을 사용하여 삽입 위치를 찾으면 비교 횟수를 줄일 수 있습니다. 작은 크기의 하위 배열에 대해서는 병합 정렬이나 퀵 정렬 대신 삽입 정렬을 사용하는 하이브리드 접근법이 효과적입니다.

퀵 정렬 최적화

무작위 피벗 선택, 중간값 피벗(Median-of-Three), 3-way 파티셔닝(중복 값이 많을 때 유용)을 사용하여 최악의 경우를 방지할 수 있습니다. 작은 하위 배열에는 삽입 정렬로 전환하면 재귀 오버헤드를 줄일 수 있습니다.

병합 정렬 최적화

제자리 병합 정렬(In-place merge sort)을 구현하여 공간 복잡도를 줄일 수 있습니다. Timsort처럼 삽입 정렬과 병합 정렬을 결합한 하이브리드 알고리즘을 사용하면 실제 데이터에서 더 나은 성능을 얻을 수 있습니다.

힙 정렬 최적화

Bottom-up 힙 구성을 사용하고, 캐시 효율성을 고려한 메모리 접근 패턴을 적용하여 성능을 향상시킬 수 있습니다.

6. 실전 활용 예제

성능 벤치마크 테스트

function benchmark(sortFn, arr, name) {
  const start = performance.now();
  sortFn([...arr]);
  const end = performance.now();
  console.log(`${name}: ${(end - start).toFixed(3)}ms`);
}

// 테스트 데이터 생성
const sizes = [100, 1000, 5000];

sizes.forEach(size => {
  console.log(`\n배열 크기: ${size}`);
  const randomArr = Array.from({length: size}, () => Math.floor(Math.random() * 1000));
  
  benchmark(bubbleSort, randomArr, "버블 정렬");
  benchmark(selectionSort, randomArr, "선택 정렬");
  benchmark(insertionSort, randomArr, "삽입 정렬");
  benchmark(mergeSort, randomArr, "병합 정렬");
  benchmark(quickSort, randomArr, "퀵 정렬");
  benchmark(heapSort, randomArr, "힙 정렬");
});

// 특수 케이스 테스트
console.log("\n거의 정렬된 배열:");
const nearSorted = Array.from({length: 1000}, (_, i) => i);
nearSorted[500] = 999;
benchmark(insertionSort, nearSorted, "삽입 정렬");
benchmark(quickSort, nearSorted, "퀵 정렬");

실무 적용 가이드라인

• 작은 배열(n < 50): 삽입 정렬 사용 (간단하고 오버헤드가 적음)
• 거의 정렬된 데이터: 삽입 정렬 또는 Timsort 사용
• 일반적인 경우: 퀵 정렬 또는 병합 정렬 사용
• 안정성이 필요한 경우: 병합 정렬 사용
• 메모리 제약이 있는 경우: 힙 정렬 또는 제자리 퀵 정렬 사용
• 최악의 경우 보장이 필요한 경우: 병합 정렬 또는 힙 정렬 사용

결론

배열 정렬 알고리즘 성능 비교를 통해 각 알고리즘의 장단점을 이해하고 상황에 맞는 최적의 선택을 할 수 있습니다. 작은 데이터셋에는 단순한 O(n²) 알고리즘이 효율적일 수 있으며, 큰 데이터셋에는 O(n log n) 알고리즘이 필수적입니다. 실무에서는 JavaScript의 Array.sort()가 Timsort를 기반으로 구현되어 있어 대부분의 경우에 최적화되어 있지만, 알고리즘의 동작 원리를 이해하면 특수한 상황에서 커스텀 솔루션을 구현할 수 있습니다. 이 가이드를 통해 배열 정렬 알고리즘 성능 비교에 대한 완벽한 이해를 얻으시길 바랍니다.