계수정렬(Counting Sort)
크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘이다.
각 데이터의 크기를 기준으로 분류하므로 O(N)의 시간 복잡도를 갖는다.
데이터의 크기를 할당해준 뒤 처리해야 하기 때문에 데이터의 크기가 한정적일 때 사용할 수 있다.
계수정렬의 처리방법은 배열의 인덱스를 기준으로 각 원소의 개수를 파악하고 그 개수만큼 출력하는 방식이다.
계수정렬의 특징은 퀵정렬이나 다른 정렬 알고리즘에 비해서 보다 많은 메모리를 요구하는 대신에 빠른 처리가
가능하다는 효율성을 제공한다는 것이다.
처리방법
예를들어 2 1 0 2 2 1 3 1 0 3 이라는 데이터를 계수정렬로 처리한다고 할 때
값과 동일한 인덱스에 개수를 원소값으로 넣어주는 것이다.
정리하면 다음과 같다.
| 인덱스 | 0 | 1 | 2 | 3 |
| 원소 | 2 | 3 | 3 | 2 |
데이터의 끝까지 다 확인해서 개수를 파악했다면 0번 인덱스부터 출력을 시작해서
0 0 1 1 1 2 2 2 3 3 형태로 출력하게 된다.
예제코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_VALUE 10001
int n, m;
int a[MAX_VALUE];
int main(void){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &m);
a[m]++;
}
for(int i = 0; i < MAX_VALUE; i++){
while(a[i] != 0){
printf("%d ", i);
a[i]--;
}
}
system("pause");
}n에는 값의 개수를 넣어준다. 예제대로라면 10개의 값을 넣어주기 때문에 n은 10을 입력하고
2 1 0 2 2 1 3 1 0 3을 입력해준다.
값의 개수를 넣어주는 것은 입력값처리를 좀 더 편하게 하기 위한 것 뿐이다.
값을 입력하는 반복문의 과정에서 값을 넣어준 뒤 a배열에서 값과 같은 인덱스에 원소값을 하나 증가시켜준다.
첫 값인 2가 들어왔다면 m은 2가 되므로 a[2]의 값을 ++로 하나 증가시켜 주는것이다.
그럼 a[2]는 1이 되고 처리과정을 반복하다가 네번째 값에서 2가 또 나오는데 이때 또 a[2]++을 해주게 된다면
a[2]가 2가 되는 형태다.
그렇게 반복문을 다 처리 해준다면 위 처리방법에서의 형태처럼 처리가 된다.
즉, 첫 반복문에서 값의 입력과 정렬을 같이 처리하게되는 셈이다.
출력문에서는 MAX_VALUE를 이용해서 배열의 전체를 훑고 원소값이 0이 아닌 배열을 출력하도록 한다.
원소값이 0이 아닐 경우에는 한번 출력을 한 뒤 해당 인덱스의 값을 하나 감소시켜서 또 출력하는 형태로
값이 0이 될때까지 반복해준다.
MAX_VALUE의 값이 10001로 되어있고 a배열의 크기가 MAX_VALUE이므로 정렬하고자하는 최대값으로는 10000
이상을 넣을 수 없다.
만약 MAX_VALUE의 값을 101로 해두었다면 마찬가지로 정렬하고자하는 최대값은 100이상이 될 수 없다.
기수정렬(Radix Sort)
자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘이다.
각 데이터를 자릿수 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 대 O(DN)의 시간 복잡도를 갖는다.
일반적으로 자릿수가 10개를 넘어가면 억단위를 넘어가기 때문에 왠만해서는 D는 그렇게 큰 값이 아니도록 형성이
된다.
그래서 O(DN)은 N에 가까운 시간 복잡도를 갖기 때문에 계수정렬만큼 빠른 알고리즘이라고 할 수 있다.
자리수의 개수만큼 N번 반복한다.
일반적으로 100의 자리 1000의 자리 이런식으로 작은 자리수는 D가 3정도밖에 안되기 때문에 사실상 N이라고 볼 수
있을 정도로 빠르다.
계수정렬보다 약간 더 느리지만 숫자가 매우 큰 상황에서도 사용할 수 있다.
처리방법
7 84 25 341 65 30 34 라는 값을 정렬하고자 한다면
1의 자리수부터 시작하는데 계수정렬할때처럼 배열형태로 정렬해준다.
위의 값들을 1의자리만 본다면
7 4 5 1 5 0 4 가 되므로 계수정렬한것처럼 정리한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 1 | 0 | 0 | 2 | 2 | 0 | 1 | 0 | 0 |
여기서 각 원소값을 누적형태로 바꿔준다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 2 | 0 | 0 | 4 | 6 | 0 | 7 | 0 | 0 |
이렇게 누적형태로 정리하고 난 뒤에는 값을 정렬해주게 되는데 정렬하는 순서는 뒤에서 앞으로 처리한다.
7 84 25 341 65 30 34 의 값을 정렬하기 시작하면 제일 뒤에 있는 34부터 시작하게 된다.
34는 1의 자리수가 4이고 4번 인덱스의 값은 4이다.
그럼 34의 위치는 4가 되는데 이때 4의 위치는 0부터 시작하는 배열상 4의 위치가 아닌 1부터 시작한 위치에서 4이다.
이렇게 값을 위치해주면서 자리수 배열 내에서는 4번 인덱스의 값을 하나 감소시켜준다.
| 34 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 2 | 0 | 0 | 3 | 6 | 0 | 7 | 0 | 0 |
이런 형태가 된다. 다음 값인 30을 정렬할때는 1의자리가 0이었기 때문에 0인덱스의 값인 1번 위치에 넣어주고
마찬가지로 0번인덱스의 원소값을 하나 감소시킨다.
| 30 | 34 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 2 | 0 | 0 | 3 | 6 | 0 | 7 | 0 | 0 |
전부 정렬하면 아래와 같은 형태가 된다.
| 30 | 341 | 84 | 34 | 25 | 65 | 7 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 1 | 0 | 0 | 2 | 4 | 0 | 6 | 0 | 0 |
여기서 인덱스의 원소값을 보면 0이 아닌 값들이 있지만 신경써야하는 부분이 아니다.
여기까지가 1의자리수를 이용한 정렬이다.
여기서 최대값인 341은 100의자리까지 있기 때문에 10의자리, 100의자리를 이용한 정렬을 해줘야 한다.
다음으로는 10의자리를 이용한 정렬이다.
1의자리때와 마찬가지로 자릿수 값에 대한 누적값을 구해줘야 한다.
| 30 | 341 | 84 | 34 | 25 | 65 | 7 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 0 | 1 | 2 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 0 | 2 | 4 | 5 | 0 | 6 | 0 | 7 | 0 |
이렇게 누적값까지 구하고 나면 1의자릿수에서 정렬한것과 같은 방법으로 정렬한다.
똑같이 맨 뒤의 값 부터 정렬을 시작하게 되고 7은 10의자리수가 0이기 때문에 0인덱스의 원소값처럼 1번째에
위치하고 마찬가지로 누적값에서 해당 인덱스의 값을 하나 감소시킨다.
| 7 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 2 | 4 | 5 | 0 | 6 | 0 | 7 | 0 |
위와 같은 방법으로 전부 정렬하면 다음과 같다.
| 7 | 25 | 30 | 34 | 341 | 65 | 84 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 1 | 2 | 4 | 0 | 5 | 0 | 6 | 0 |
마지막으로 100의자리를 정렬한다.
지금까지와 마찬가지로 10의자리에서 정렬한 값을 가져와서 사용한다.
| 7 | 25 | 30 | 34 | 341 | 65 | 84 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 6 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 6 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 | 0 |
누적값을 구했으니 같은 방법으로 뒤에서부터 정렬한다.
그럼 84는 6번째, 65는 5번째, 341은 7번째, 34는 4번째, 30은 3번째 이렇게 정렬해준다.
| 7 | 25 | 30 | 34 | 65 | 84 | 341 |
그럼 이렇게 정렬되게 되고 1000의 자리는 없기 때문에 정렬이 끝나게 된다.
예제코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 10000
void radixSort(int *a, int n){
int res[MAX], maxValue = 0;
int exp = 1;
for(int i = 0; i < n; i++){
if(a[i] > maxValue) maxValue = a[i];
}
while(maxValue / exp > 0){
int bucket[10] = { 0 };
for(int i = 0; i < n; i++) bucket[a[i] / exp % 10]++; //자릿수 배열처리
for(int i = 0; i < 10; i++) bucket[i] += bucket[i - 1]; //누적 처리
for(int i = n - 1; i >= 0; i--){
res[--bucket[a[i] / exp % 10]] = a[i];
}
for(int i = 0; i < n; i++) a[i] = res[i]; //기본 배열 갱신
exp *= 10;
}
}
int main(void){
int a[MAX];
int i, n;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
radixSort(a, n);
for(i = 0; i < n; i++){
printf("%d ", a[i]);
}
system("pause");
}n에 입력할 값의 개수를 입력하고 그만큼 반복문을 돌려 리스트에 값을 넣어준다.
radixSort에 리스트와 값의 개수인 n을 넘겨준다.
radixSort함수의 첫 반복문에서는 리스트를 전체 다 훑으며 가장 큰 값을 찾아 maxValue에 넣어준다.
while문에서 maxValue / exp를 하는데 자릿수를 확인하는 것이다.
처음 체크한다면 1의자리는 당연히 존재하니까 0보다 크겠지만 위 예제처럼 100의자리까지만 있는 값이라면
자릿수 정렬 후 exp가 1000이 되었을 때 값이 0보다 작아지게 되고 그럼 1000의자리수는 존재하지 않는다는 의미가
된다.
while안의 첫 for문에서는 자릿수의 배열처리를 한다. exp 뒤에 % 10으로 나머지를 왜 구하는지 헷갈렸었는데
꼭 구해야한다.
예를들어 a[i]가 84라고 하고 exp가 아직 1이라고 했을 때 84/1 = 84이다. 하지만 exp가 1이라는 것은
1의 자리수를 이용한 정렬을 하고 있는 것이기 때문에 4만 가져와야 한다.
그래서 % 10으로 나머지값을 구해서 원하는 자리수만 가져오기 위함이다.
그리고 뒤에 있는 ++로 해당 인덱스의 원소값을 하나 올려주는 것이고 값의 개수만큼 반복한다.
두번째 for문은 누적값을 계산한다. 처리방법에서 표에 작성했듯이 누적값이 필요한데 그 부분을 처리해주는
반복문이다.
i번 인덱스에 i - 1번 인덱스의 값을 더해라 라는 처리이므로 앞 인덱스의 값을 현재 인덱스에 더하라는 것이다.
세번째 반복문에서 res에 값을 넣어주며 정렬을 하게 되는 것이다.
리스트의 제일 뒤에서부터 시작해서 자리를 찾아가는 과정이 이 부분이다.
마지막 for문은 a배열을 res에 정렬해놓은 배열로 갱신하는 것이다.
그리고 마지막에 exp에 10을 곱해주는데 그래야 10의자리, 100의자리, 1000의 자리를 체크하고 정렬 할 수 있다.
인강에서는 코드에 대한 별 설명이 없이 그냥 슥 넘어가서 이해 안되는 부분들이 있었다.
그래서 출력문을 중간중간 적어주면서 이해했다 ㅠㅠ
아래코드가 출력문 다 적어둔 코드...
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 10000
void radixSort(int *a, int n) {
int res[MAX], maxValue = 0;
int exp = 1;
for (int i = 0; i < n; i++) {
if (a[i] > maxValue) maxValue = a[i];
}
while (maxValue / exp > 0) { //자릿수 체크
int bucket[10] = { 0 };
for (int i = 0; i < n; i++) { //자릿수 배열처리
bucket[a[i] / exp % 10]++;
printf("bucket first : "); //자릿수 배열처리 과정 출력
for (int j = 0; j < 10; j++) {
printf("%d ", bucket[j]);
}
printf("\n");
}
for (int i = 1; i < 10; i++) { //누적계산
bucket[i] += bucket[i - 1];
printf("bucket accu : "); //누적계산 과정 출력
for (int j = 0; j < 10; j++) {
printf("%d ", bucket[j]);
}
printf("\n");
}
for (int i = n - 1; i >= 0; i--) { //기본 배열 갱신
res[--bucket[a[i] / exp % 10]] = a[i];
printf("res : "); //배열 갱신과정 출력
for (int j = 0; j < 7; j++) {
printf("%d ", res[j]);
}
printf("\n");
}
printf("a prev : "); //정렬 전 배열
for (int j = 0; j < n; j++) {
printf("%d ", a[j]);
}
printf("\n");
for (int i = 0; i < n; i++) {
a[i] = res[i];
}
printf("check : "); //갱신된 배열
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
exp *= 10;
}
}
int main(void) {
int a[MAX];
int i, n;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
radixSort(a, n);
printf("final : ");
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
system("pause");
}
레퍼런스
패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직