버킷정렬(Bucket Sort)

버킷 정렬(bucket sort) or bin sort 은 입력 값이 일정한 범위에 걸쳐 분포(uniformly distributed)되어있을 때 주로 유용하다. 

예를들어 0.0에서 1.0 범위의 부동 소수점 숫자 집합을 정렬해야 하고 싶다고 할때 선택할수 있는 정렬의 방법은 여러가지이다. 
간단한 방법은 비교 기반 알고리즘(comparision based sort alogrithm)을 적용하면 된다.
비교 기반 알고리즘 중 그래도 시간복잡도가 좀 빠른  병합 정렬(merge sort), 힙 정렬(heap sort), 빠른 정렬(quick sort)은 O(nLogn) 이다. 즉 O(nLogn)보다 좋을수는 없다.
선형 시간(linear time)으로 배열을 정렬할 방법은 없을까?
카운팅 정렬(counting sort)와 기수정렬(radix sort)는 정렬하는데 선형시간내에 수행할수 있어 선택지가 될수 있지만 문제는 카운팅정렬에서 원소의 값을 키로하여 사용하기때문에 소수점은 사용할수없고(배열의 index는 정수형이어야 한다) radix sort 도 내부적으로 counting sort를 사용하기 때문에 똑같은 제약을 받게 된다.

방법은 버킷 정렬을 사용하면 된다. 

그림1. 버킷정렬 알고리즘

[출처] https://www.slideshare.net/KrupaliMistry/bucket-sort-a-noncomparision-algorithm-66752812

 

그림 1은 버킷 알고리즘을 보여주는데 단계는 다음과 같다.

 

bucket sort algorithm

1. N=10(배열의 인덱스가 정수 0-9까지 필요로함)인 빈 버킷 또는 리스트 B를 셍상힌다.
2. 배열 A의 모든 원소 A[i] 에 대해  B[N*A[i]] 버킷에 A[i]를 추가한다.
ex) A[0] = 0.78 -> B[10*0.78 = 7] = 0.78 ... 
3. B[N*A[i]] 버킷에 A[i]를 추가시 삽입정렬(insertion sort)을 사용하여 각 버킷에 추가된 자료를 정렬한다.
4. 모든 버킷들 (B[0] 부터 B[N-1])에 정렬된데이터를 순차적으로 연결한다.

 

알고리즘은 상대적으로 간단하기 때문에 바로 구현 하도록 하겠다.

 

 
import java.util.ArrayList;
import java.util.List;
 
public class HelloWorld {
 
    
    public static void main(String[] args) {
        float[] datasets = {0.897f, 0.156f, 0.565f, 0.556f, 0.656f, 0.1234f, 0.665f, 0.3434f};
        bucketSort(datasets);
 
        for(int i = 0 ; i < datasets.length ; i++) {
            System.out.println(datasets[i] + " ");
        }
    }
 
 
    public static void bucketSort(float[] datasets) {
        // 0-9 bucket list 를 생성.
        List<Float> []buckets = new ArrayList[10];
        for(int i = 0 ; i < datasets.length ; i++) {
 
            int index = (int)(datasets[i]*10);
            if( buckets[index] == null) {
                buckets[index] = new ArrayList<>();
            }
 
            // 일단 맨 뒤에 추가.
            buckets[index].add(datasets[i]);
            insertionSort(buckets[index], datasets[i]);
        }
 
        int c = 0 ;
        for(int i = 0 ; i < 10 ; i++) {
            if(buckets[i] != null) {
                int size = buckets[i].size();
                for (int j = 0; j < size ; j++) {
                    datasets[c++] = buckets[i].get(j);
                }
            }
        }
    }
 
    public static void insertionSort(List<Float> list, float v2) {
 
        int bucketSize = list.size() -1 ;
        int i = 0 ;
        for(i = bucketSize - 2 ; i >= 0 ; i--) {
            float v1 = list.get(i);
            if(list.get(i) < v2)
                break;
            list.set(i+1,  v1);
        }
 
        if(i >= 0 ) {
            list.set(i, v2);
        }
    }
}

 

참고로 버킷정렬이 반드시 부동 소수점 숫자 집합을 정렬해야 하고 싶다고 할때 선택 할 수 있는 정렬의 방법은 아니다 정수형도 가능하다.

그리고 위 코드에서는 삽입정렬(insertion sort)을 사용하여 버킷의 리스트들을 정렬하였는데 다른 정렬 방법을 사용해도 된다.