Blog

1. 알고리즘 소개 및 개념

배열 정렬 알고리즘 성능 비교는 개발자라면 반드시 이해해야 할 핵심 주제입니다. 정렬 알고리즘은 데이터를 특정 순서로 재배열하는 기법으로, 검색 효율성을 높이고 데이터 분석을 용이하게 만듭니다. 대표적인 정렬 알고리즘으로는 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort) 등이 있습니다. 각 알고리즘은 시간 복잡도, 공간 복잡도, 안정성(Stability) 측면에서 서로 다른 특성을 가지고 있어, 상황에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

2. 동작 원리 상세 설명

버블 정렬(Bubble Sort): 인접한 두 요소를 비교하여 정렬되지 않은 경우 교환하는 방식입니다. 가장 큰 값이 배열의 끝으로 ‘거품처럼’ 올라가는 과정을 반복합니다.

선택 정렬(Selection Sort): 배열에서 최솟값을 찾아 맨 앞의 요소와 교환하고, 나머지 부분에서 같은 작업을 반복합니다.

삽입 정렬(Insertion Sort): 배열을 정렬된 부분과 미정렬된 부분으로 나누고, 미정렬 부분의 첫 요소를 정렬된 부분의 적절한 위치에 삽입합니다.

병합 정렬(Merge Sort): 분할 정복(Divide and Conquer) 방식으로, 배열을 절반씩 나누어 각각 정렬한 후 병합합니다.

퀵 정렬(Quick Sort): 피벗(pivot)을 선택하여 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한 후 재귀적으로 정렬합니다.

힙 정렬(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;
}

// 사용 예시
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;
}

4.3 삽입 정렬 구현

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

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]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

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

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

5. 최적화 방법

버블 정렬 최적화: 이미 정렬된 경우를 감지하기 위해 swapped 플래그를 사용하여 조기 종료합니다.

퀵 정렬 최적화: 피벗 선택 전략을 개선합니다. 첫 번째, 중간, 마지막 요소의 중간값을 피벗으로 선택하는 'Median-of-Three' 방식을 사용하면 최악의 경우를 피할 수 있습니다. 또한 작은 부분 배열에는 삽입 정렬을 사용하는 하이브리드 방식도 효과적입니다.

function optimizedQuickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // 작은 배열에는 삽입 정렬 사용
    if (high - low < 10) {
      insertionSortRange(arr, low, high);
    } else {
      const pi = medianOfThreePartition(arr, low, high);
      optimizedQuickSort(arr, low, pi - 1);
      optimizedQuickSort(arr, pi + 1, high);
    }
  }
  return arr;
}

function medianOfThreePartition(arr, low, high) {
  const mid = Math.floor((low + high) / 2);
  
  // 중간값을 피벗으로 선택
  if (arr[mid] < arr[low]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[high] < arr[low]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[mid] < arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
  
  return partition(arr, low, high);
}

병합 정렬 최적화: 작은 부분 배열에는 삽입 정렬을 사용하고, 추가 메모리 할당을 최소화하기 위해 in-place 병합을 구현할 수 있습니다.

6. 실전 활용 예제

배열 정렬 알고리즘 성능 비교를 실제로 측정하는 벤치마크 코드입니다:

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

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

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, '힙 정렬');
});

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

// 나이순 정렬
users.sort((a, b) => a.age - b.age);

배열 정렬 알고리즘 성능 비교를 통해 각 알고리즘의 특성을 이해하고, 상황에 맞는 최적의 정렬 방법을 선택할 수 있습니다. 소규모 데이터나 거의 정렬된 데이터는 삽입 정렬, 일반적인 경우는 퀵 정렬, 안정성이 중요한 경우는 병합 정렬을 사용하는 것이 권장됩니다.