기수정렬
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같은 코드만 짜고있어서 먼저 공부를 한 후 채울 예정이다.