Radix Sort의 정의로 예제

소개글

Radix Sort의 정의로 예제에 대한 보고서 자료입니다.

목차

Radix Sort

◎Radix Sort란
◎Radix Sort의 정렬 방법
◎Radix Sort의 예
◎기수 정렬 알고리즘
◎예제1
◎예제2
◎Radix Sort 알고리즘의 분석

본문내용

10 나눈 수로 나눈다 -> 그 자리의 수만 구함
key = ++tmpSave[tmp][0]; // 첫 번째 자리는 입력된 수의 카운팅
tmpSave[tmp][key] = toSort[j];
// 입력된 수의 카운터를 키로 삼아 그 자리에 값을 저장
}
tmp = 0; // 원래 배열의 위치
for ( j = 0 ; j < 10 ; j++ ) { // tmpSave 의 행을 돈다
for ( k = 0 ; k < tmpSave[j][0] ; k++ ) {
// tmpSave 의 각 행의 첫 번째 자리의 값만큼 루프
toSort[tmp] = tmpSave[j][k+1]; // 두 번째 자리의 값부터 원래 배열에 저장
tmp++;
}
}
for ( j = 0 ; j < 10 ; j++ ) { // tmpSave 를 비워준다.
for ( k = 0 ; k < SIZE + 1 ; k++ ) {
tmpSave[j][k] = 0;
}
}
printf("%5d 자리의 정렬 : ", i / 10);
displayArray(toSort, SIZE);
}
printf("\n 정렬 완료 데이터 : ", i / 10);
displayArray(toSort, SIZE);
printf("\n");
return 0;
}
void toArray(int toArray[], int size, int maxsize) {
int i;
for (i = 0 ; i < size ; i++ ) {
toArray[i] = rand() % maxsize + 1;
}
}
void displayArray(int toArray[], int size) {
int i;
for (i = 0 ; i < size ; i++ ) {
printf("%6d", toArray[i]);
}
printf("\n");
}
*예제2 결과값
정렬 안된 데이터 : 29618 24269 10964 29096 25508 9402 7438 16189 15709 16998
1 자리의 정렬 : 9402 10964 29096 29618 25508 7438 16998 24269 16189 15709
10 자리의 정렬 : 9402 25508 15709 29618 7498 10964 24269 16189 29096 16998
100 자리의 정렬 : 29096 16189 24269 9402 7438 25508 29618 15709 10964 16998
1000 자리의 정렬 : 10964 24269 25508 15709 16189 16998 7438 29096 9402 29618
10000 자리의 정렬 : 7438 9402 10964 15709 16189 16998 24269 25508 29096 29618
정렬 완료 데이터 : 7438 9402 10964 15709 16189 16998 24269 25508 29096 29618
Radix Sort 알고리즘의 분석
1)실제 실험을 해보진 않았지만 제약이 있는 sort이긴 하지만 퀵소트 보다도 빠른 성능을 보인다
2)시간 복잡도가 O(n)이라고 생각할 수 있기 때문인 듯 하다.

키워드

C언어,   Radix Sort,   Radix Sort 예제,   C+,   요점정리,   레포트