앞서 배운 선택정렬, 삽입정렬, 버블정렬은 쉽고 간단한 알고리즘입니다.
따라서 성능을 더 개선 시키고자 심화된 알고리즘 정렬 방식이 나왔습니다. 계수정렬, 힙정렬, 병합정렬, 기수정렬, 퀵정렬이 있습니다.
이번은 계수정렬 (counting Sort)에 대해서 설명드리도록 할게요.
계수정렬
계수정렬은 정렬되지 않은 숫자들을 가지고 횟수를 셉니다. 각 숫자별로 횟수들의 합을 구하여 누적합니다.
누적 된 숫자를 인덱스로하여 삽입하고 누적 숫자를 감소시킵니다. 계수정렬의 특징은 뒤에서부터 앞으로 정렬 배열에 넣습니다.
즉 누적된 숫자가 정렬 배열에 들어갈 위치입니다.
제가 그려본 예로 한번 봅시다.
우선 정렬 되지 않은 숫자(not_Sort): 1 3 2 2 4
*인덱스는 1부터 시작
|
인덱스 |
1 |
2 |
3 |
4 |
5 |
|
숫자 |
1 |
3 |
2 |
2 |
4 |
이런 식으로 있습니다.
우선 횟수를 세는 함수를 통해 각 숫자의 출현 횟수를 구합니다. process
|
숫자 |
1 |
2 |
3 |
4 |
|
등장 횟수 |
1 |
2 |
1 |
1 |
|
숫자 |
1 |
2 |
3 |
4 |
|
누적 합 |
1 |
3 |
4 |
5 |
이렇게 됩니다.
위에서 얘기했듯이 뒤에서부터 앞으로 탐색을 합니다. 따라서 계수정렬 알고리즘에 의해서
- 숫자 4는 누적 합이 인덱스이므로 5가 인덱스가 됩니다. 따라서 숫자 4는 인덱스 5로 갑니다. 이때 누적 합 5->4로 1 감소시킵니다.
- 숫자 3은 누적 합이 인덱스이므로 4가 인덱스가 됩니다. 따라서 숫자 3은 인덱스 4로 갑니다. 이때 누적 합 4->3으로 1감소시킵니다.
.
.
.
이렇게 반복을 하는 정렬이 계수정렬입니다.
계수정렬.c
<코드>
main
우선 변수들은 주석처리 했기 때문에 이해하실 겁니다.
수열 총 길이를 우선적으로 입력받습니다. size변수에 저장이 될겁니다.
appear_count함수는 횟수를 세주는 함수로 이함수에 매개변수로 전달하여 함수를 실행시킵니다.
결과는 cnt에 횟수가 저장됩니다.
이것이 바로 appear_count함수입니다.
appear_count 출현횟수 함수
cnt를 초기화 시키고 1부터 n까지 숫자를 정렬되지 않은 배열 not_Sort배열에 입력합니다.
그리고 그 입력된 배열의 값을 인덱스로 해서 cnt횟수를 증가시킵니다.
숫자가 같으면 인덱스가 같기때문에 횟수는 증가하겠지요~~
그다음 sum_count를 통해 누적 합을 구합니다.
이것이 바로 누적함수입니다.
누적 함수 sum_count
이 함수는 누적 횟수의 합입니다.
전의 숫자를 더하는 피보나치 수열과 원리는 비슷합니다.
전의 숫자를 더해주는 원리죠.
sum의 전 숫자+횟수
메인 함수의 계수 알고리즘
이 알고리즘은 계수정렬 할때 꼭 필요한 부분입니다.
위에서 말씀 드린 것 처럼 뒤에서 앞으로 탐색을 하여
for문이 size부터 1씩 감소합니다.
done_sort 정렬 할 배열에 정렬 되지않은 배열 not_sort배열을 집어 넣습니다.
이때 done_sort의 인덱스는 누적 횟수의 합입니다!!!
그리고 1을 감소시킵니다.
이것으로 계수정렬에 대해 설명드렸습니다.
다
