셸 정렬

삽입 정렬의 개선된 버전으로, 원소를 멀리 떨어진 요소부터 비교합니다. 전체 배열을 부분 시퀀스로 분할하여 각각 삽입 정렬을 수행한 후 최종적으로 전체 정렬을 완성합니다.

동작 과정

1. 감소하는 증분 시퀀스(t₁, t₂, ..., tₖ) 설정 (tₖ=1)
2. 각 증분 크기별로 부분 배열 분할
3. 부분 배열에 삽입 정렬 적용

function shellSort(arr) {
  const len = arr.length;
  for (let gap = Math.floor(len/2); gap > 0; gap = Math.floor(gap/2)) {
    for (let i = gap; i < len; i++) {
      const current = arr[i];
      let position = i;
      while (position >= gap && arr[position - gap] > current) {
        arr[position] = arr[position - gap];
        position -= gap;
      }
      arr[position] = current;
    }
  }
  return arr;
}

힙 정렬

힙 자료구조를 이용한 선택 정렬 방식입니다. 최대 힙 구성 후 루트 노드와 마지막 노드를 교환하며 정렬을 수행합니다.

구현 절차

function createHeap(data) {
  const len = data.length;
  for (let i = Math.floor(len/2); i >= 0; i--) {
    adjustHeap(data, i, len);
  }
}

function adjustHeap(data, idx, size) {
  let childIdx = 2 * idx + 1;
  while (childIdx < size) {
    if (childIdx + 1 < size && data[childIdx] < data[childIdx + 1]) {
      childIdx++;
    }
    if (data[idx] >= data[childIdx]) break;
    [data[idx], data[childIdx]] = [data[childIdx], data[idx]];
    idx = childIdx;
    childIdx = 2 * idx + 1;
  }
}

function heapSort(data) {
  createHeap(data);
  for (let i = data.length - 1; i > 0; i--) {
    [data[0], data[i]] = [data[i], data[0]];
    adjustHeap(data, 0, i);
  }
  return data;
}

계수 정렬

정수 제한이 있는 경우 효율적인 알고리즘으로, 값의 발생 횟수를 카운팅하여 정렬합니다.

function countSort(arr, max) {
  const countArr = new Array(max + 1).fill(0);
  const output = [];
  
  arr.forEach(val => countArr[val]++);
  
  countArr.forEach((count, num) => {
    while (count--) output.push(num);
  });
  
  return output;
}

버킷 정렬

계수 정렬의 확장으로, 데이터를 버킷에 분산시킨 후 각 버킷을 개별 정렬합니다.

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) return arr;
  
  const minVal = Math.min(...arr);
  const maxVal = Math.max(...arr);
  const bucketCount = Math.floor((maxVal - minVal) / bucketSize) + 1;
  const buckets = Array.from({length: bucketCount}, () => []);
  
  arr.forEach(num => {
    buckets[Math.floor((num - minVal) / bucketSize)].push(num);
  });
  
  return buckets.reduce((result, bucket) => {
    return result.concat(bucket.sort((a, b) => a - b));
  }, []);
}

기수 정렬

LSD(Least Significant Digit) 방식으로 자릿수별로 안정 정렬을 반복 적용합니다.

function radixSort(arr, maxDigits) {
  const bins = Array(10).fill().map(() => []);
  
  for (let exp = 0, mod = 10, dev = 1; exp < maxDigits; exp++, dev *= 10, mod *= 10) {
    arr.forEach(num => {
      const digit = Math.floor((num % mod) / dev);
      bins[digit].push(num);
    });
    
    arr = bins.reduce((flat, bin) => flat.concat(bin), []);
    bins.forEach(bin => bin.length = 0);
  }
  
  return arr;
}