[java] 자바의 버킷 정렬(Bucket Sort) 알고리즘 이해하기

14 Dec 2023

java

버킷 정렬은 배열을 여러 개의 작은 버킷으로 나누고 각 버킷을 정렬하는 알고리즘입니다.

버킷 정렬 알고리즘

입력 배열을 순회하며 각 요소를 적절한 버킷에 배치합니다.
각 버킷을 개별적으로 정렬합니다.
각 버킷에서 정렬된 요소를 순서대로 모아 최종 결과 배열을 만듭니다.

자바 코드 예시

다음은 자바로 구현한 버킷 정렬의 간단한 예제 코드입니다.

import java.util.*;

public class BucketSort {
   public static void bucketSort(int[] arr, int bucketSize) {
      if (arr.length == 0) {
         return;
      }

      // 가장 작은 값과 가장 큰 값 구하기
      int minValue = arr[0];
      int maxValue = arr[0];
      for (int i = 1; i < arr.length; i++) {
         if (arr[i] < minValue) {
            minValue = arr[i];
         } else if (arr[i] > maxValue) {
            maxValue = arr[i];
         }
      }

      // 버킷 개수 구하기
      int bucketCount = (maxValue - minValue) / bucketSize + 1;

      // 버킷 초기화
      List<List<Integer>> buckets = new ArrayList<>(bucketCount);
      for (int i = 0; i < bucketCount; i++) {
         buckets.add(new ArrayList<>());
      }

      // 요소를 버킷에 추가
      for (int i = 0; i < arr.length; i++) {
         int index = (arr[i] - minValue) / bucketSize;
         buckets.get(index).add(arr[i]);
      }

      // 각 버킷을 정렬하고 결과 배열 만들기
      int currentIndex = 0;
      for (int i = 0; i < buckets.size(); i++) {
         Collections.sort(buckets.get(i));
         for (int j = 0; j < buckets.get(i).size(); j++) {
            arr[currentIndex++] = buckets.get(i).get(j);
         }
      }
   }

   public static void main(String[] args) {
      int[] arr = {64, 34, 25, 12, 22, 11, 90};
      int bucketSize = 10;
      bucketSort(arr, bucketSize);
      System.out.println("Sorted array: " + Arrays.toString(arr));
   }
}

위 코드는 입력 배열을 주어진 버킷 크기에 따라 정렬하는 간단한 버킷 정렬입니다.

요약

버킷 정렬은 작은 범위의 값들을 정렬할 때 빠른 성능을 보이는 효율적인 정렬 알고리즘입니다. 충분한 메모리 공간이 확보될 수 있다면 적용 가능하며, 자바와 같은 다양한 프로그래밍 언어로 구현할 수 있습니다.

참고 문헌: GeeksforGeeks