기수정렬

20 Jan 2021 in Algorithms

알고리즘 설명

**IDEA : ** 숫자를 각 자리끼리 비교해 정렬하는 알고리즘

JAVA 코드

static int[] ary = {122,21,4752,24,563,25,62,2,37,552,13349,76};
public static void main(String[] args) {
    ary=radixSort(ary);
    System.out.println("정렬 후 : " + Arrays.toString(ary));        
}

public static int[] radixSort(int[] ary) {
    //가장 큰수의 자리수 파악
    int dMax=0;
    for(int i : ary) {
        if((i+"").length() > dMax) {
            dMax = (i+"").length();
        }
    }

    System.out.println(dMax);
    int len = ary.length;
    //자리수 관리 변수
    int cur_dig = 1;

    int[] sArray = new int[len];
    int[] ind;

    //p가 직접적으로 사용되지는 않는다. 그냥 루프를 max_len번 돌게함. 
    //그리고 루프 돌때마다 myRadix가 10배가된다. 자리수 끼리 비교하는 작업 수행하는 것임.
    for (int _i = 0; _i < dMax; _i++) {
        ind = new int[10];
        //counts 에는 바깥 루프 맨 처음 돌 때는 1의 자리만 세서 0~9까지 몇개 있는지.
        //두번째 루프 돌 때는 10의 자리 세서. 
        for (int e : ary) {
            ind[(e / cur_dig) % 10]++;
        }
        //누적시킨다. (index로 사용하기 위한 배열)
        for (int i = 1; i < 10; i++)
            ind[i] += ind[i - 1];
        //ind배열을 인덱스로 사용해서 sarray에 넣는다.ary의 요소 뒤에서 부터 확인해 새 배열에 넣음.
        for (int i = len - 1; i >= 0; i--) {
            sArray[ind[(ary[i] / cur_dig) % 10]-- - 1] = ary[i];
        }
        //이게 deep copy가 아니라 이 scope밖에 나가면 ary가 이 스코프 안의 ary와 다른 값을 출력해 보여준다. 
        //그래서 그냥 ary를 반환해서 밖에서 받게함.
        ary = sArray;
        //sorted array 초기화 해준다.
        sArray = new int[len];
        cur_dig *= 10;
    }
    return ary;
}    

PYTHON 코드 - 나중에 첨부

• python을 같이 한 이유는 pythonic한 코드를 공부하려고 해서다. 근데 계속 pythonic한 코드를 익히지 않고, java같은 코드만 짜고있어서 먼저 공부를 한 후 채울 예정이다.