기수정렬 보고서

소개글

Dev c++, Visual studio

목차

1. 알고리즘

2. 구현 방법
2-1 데이터의 범위
2-2 입출력 형식
2-3 토대가 되는 방식
2-4 최종 구현 내용

3. 소스코드

본문내용

1. 알고리즘
기수 정렬(radix sort)은 낮은 자릿수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 O(dn)이다. (d는 가장 큰 데이터의 자릿수)

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 O(dn)이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만 한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

입력한 수열은 몇 개의 키로 분류된다. 예를 들어, 3자리이하 수라면, 1의 자리, 10의 자리, 100의 자리로 나누어 분류된다. 각각의 키에 대해 하위키부터 정렬한다.

<중 략>

2. 구현 방법
2-1 데이터의 범위
1~999까지의 난수 1000개를 이용하여 기수 정렬을 실행한 후, 정렬된 수들을 메모장에 저장하도록 하였다. 다음은 난수를 발생시키는 함수이다.

void generate(int arr[]){
int i;
srand(time(NULL));
printf("Random array : \n");
for(i=0; i < NU; i++){
arr[i] = (rand() % 999) + 1;
}
}

이 함수에는 srand 함수와 rand 함수가 이용되었다.
프로그램을 구현하다 보면 난수(Random Number)를 발생시켜야 하는 경우가 종종 있다. 여기서 말하는 난수란 임의의, 정해지지 않은, 무엇이 될지 모르는 수를 의미한다. 그런데 다행인 것은 ANSI 표준에서 난수를 생성할 때 호출할 수 있는 다음 함수를 제공하고 있다는 것이다.
#include
int rand(void); // 의사 난수를 반환

ANSI 표준에서는 이렇게 난수를 생성할 때 사용할 수 있는 함수 rand를 제공하고 있다. 이 함수의 사용방법은 다음과 같다.

참고 자료

없음