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

배열 정렬 알고리즘 성능 비교는 프로그래밍에서 가장 중요한 주제 중 하나입니다. 다양한 정렬 알고리즘들은 각각 고유한 특성과 성능을 가지고 있으며, 상황에 따라 최적의 알고리즘을 선택하는 것이 매우 중요합니다. 이 글에서는 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등 주요 정렬 알고리즘들의 성능을 비교 분석하고, 실제 코드 구현과 함께 각 알고리즘의 시간 복잡도와 공간 복잡도를 상세히 살펴보겠습니다.

1. 알고리즘 소개 및 개념

정렬 알고리즘은 데이터를 특정 순서로 배열하는 방법론입니다. 주요 정렬 알고리즘은 크게 비교 기반 정렬과 비교를 사용하지 않는 정렬로 나뉩니다.

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

각 알고리즘은 데이터의 크기, 초기 상태, 메모리 제약 등에 따라 다른 성능을 보입니다.

2. 동작 원리 상세 설명

버블 정렬

배열의 처음부터 끝까지 순회하며 인접한 두 요소를 비교하고, 순서가 잘못되어 있으면 교환합니다. 한 번의 순회가 끝나면 가장 큰 요소가 맨 뒤로 이동합니다. 이 과정을 배열이 정렬될 때까지 반복합니다.

퀵 정렬

피벗(pivot) 요소를 선택한 후, 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 분할합니다. 그 후 각 부분 배열에 대해 재귀적으로 같은 과정을 반복합니다. 피벗 선택 전략에 따라 성능이 크게 달라집니다.

병합 정렬

배열을 절반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 두 개의 정렬된 부분 배열을 병합하여 하나의 정렬된 배열을 만듭니다. 분할 정복 방식으로 항상 일정한 성능을 보장합니다.

힙 정렬

배열을 최대 힙(Max Heap) 구조로 변환한 후, 루트 노드(최댓값)를 배열의 끝으로 이동시키고 힙 크기를 줄입니다. 남은 요소들로 다시 힙을 재구성하는 과정을 반복합니다.

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

핵심 포인트:

• 작은 데이터셋(n < 50): 삽입 정렬이 효율적
• 대용량 데이터: 퀵 정렬, 병합 정렬, 힙 정렬 권장
• 메모리 제약이 있는 경우: 힙 정렬이나 퀵 정렬
• 안정성이 필요한 경우: 병합 정렬이나 삽입 정렬

4. 단계별 구현 과정

4.1 버블 정렬 구현

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

4.3 병합 정렬 구현

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 leftIndex = 0;
  let rightIndex = 0;
  
  // 두 배열을 비교하며 병합
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // 남은 요소들 추가
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 테스트
console.log(mergeSort([64, 34, 25, 12, 22, 11, 90]));
// 출력: [11, 12, 22, 25, 34, 64, 90]

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([64, 34, 25, 12, 22, 11, 90]));
// 출력: [11, 12, 22, 25, 34, 64, 90]

5. 최적화 방법

퀵 정렬 최적화

• 피벗 선택 개선: 중간값(median-of-three) 방식으로 피벗을 선택하여 최악의 경우 방지
• 작은 부분 배열 처리: 크기가 작은 부분 배열은 삽입 정렬로 처리
• 꼬리 재귀 최적화: 스택 오버플로우 방지

function optimizedQuickSort(arr, left = 0, right = arr.length - 1) {
  while (left < right) {
    // 작은 배열은 삽입 정렬 사용
    if (right - left < 10) {
      insertionSort(arr, left, right);
      break;
    }
    
    const pivotIndex = medianOfThree(arr, left, right);
    
    // 왼쪽만 재귀, 오른쪽은 반복문으로
    if (pivotIndex - left < right - pivotIndex) {
      optimizedQuickSort(arr, left, pivotIndex - 1);
      left = pivotIndex + 1;
    } else {
      optimizedQuickSort(arr, pivotIndex + 1, right);
      right = pivotIndex - 1;
    }
  }
  
  return arr;
}

병합 정렬 최적화

• 제자리 병합: 추가 메모리 사용 최소화
• 작은 배열 처리: 임계값 이하는 삽입 정렬 사용
• 정렬 여부 체크: 이미 정렬된 부분은 병합 생략

성능 측정 코드

function measurePerformance(sortFunc, arr, name) {
  const copy = [...arr];
  const start = performance.now();
  sortFunc(copy);
  const end = performance.now();
  
  console.log(`${name}: ${(end - start).toFixed(4)}ms`);
  return end - start;
}

// 다양한 크기의 배열로 테스트
const sizes = [100, 1000, 10000];
const algorithms = [
  { name: '버블 정렬', func: bubbleSort },
  { name: '퀵 정렬', func: quickSort },
  { name: '병합 정렬', func: mergeSort },
  { name: '힙 정렬', func: heapSort }
];

sizes.forEach(size => {
  console.log(`\n배열 크기: ${size}`);
  const randomArr = Array.from({ length: size }, () => Math.floor(Math.random() * 1000));
  
  algorithms.forEach(({ name, func }) => {
    measurePerformance(func, randomArr, name);
  });
});

6. 실전 활용 예제

상황별 알고리즘 선택

function smartSort(arr) {
  const n = arr.length;
  
  // 작은 배열: 삽입 정렬
  if (n < 50) {
    return insertionSort(arr);
  }
  
  // 거의 정렬된 배열 체크
  if (isNearlySorted(arr)) {
    return insertionSort(arr);
  }
  
  // 일반적인 경우: 퀵 정렬
  return quickSort(arr);
}

function isNearlySorted(arr) {
  let inversions = 0;
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) inversions++;
    if (inversions > arr.length * 0.1) return false;
  }
  return true;
}

// 실제 사용 예시
const data = [15, 3, 8, 12, 5, 1, 9];
const sorted = smartSort(data);
console.log('정렬된 배열:', sorted);

객체 배열 정렬

const users = [
  { name: 'Alice', age: 25 },
  { name: 'Bob', age: 30 },
  { name: 'Charlie', age: 20 }
];

// 나이순 정렬 (병합 정렬 활용)
function mergeSortObjects(arr, key) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSortObjects(arr.slice(0, mid), key);
  const right = mergeSortObjects(arr.slice(mid), key);
  
  return mergeObjects(left, right, key);
}

function mergeObjects(left, right, key) {
  const result = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i][key] <= right[j][key]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

const sortedUsers = mergeSortObjects(users, 'age');
console.log(sortedUsers);

결론

배열 정렬 알고리즘 성능 비교를 통해 각 알고리즘의 특성을 이해하고 상황에 맞게 선택하는 것이 중요합니다. 작은 데이터셋에는 삽입 정렬이나 버블 정렬이 효율적이고, 대용량 데이터에는 퀵 정렬, 병합 정렬, 힙 정렬이 적합합니다. 실제 프로젝트에서는 JavaScript의 내장 Array.sort() 메서드가 Timsort 알고리즘을 사용하여 대부분의 경우에 최적화되어 있지만, 알고리즘의 내부 동작을 이해하면 더 나은 코드를 작성할 수 있습니다.