radix.cpp

목차

radix.cpp 1.52KB

본문내용

#include
#include
#define MAX 1000 //1000개 이하의 숫자만 radix sort가능하다고 가정

int bins[10][MAX];
int tails[10] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

void push(int digit, int key){

bins[digit][++tails[digit]] = key; //key는 바구니에 들어갈 그 정수를 가르킨다
}

void collect(int A[]){

int i, j;
int k = 0;

for(i=0; i<10; i++){
if(tails[i] != -1){ //tails에 -1보다 큰 수가 들어있다면 그 자릿수에 숫자가 있다는 것이기 때문에 배열A로 옮기기 시작
for(j=0; j A[k] = bins[i][j];
k++;
}
tails[i] = -1; //다시 tail을 -1로 reset
}
}
}

키워드

알고리즘,   sort,   radix