버킷 정렬

소스코드

import java.util.Arrays;

public class test{

    public static void testsort(int[] a, int maxVal) {
        int [] bucketArr=new int[maxVal];


        //버킷사이즈에다가 0으로 초기화시켜준다.
        for (int i=0; i<bucketArr.length; i++) {
            bucketArr[i]=0;
        }
        //입력 리스트의 숫자마다 버킷의 값들을 ++시켜준다.
        for (int i=0; i<a.length; i++) {
            bucketArr[a[i]]++;
        }

        //버킷의 길이 만큼 돌린다음 그 안에 가진 값들 만큼을 돌려준다.
        int outPos=0;
        for (int i=0; i<bucketArr.length; i++) {
            for (int j=0; j<bucketArr[i]; j++) {
                a[outPos++]=i;
            }
        }
    }

    public static void main(String[] iargs) {
        int [] myArr= {5,3,0,2,4,1,0,5,2,3,1,4,6,7,8,9,11,12,13,14,15,99};
        int max=0;
        for(int i=1 ; i<myArr.length ; i++) {
            if(myArr[i]>max) {
                max = myArr[i];
            }
        }

        System.out.println("Before: " + Arrays.toString(myArr));
        long beforeTime = System.currentTimeMillis();
        testsort(myArr,max);
        long afterTime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime)/60;
        System.out.println("After:  " + Arrays.toString(myArr));
        System.out.println("Time :  "+secDiffTime);
    }
}

 

장단점

버킷정렬의 기본전제는 균등하게 배분이 되어 있다는 점이다. 1-100까지의 숫자 범위중에 리스트[55,52,54,68,88,1,57,58] 이런식으로 들어가면 버킷을 10의 범위씩으로 생각을 하면 1-10까지의 버킷에는 1이 들어가고 11-20까지는 0개 21-30까지는 0개 쭉가다가 41-50은 0개 51-60까지는 5개가 들어간다고 쳤을 때 각각의 버킷에는 균등하게 들어가는게 아니여서 효율적이지는 않다. 균등하게 들어가면 시간복잡도를 O(1)에 정렬을 시킨는 과정을 N번을 해야하니 시간복잡도는 O(N)이라는 결과가 나온다. 하지만 균등하지않다면 버킷안에서의 정렬시간이 O(1)이 넘어갈수 있다.