[Algorithm]Sort-Bucket Sort

Bucket Sort Algorithm

Bucket Sort Algorithm은 먼저 입력 배열을 여러 버킷으로 나누고 각 버킷에는 다양한 요소가 포함됩니다. 사용할 버킷 수는 입력 요소의 범위와 입력 분포에 따라 달라집니다. 입력을 버킷으로 나눈 후 알고리즘은 삽입 정렬과 같은 다른 정렬 알고리즘을 사용하여 각 버킷을 개별적으로 정렬합니다. 마지막으로 알고리즘은 정렬된 버킷을 연결하여 정렬된 배열을 가져옵니다.

Bucket Sort Algorithm은 다음과 같은 두 가지 방법을 사용하여 수행할 수 있습니다:

1. Internal Bucket Sort(내부 버킷 정렬): 이 접근법은 입력 배열을 저장하는 데 사용되는 동일한 배열 내의 요소를 정렬합니다. 이 방법을 사용하려면 버킷을 저장할 공간이 추가로 필요합니다.
2. External Bucket Sort(외부 버킷 정렬): 이 접근법은 여러 패스를 사용하여 요소를 정렬하며, 각 패스는 입력 배열의 일부를 정렬하고 정렬된 부분은 새 파일에 기록됩니다. 이 방법에는 많은 디스크 공간이 필요합니다.

저는 내부 버킷 정렬로 표현 하겠습니다.

Internal Bucket Sort(내부 버킷 정렬)을 구현하려면 먼저 사용할 버킷 수를 결정해야 합니다. 입력 요소의 범위를 버킷 크기(버킷 수로 나눈 범위)로 나누어 버킷 수를 결정할 수 있습니다. 그런 다음 입력 배열을 반복하고 값을 기준으로 각 요소를 해당 버킷에 배포할 수 있습니다.

요소를 버킷으로 배포한 후 삽입 정렬과 같은 다른 정렬 알고리즘을 사용하여 각 버킷을 개별적으로 정렬할 수 있습니다. 마지막으로 정렬된 버킷을 연결하여 정렬된 배열을 가져옵니다.

코드는 아래와 같습니다.

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) {
    return arr;
  }

  // Determine minimum and maximum values
  let minValue = arr[0];
  let maxValue = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i];
    } else if (arr[i] > maxValue) {
      maxValue = arr[i];
    }
  }

  // Determine number of buckets
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  // Distribute elements into buckets
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
    buckets[bucketIndex].push(arr[i]);
  }

  // Sort each bucket using insertion sort
  for (let i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]);
  }

  // Concatenate sorted buckets
  return buckets.reduce((acc, curr) => acc.concat(curr), []);
}

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
}

위의 코드에서, 입력 배열 배열 배열과 각 버킷에 저장할 수 있는 요소의 수를 결정하는 선택적인 bucketSize 매개 변수를 취하는 bucketSort라는 함수를 정의합니다. bucketSize의 기본값은 5입니다.

먼저 입력 배열이 비어 있는지 확인합니다. 만약 그렇다면, 배열을 그대로 반환합니다. 그런 다음 입력 배열에서 최소값과 최대값을 결정합니다. 배열을 반복하고 각 요소를 현재 최소값 및 최대값과 비교하여 이 작업을 수행합니다.

다음으로 입력 요소의 범위를 버킷 크기로 나누고 하나를 추가하여 사용할 버킷 수를 결정합니다. 그런 다음 버킷 수와 동일한 길이를 가진 버킷이라는 빈 배열을 만듭니다. 또한 빈 배열로 배열을 채웁니다.

그런 다음 입력 배열을 반복하고 값을 기준으로 각 요소를 해당 버킷에 배포합니다. 각 요소에 대한 버킷 인덱스를 계산하고 해당 요소를 해당 버킷에 밀어넣습니다.

요소를 버킷으로 배포한 후에는 작은 배열에 적합한 또 다른 정렬 알고리즘인 insertionSort 함수를 사용하여 각 버킷을 개별적으로 정렬합니다.

마지막으로 정렬된 버킷을 연결하고 정렬된 배열을 반환합니다.

결과는 아래와 같습니다.

const arr = [12, 9, 24, 4, 19, 21, 14, 6, 2, 16];
console.log(bucketSort(arr)); // [ 2, 4, 6, 9, 12, 14, 16, 19, 21, 24 ]

입력 배열을 여러 버킷으로 나누고 각 버킷을 개별적으로 정렬한 다음 정렬된 버킷을 연결하여 정렬된 배열을 가져오는 방법으로 알고리즘이 작동하는 방식을 확인했습니다.