자료구조 counting정렬 c언어구현

1. 100개의 공간을 가지는 배열 a[100]을 선언하고, 100이하의 정수를 랜덤으로 100개를 할당하라(아래 예시).

2. Fast transpose의 row_terms 배열에 a의 항목들의 개수를 채워 넣고, 이를 이용하여 starting_pos 배열을 계산한다.

3. 이제 배열 a의 각 항목을 읽어 면서 해당 위치를 찾아서 sort 배열에 저장한다.

a) a[0]인 9을 읽어서 starting_pos[9]++인 7번 위치에 저장

b) a[1]인 8을 읽어서 starting_pos[8]++인 6번 위치에 저장

c) 이와 같은 방식으로 계속 진행하면 a 배열의 항목들이 sorted 배열에 정렬되게 된다.

4. 위와 같은 정렬 방식을 Counting Sort라 한다(나중에 이 정렬 방식을 이용해서 Radix Sort 알고리즘이 구현된다).