문제
문제 탐색
이론상 (시간 복잡도 상) 가장 빠른 정렬은 Radix Sort, Count Sort이다.
배열의 크기가
Radix Sort, Count Sort는 무려
물론 상황에 따라서 (숫자의 범위, 배열의 크기, 배열의 상태(Almost Sorted, Randomly, ...))에 따라
왜냐하면 Radix Sort가
만약 문제 상황이
Radix Sort에도 MSD(가장 높은 자릿수부터 계산), LSD(가장 낮은 자릿수부터 계산)이 있는데, LSD가 구현이 훨씬 쉽기에 선택하였다.
만약 10진수 Radix Sort로 구현하면,
이 때
그래서 문제상황의 모든
음수일 경우에는
9비트 단위로 끊어서
만약 문제상황의 메모리 제한이 적지 않다면 Bitwise Radix Sort는 굉장히 빠른 정렬 방법이다.
소스 코드
#include <cstdio>
#include <queue>
using namespace std;
void Sort(int *arr, int n) {
queue<int> que[512]; // que count
int i, j, count;
for (i = 0; i < 3; i++) { // loop count
for (j = 0; j < n; j++) que[(arr[j] >> (i * 9)) & 511].push(arr[j]);
count = 0;
for (j = 0; j < 512; j++) {
while (!que[j].empty()) {
arr[count] = que[j].front();
que[j].pop();
count++;
}
}
}
for (j = 0; j < n; j++) {
if ((arr[j] >> 27) == 0) que[0].push(arr[j]); // 양수일 때
else que[1].push(arr[j]); // 음수일 때
}
j = 0;
while (!que[1].empty()) {
arr[j] = que[1].front(); que[1].pop(); j++;
}
while (!que[0].empty()) {
arr[j] = que[0].front(); que[0].pop(); j++;
}
}
'대학 과제 복기' 카테고리의 다른 글
[AL] 알고리즘개론 수업에 나온 과제들 (0) | 2022.07.03 |
---|