Blog

1. 알고리즘 소개 및 개념

배열 정렬 알고리즘 성능 비교는 프로그래밍에서 가장 기본적이면서도 중요한 주제입니다. 데이터를 효율적으로 정렬하는 것은 검색, 분석, 최적화 등 다양한 작업의 기초가 되기 때문입니다. 대표적인 정렬 알고리즘으로는 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort) 등이 있습니다. 각 알고리즘은 시간 복잡도, 공간 복잡도, 안정성(Stability), 적용 상황에 따라 장단점이 명확하게 구분됩니다. 작은 데이터셋에서는 단순한 알고리즘이 효율적일 수 있지만, 대용량 데이터에서는 고급 알고리즘이 필수적입니다.

2. 동작 원리 상세 설명

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 가장 단순한 방식입니다. 매 반복마다 가장 큰 값이 배열 끝으로 이동합니다.

선택 정렬은 매 반복마다 최솟값을 찾아 정렬된 부분의 끝에 배치합니다. 교환 횟수가 적어 특정 상황에서 유리합니다.

삽입 정렬은 각 원소를 이미 정렬된 부분의 적절한 위치에 삽입합니다. 부분적으로 정렬된 데이터에 매우 효율적입니다.

병합 정렬은 분할 정복(Divide and Conquer) 방식으로 배열을 반으로 나누고 각각을 정렬한 후 병합합니다. 안정적이고 예측 가능한 성능을 보입니다.

퀵 정렬은 피벗(Pivot)을 기준으로 작은 값과 큰 값을 분할하며 정렬합니다. 평균적으로 가장 빠른 성능을 자랑하지만 최악의 경우 O(n²)까지 떨어질 수 있습니다.

힙 정렬은 힙 자료구조를 활용하여 최댓값 또는 최솟값을 반복적으로 추출하며 정렬합니다.

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

배열 정렬 알고리즘 성능 비교 시 시간 복잡도만큼 중요한 것이 공간 복잡도입니다. 병합 정렬은 추가 메모리가 필요하지만, 퀵 정렬과 힙 정렬은 제자리 정렬(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;
}

// 사용 예시
const array1 = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort([...array1])); // [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 minIndex = i;
    
    // 최솟값 인덱스 찾기
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    // 최솟값을 현재 위치와 교환
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

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

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

const array3 = [12, 11, 13, 5, 6];
console.log(insertionSort([...array3])); // [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]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

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

4.5 퀵 정렬 구현

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 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 array5 = [10, 7, 8, 9, 1, 5];
console.log(quickSort([...array5])); // [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 array6 = [12, 11, 13, 5, 6, 7];
console.log(heapSort([...array6])); // [5, 6, 7, 11, 12, 13]

5. 최적화 방법

1. 하이브리드 정렬: 퀵 정렬과 삽입 정렬을 결합하여, 작은 부분 배열에는 삽입 정렬을 사용하면 성능이 향상됩니다. 일반적으로 크기가 10 이하일 때 삽입 정렬로 전환합니다.

function hybridQuickSort(arr, low = 0, high = arr.length - 1) {
  const THRESHOLD = 10;
  
  if (high - low < THRESHOLD) {
    // 작은 배열은 삽입 정렬 사용
    insertionSortRange(arr, low, high);
  } else if (low < high) {
    const pivotIndex = partition(arr, low, high);
    hybridQuickSort(arr, low, pivotIndex - 1);
    hybridQuickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

2. 피벗 선택 최적화: 퀵 정렬에서 중간값(median-of-three) 방식으로 피벗을 선택하면 최악의 경우를 방지할 수 있습니다.

3. 메모리 최적화: 병합 정렬 시 임시 배열을 재사용하여 메모리 할당 횟수를 줄입니다.

4. 조기 종료: 버블 정렬과 같은 알고리즘에서 교환이 발생하지 않으면 정렬이 완료된 것으로 판단하고 조기 종료합니다.

6. 실전 활용 예제

배열 정렬 알고리즘 성능 비교를 실전에 적용할 때는 데이터 특성을 고려해야 합니다.

// 성능 비교 테스트
function comparePerformance(arr) {
  const algorithms = [
    { name: '버블 정렬', fn: bubbleSort },
    { name: '선택 정렬', fn: selectionSort },
    { name: '삽입 정렬', fn: insertionSort },
    { name: '병합 정렬', fn: mergeSort },
    { name: '퀵 정렬', fn: (a) => quickSort([...a]) },
    { name: '힙 정렬', fn: heapSort }
  ];
  
  algorithms.forEach(({ name, fn }) => {
    const testArray = [...arr];
    const start = performance.now();
    fn(testArray);
    const end = performance.now();
    console.log(`${name}: ${(end - start).toFixed(4)}ms`);
  });
}

// 1000개의 랜덤 숫자로 테스트
const testData = Array.from({ length: 1000 }, () => 
  Math.floor(Math.random() * 10000)
);

comparePerformance(testData);

// 활용 시나리오별 추천
// - 거의 정렬된 데이터: 삽입 정렬
// - 작은 데이터셋 (n < 50): 삽입 정렬
// - 일반적인 경우: 퀵 정렬
// - 안정성이 필요한 경우: 병합 정렬
// - 메모리 제약이 있는 경우: 힙 정렬

실무에서는 JavaScript의 내장 Array.prototype.sort()가 Timsort(삽입 정렬과 병합 정렬의 하이브리드)를 사용하지만, 알고리즘의 원리를 이해하면 최적의 선택을 할 수 있습니다.