<기수 정렬 구현>
https://github.com/sevenshards00/DataStructure_C/tree/master/Ch10-Sorting/RadixSort
기존에 작성했던 리스트 기반의 큐를 활용.
여기서 큐는 기수 정렬의 버킷(Bucket)으로 사용하기 위해서 쓰였다.
[RadixSort.c]
/*
* 알고리즘 - 기수 정렬(Radix Sort)
* 파일명: RadixSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-27
* 이전 버전 작성 일자:
* 버전 내용: 간단한 기수 정렬(LSD, Least Significant Digit) 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include "ListBaseQueue.h"
#define BUCKET_NUM 10
void RadixSort(int arr[], int num, int maxLen)
{
// 매개변수 maxLen에는 정렬대상 중 가장 긴 데이터의 길이 정보가 전달
Queue buckets[BUCKET_NUM];
int bucket_idx; // 버킷에 사용할 인덱스
int pos;
int data_idx; // 데이터에 사용할 인덱스
int div_factor = 1; // 자릿수를 구하는데 사용하는 피제수
int radix;
// 10개의 버킷 초기화
for (bucket_idx = 0; bucket_idx < BUCKET_NUM; bucket_idx++)
QueueInit(&buckets[bucket_idx]);
// 가장 긴 데이터의 길이만큼 반복
for (pos = 0; pos < maxLen; pos++)
{
// 버킷에 데이터를 넣는 부분
for (data_idx = 0; data_idx < num; data_idx++)
{
// N번째 자리의 숫자 추출
radix = (arr[data_idx] / div_factor) % 10;
// 추출한 숫자를 근거로 버킷에 데이터를 저장
QEnqueue(&buckets[radix], arr[data_idx]);
}
// 버킷에서 데이터를 추출하는 부분
// 버킷의 수 만큼 반복
for (bucket_idx = 0, data_idx = 0; bucket_idx < BUCKET_NUM; bucket_idx++)
{
// 버킷에 저장된 것을 순서대로 다 꺼내서 다시 arr에 저장
while (!QisEmpty(&buckets[bucket_idx]))
arr[data_idx++] = QDequeue(&buckets[bucket_idx]);
}
// N번째 자리의 숫자 추출을 위해서 피제수의 증가
div_factor *= 10;
}
}
int main()
{
int arr[7] = { 13, 212, 14, 7141, 10987, 6, 15 };
int i;
int len = sizeof(arr) / sizeof(int);
RadixSort(arr, len, 5);
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[기수 정렬의 이해]
기수 정렬의 가장 큰 특징이자 장점은 다음과 같다.
“정렬순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다”
그리고 정렬 알고리즘의 이론상 성능의 한계 알려져 있는 $O(log_2n)$의 한계를 넘어설 수 있는 유일한 알고리즘이다.
세상에 만병통치약은 없는 것처럼 모든게 다 좋을 수는 없는 것이다.
그렇다면 한계를 넘어설 수 있으니 더 좋은게 아닌가 싶겠지만, “적용할 수 있는 범위가 제한적”이라는 것이 단점이다.
예를 들어, 기수 정렬로 해결할 수 있는 문제는 다음과 같다.
“배열에 저장된 1, 7, 9, 5, 2, 6을 오름차순으로 정렬하라.”
“영단어 red, why, zoo, box를 사전에 편찬된 순서대로 정렬하라”
그리고 이런 문제는 해결할 수가 없다.
“배열에 저장된 21, -9, 125, 8, -136, 45를 오름차순으로 정렬하라”
“영단어 professionalism, few, hydroxyproline, simple을 사전에 편찬된 순서대로 정렬하라.”
적용할 수 있는 범위가 제한적이라는 말은, 다시 말하면 데이터의 길이가 같은 대상에 한해서만 정렬이 가능하다는 것.
길이가 같지 않은 데이터를 대상으로는 정렬이 불가능한 것이 기수 정렬의 단점이자 한계이다.
엄밀히 따지면, -999~+999 까지 기수 정렬의 대상이 될 수 있다.
하지만, 이런 경우에는 데이터의 가공을 위한 별도의 알고리즘이 필요하다.
그리고 별도의 알고리즘 적용으로 인한 효율의 문제도 고민할 필요가 있다.
그래서 “정렬이 불가능하다”라는 말은 정말로 불가능한 것이 아니라, 다음과 같이 생각해야 한다.
“별도의 알고리즘을 고민하고 효율의 문제까지 감수해가면서 기수 정렬을 사용해야 하는가?”
효율적이지 못하기에 하지 않는 것이지, 불가능한 것은 아니라는 것.
[기수 정렬의 원리]
기수(radix): 주어진 데이터를 구성하는 기본 요소.
2진수라면 0과 1이 기수, 10진수라면 0~9가 기수, 16진수라면 0~F까지가 기수다.
버킷(bucket): 해당 기수를 담기 위한 양동이. 기수의 수만큼 버킷이 있어야 한다.
1) LSD (Least Significant Digit) - 덜 중요한 자릿수(낮은 자릿수)부터 정렬을 진행
쉽게 말하면, 가장 낮은 자릿수부터 시작해서 정렬을 진행해나가는 방식.
마지막 자릿수까지 진행해야 정렬이 종료된다.
LSD의 단점은 위의 특징과 같다.
“작은 자릿수에서부터 시작해서 가장 큰 자릿수까지 모두 진행이 되어야 값의 대소를 판단할 수 있다.
그러므로 정렬을 진행하는 중간에 값의 대소를 판단하는 것은 불가능하다.”
2) MSD (Most Significant Digit) - 가장 중요한 자릿수(높은 자릿수)부터 정렬을 진행
쉽게 말하면, 가장 높은 자릿수부터 시작해서 정렬을 진행해나가는 방식.
마지막 자릿수까지 진행하지 않아도 정렬이 끝날 수 있다.
다시 말해서, “반드시 끝까지 정렬을 진행하지 않더라도 중간에 정렬이 완료될 수도 있다”는 것이 장점이 된다.
마지막까지 정렬을 진행하지 않고도 끝이 날 수도 있지만, 다음과 같은 단점이 있다.
“모든 데이터에 일괄적인 과정을 거치게 할 수 없다”
이는 가장 높은 자릿수에서 우선순위가 정렬이 되었는데, 다음 자릿수의 정렬을 진행하면서 잘못될 수 있다.
예를 들면 이런 경우다.
(1) 3 4 → 1 (3) 4 → 1 2 (2) → (의미없는 결과)
(2) 2 4 → 1 (2) 2 → 2 2 (4) → (의미없는 결과)
(2) 3 2 → 2 (2) 4 → 1 3 (4) → (의미없는 결과)
(1) 2 2 → 2 (3) 2 → 2 3 (2) → (의미없는 결과)
다시 말해서 정렬을 수행하는 중간에 데이터를 점검해야 하는 단점이 있다.
이는 LSD에 비해서 구현의 난이도가 올라가게 되고, 중간에 데이터의 점검으로 인한 성능의 저하가 생길 수도 있다.
[기수 정렬의 성능 평가]
기수 정렬은 비교 연산을 진행하지 않고 정렬을 수행한다.
버킷으로 데이터의 삽입과 추출만 반복하여 정렬을 하기 때문에, 삽입과 추출의 빈도수로 시간 복잡도를 계산할 수 있다.
삽입과 추출은 데이터의 양만큼 $n$회 수행하므로 각각이 $O(n)$이다.
이 둘을 합하면 $O(2n)$이지만, 빅-오에서는 앞의 계수에는 신경쓰지 않으므로 삽입과 추출을 합치면 $O(n)$이 된다.
데이터의 길이만큼 삽입과 추출을 반복하므로 데이터의 길이가 $l$이라고 하면, 전체적인 시간복잡도는 $O(ln)$이 된다.
그래서 다른 정렬 알고리즘의 한계를 넘어설 수 있는 성능을 보이는 것은 사실이다.
하지만, 적용 가능한 대상이 매우 제한적이라는 단점을 고려해야 한다.
<기수 정렬 구현>
https://github.com/sevenshards00/DataStructure_C/tree/master/Ch10-Sorting/RadixSort
기존에 작성했던 리스트 기반의 큐를 활용.
여기서 큐는 기수 정렬의 버킷(Bucket)으로 사용하기 위해서 쓰였다.
[RadixSort.c]
/*
* 알고리즘 - 기수 정렬(Radix Sort)
* 파일명: RadixSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-27
* 이전 버전 작성 일자:
* 버전 내용: 간단한 기수 정렬(LSD, Least Significant Digit) 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include "ListBaseQueue.h"
#define BUCKET_NUM 10
void RadixSort(int arr[], int num, int maxLen)
{
// 매개변수 maxLen에는 정렬대상 중 가장 긴 데이터의 길이 정보가 전달
Queue buckets[BUCKET_NUM];
int bucket_idx; // 버킷에 사용할 인덱스
int pos;
int data_idx; // 데이터에 사용할 인덱스
int div_factor = 1; // 자릿수를 구하는데 사용하는 피제수
int radix;
// 10개의 버킷 초기화
for (bucket_idx = 0; bucket_idx < BUCKET_NUM; bucket_idx++)
QueueInit(&buckets[bucket_idx]);
// 가장 긴 데이터의 길이만큼 반복
for (pos = 0; pos < maxLen; pos++)
{
// 버킷에 데이터를 넣는 부분
for (data_idx = 0; data_idx < num; data_idx++)
{
// N번째 자리의 숫자 추출
radix = (arr[data_idx] / div_factor) % 10;
// 추출한 숫자를 근거로 버킷에 데이터를 저장
QEnqueue(&buckets[radix], arr[data_idx]);
}
// 버킷에서 데이터를 추출하는 부분
// 버킷의 수 만큼 반복
for (bucket_idx = 0, data_idx = 0; bucket_idx < BUCKET_NUM; bucket_idx++)
{
// 버킷에 저장된 것을 순서대로 다 꺼내서 다시 arr에 저장
while (!QisEmpty(&buckets[bucket_idx]))
arr[data_idx++] = QDequeue(&buckets[bucket_idx]);
}
// N번째 자리의 숫자 추출을 위해서 피제수의 증가
div_factor *= 10;
}
}
int main()
{
int arr[7] = { 13, 212, 14, 7141, 10987, 6, 15 };
int i;
int len = sizeof(arr) / sizeof(int);
RadixSort(arr, len, 5);
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
[기수 정렬의 이해]
기수 정렬의 가장 큰 특징이자 장점은 다음과 같다.
“정렬순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다”
그리고 정렬 알고리즘의 이론상 성능의 한계 알려져 있는 $O(log_2n)$의 한계를 넘어설 수 있는 유일한 알고리즘이다.
세상에 만병통치약은 없는 것처럼 모든게 다 좋을 수는 없는 것이다.
그렇다면 한계를 넘어설 수 있으니 더 좋은게 아닌가 싶겠지만, “적용할 수 있는 범위가 제한적”이라는 것이 단점이다.
예를 들어, 기수 정렬로 해결할 수 있는 문제는 다음과 같다.
“배열에 저장된 1, 7, 9, 5, 2, 6을 오름차순으로 정렬하라.”
“영단어 red, why, zoo, box를 사전에 편찬된 순서대로 정렬하라”
그리고 이런 문제는 해결할 수가 없다.
“배열에 저장된 21, -9, 125, 8, -136, 45를 오름차순으로 정렬하라”
“영단어 professionalism, few, hydroxyproline, simple을 사전에 편찬된 순서대로 정렬하라.”
적용할 수 있는 범위가 제한적이라는 말은, 다시 말하면 데이터의 길이가 같은 대상에 한해서만 정렬이 가능하다는 것.
길이가 같지 않은 데이터를 대상으로는 정렬이 불가능한 것이 기수 정렬의 단점이자 한계이다.
엄밀히 따지면, -999~+999 까지 기수 정렬의 대상이 될 수 있다.
하지만, 이런 경우에는 데이터의 가공을 위한 별도의 알고리즘이 필요하다.
그리고 별도의 알고리즘 적용으로 인한 효율의 문제도 고민할 필요가 있다.
그래서 “정렬이 불가능하다”라는 말은 정말로 불가능한 것이 아니라, 다음과 같이 생각해야 한다.
“별도의 알고리즘을 고민하고 효율의 문제까지 감수해가면서 기수 정렬을 사용해야 하는가?”
효율적이지 못하기에 하지 않는 것이지, 불가능한 것은 아니라는 것.
[기수 정렬의 원리]
기수(radix): 주어진 데이터를 구성하는 기본 요소.
2진수라면 0과 1이 기수, 10진수라면 0~9가 기수, 16진수라면 0~F까지가 기수다.
버킷(bucket): 해당 기수를 담기 위한 양동이. 기수의 수만큼 버킷이 있어야 한다.
1) LSD (Least Significant Digit) - 덜 중요한 자릿수(낮은 자릿수)부터 정렬을 진행
쉽게 말하면, 가장 낮은 자릿수부터 시작해서 정렬을 진행해나가는 방식.
마지막 자릿수까지 진행해야 정렬이 종료된다.
LSD의 단점은 위의 특징과 같다.
“작은 자릿수에서부터 시작해서 가장 큰 자릿수까지 모두 진행이 되어야 값의 대소를 판단할 수 있다.
그러므로 정렬을 진행하는 중간에 값의 대소를 판단하는 것은 불가능하다.”
2) MSD (Most Significant Digit) - 가장 중요한 자릿수(높은 자릿수)부터 정렬을 진행
쉽게 말하면, 가장 높은 자릿수부터 시작해서 정렬을 진행해나가는 방식.
마지막 자릿수까지 진행하지 않아도 정렬이 끝날 수 있다.
다시 말해서, “반드시 끝까지 정렬을 진행하지 않더라도 중간에 정렬이 완료될 수도 있다”는 것이 장점이 된다.
마지막까지 정렬을 진행하지 않고도 끝이 날 수도 있지만, 다음과 같은 단점이 있다.
“모든 데이터에 일괄적인 과정을 거치게 할 수 없다”
이는 가장 높은 자릿수에서 우선순위가 정렬이 되었는데, 다음 자릿수의 정렬을 진행하면서 잘못될 수 있다.
예를 들면 이런 경우다.
(1) 3 4 → 1 (3) 4 → 1 2 (2) → (의미없는 결과)
(2) 2 4 → 1 (2) 2 → 2 2 (4) → (의미없는 결과)
(2) 3 2 → 2 (2) 4 → 1 3 (4) → (의미없는 결과)
(1) 2 2 → 2 (3) 2 → 2 3 (2) → (의미없는 결과)
다시 말해서 정렬을 수행하는 중간에 데이터를 점검해야 하는 단점이 있다.
이는 LSD에 비해서 구현의 난이도가 올라가게 되고, 중간에 데이터의 점검으로 인한 성능의 저하가 생길 수도 있다.
[기수 정렬의 성능 평가]
기수 정렬은 비교 연산을 진행하지 않고 정렬을 수행한다.
버킷으로 데이터의 삽입과 추출만 반복하여 정렬을 하기 때문에, 삽입과 추출의 빈도수로 시간 복잡도를 계산할 수 있다.
삽입과 추출은 데이터의 양만큼 $n$회 수행하므로 각각이 $O(n)$이다.
이 둘을 합하면 $O(2n)$이지만, 빅-오에서는 앞의 계수에는 신경쓰지 않으므로 삽입과 추출을 합치면 $O(n)$이 된다.
데이터의 길이만큼 삽입과 추출을 반복하므로 데이터의 길이가 $l$이라고 하면, 전체적인 시간복잡도는 $O(ln)$이 된다.
그래서 다른 정렬 알고리즘의 한계를 넘어설 수 있는 성능을 보이는 것은 사실이다.
하지만, 적용 가능한 대상이 매우 제한적이라는 단점을 고려해야 한다.
