비둘기집 정렬

비둘기집 정렬

정렬될 값들의 수 n과 잠재적인 키 값들의 범위 길이 N이 대략적으로 동일한, 요소의 정렬 나열에 적합합 정렬 알고리즘?

한 번의 분배/수집 작업으로 정렬되는 간단하면서 빠른 정렬 알고리즘

비둘기집 정렬 알고리즘의 시간 복잡도와 공간 복잡도는 자료의 최대값과 최소값의 차이에 정비례함. => 자료의 분포 범위가 넓을수록 비둘기집 갯수가 늘어나 시간과 공간 증가.

기본 원리 : n개의 상자, n+1 이상의 물건이 있을 경우 어떤 상자에는 2개 이상의 물건이 들어가게 된다.

예시 코드 1

void pigeonhole_sort(int *data, int n)
{
  int i, j, min, max, range, *house;

  for(i = 1, min = max = data[0]; i < n; i++)
  {
    if (data[i] < min) min = data[i];
    if (data[i] > max) max = data[i];
  }
  //최대값과 최소값을 찾는다. 

​

  range = max - min + 1;
  house = (int *)calloc(sizeof(int), range);

  if (house == NULL) { fprintf(stdin, "비둘기집을 만들 공간이 부족합니다.\n"); return; }
 
  for(i = 0; i < n; i++) house[data[i]-min]++;

  for(i = j = 0; i < range; i++) while(house[i] > 0) { house[i]--; data[j++] = i + min; }
  free(house);
}

예시 코드 2

function pigeonholeSort(arr) {
  if (arr.length === 0) return [];

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const size = max - min + 1;

  // 피존홀 배열 초기화
  const holes = Array.from({ length: size }, () => []);

  // 각 요소를 해당 피존홀에 삽입
  for (let i = 0; i < arr.length; i++) {
    holes[arr[i] - min].push(arr[i]);
  }

  // 피존홀에서 정렬된 값 꺼내기
  let i = 0;
  for (let hole of holes) {
    for (let val of hole) {
      arr[i++] = val;
    }
  }

  return arr;
}

// 예제 사용
const input = [8, 3, 2, 7, 4, 6, 8];
console.log(pigeonholeSort(input)); // [2, 3, 4, 6, 7, 8, 8]