버킷 정렬, 기수 정렬, 병합 정렬

버킷 정렬:

1.입력 배열의 원소들을 해당하는 버킷에 저장

2. 각 버킷을 정렬함.

3. 버킷을 차례로 방문하여 원소들을 원 배열에 저장

 

---

기수 정렬(Radix sort)

 

-높은 자리 우선 정렬(MSD)

-낮은 자리 우선 정렬(LSD) 

가 있음.

이 때 LSD방식은 버킷별로 별도 정렬 단계가 필요 없으므로 MSD보다 많이 사용됨.

 

LSD를 이용한 기수 정렬

입력 데이터에서 가장 큰 숫자를 max라고 할 때,

입력 데이터를 일의자리 수부터, max의 최대자릿수까지,한 값을 기준으로 삼아 차례대로 counting sort를 반복한다.

 

public class Radix {
    public static void sort(int[] A){
        int i,m = A[0], exp=1, n=A.length;
        int[] B = new int[n]; //각 기수의 정렬 결과를 저장할 배열

        for(i=1;i<n;i++){
            if(A[i]>m) m=A[i]; //최댓값을 검색
        }

        while(m/exp >0){ //1의 자리부터 계수정렬 시작
            int[] C = new int[10];
            for(i=0;i<n;i++)    C[(A[i]/exp)%10]++;
            for(i=1;i<10;i++)   C[i]+=C[i-1];
            for(i=n-1;i>=0;i--)   B[--C[(A[i]/exp)%10]]=A[i];
            for(i=0;i<n;i++){
                A[i]=B[i]; //옮기기
            }
            exp*=10;//다음자릿수 이동
        }
    }
    public static void main(String[] args){
        int[] A = {10,20,90,23,4,2,2,503,30,2};
        Radix.sort(A);
        for(int i=0;i<A.length;i++){
            System.out.print(A[i]+" ");
        }
    }
}

---

병합 정렬.

 

병합 방법에 따라

1. 별도의 배열 이용

2. 제자리 병합(In-place merge)

 

정렬의 방법에 따라

1. Top-down

2. Bottom-up

 

방식으로 나눌 수 있다.

 

제자리 병합은 복잡하고 느리기 때문에, 별도의 배열을 이용하는 방법을 쓰도록 하자

.

import java.util.concurrent.ConcurrentMap;

public class Merge extends AbstractSort{

    //새 배열을 이용해서 병합하는 경우.
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi){
        for(int k=lo; k<=hi; k++){
            aux[k]=a[k]; //aux에 a를 복사
        }

        int i=lo, j=mid+1;
        for(int k=lo ; k<=hi; k++){
            if(i > mid)     a[k] = aux[j++]; //i가 끝난 경우는 j것만 옮김
            else if(j>hi)   a[k] = aux[i++]; //j가 끝난 경우는 i것만 옮김
            else if(less(aux[j],aux[i]))    a[k] = aux[j++];//j가 작은경우 j를 넣고
            else    a[k]=aux[i++];  //둘이 같거나 i가 작으면 i를 넣음

        }
    }

    public static void sortTD(Comparable[] a){
        //탑다운소트
        Comparable[] aux = new Comparable[a.length]; //aux배열 생성
        sortTD(a,aux,0,a.length-1);
    }
    public static void sortTD(Comparable[] a, Comparable[] aux,int lo,int hi){
        if(hi <= lo )   return; //데이터가 1개라서 더이상 못 나누는 경우
        int mid = lo + (hi-lo)/2; //중간
        sortTD(a,aux,lo,mid);
        sortTD(a,aux,mid+1,hi);
        merge(a,aux,lo,mid,hi);
    }

    public static void main(String[] args) {
        Integer[] a= {2,4,53,6,3,2,3,5,1,5,6,3};
        Merge.sortTD(a);
        Merge.show(a);
    }
}

이것은 탑다운방식 병합정렬이다.

위에서부터 반씩 잘게 쪼개고..

다 쪼갠다음 하나씩 붙여나감..

 

    public static void sortBU(Comparable[] a){
        Comparable[] src = a, dst = new Comparable[a.length],tmp;
        int N= a.length;
        for(int n=1;n<N;n*=2){//n==병합할 부분 배열 크기
            for(int i=0;i<N;i+=2*n)//i==병합할 부분 배열의 위치
            {
                mergeBU(src,dst,i,i+n-1,Math.min(i+2*n-1,N-1));
            }
            tmp=src; src=dst; dst=tmp;
        }
        if(src!=a)  System.arraycopy(src,0,a,0,N);
    }
    public static void mergeBU(Comparable[] in, Comparable[] out,int lo,int mid,int hi){
        int i=lo, j=mid+1;
        for(int k=lo;k<=hi;k++){
            if(i>mid)   out[k]=in[j++];
            else if(j>hi)   out[k]=in[i++];
            else if(less(in[j],in[i]))  out[k]=in[j++];
            else    out[k]=in[i++];
        }
    }

병합정렬 바텀업.

처음부터.. 1쌍씩 짝지어서 병합시작함.