<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
void RadixSort(vector<int>& v, int maxRadix, int firstIndex)
{
// maxRadix는 [최대 자릿수 + 1] 이므로 그 이전까지만 반복을 진행
for (int i = 1; i < maxRadix; i *= 10)
{
// 버켓 생성(0~9 : 10개) : 해당 자릿수의 자릿값을 의미
// ex) 100의 자릿수 검사 -> 104, 103은 1번, 555는 5번, 777은 7번
// 0번 인덱스는 해당 자릿수의 값이 없는 경우
// ex) 100의 자릿수 검사 -> 1, 57, 98 등은 0번 인덱스임
queue<int> bucket[10];
for (int j = 0; j < v.size(); j++)
{
int curRadix; // 현재 수의 자릿값
if (v[j] < 0) continue; // 음수인 경우 넣을 필요 x
else if (v[j] >= i) curRadix = (v[j] / i) % 10;
else curRadix = 0; // 현재 수가 자릿수보다 작으면 0을 넣음
bucket[curRadix].push(v[j]); // 버킷에 현재 수를 넣음
}
int insertIndex = firstIndex; // 벡터에 넣을 인덱스
for (int k = 0; k < 10; k++)
{
// 버킷에서 앞에서부터 순차적으로 빼내어 원래 벡터에 다시 저장
while (!bucket[k].empty())
{
// 버킷이 비어있지 않은 경우에 빌때까지 해당 큐에서 원소를 가져옴
v[insertIndex++] = bucket[k].front();
bucket[k].pop();
}
}
}
}
int MinusRadixSort(vector<int>& v, int minRadix)
{
int firstPlusIndex = 0; // 리턴해줄 음수 이후의 첫번째 인덱스 값
// minRadix는 [음의 최대 자릿수 + 1] 이므로 그 이전까지만 반복 진행
for (int i = -1; i > minRadix; i *= 10)
{
queue<int> bucket[11];
for (int j = 0; j < v.size(); j++)
{
int curRadix;
if (v[j] >= 0) curRadix = 10; // 0이나 양수인 경우 11번째 인덱스에 넣음
else if (v[j] <= -1) curRadix = (v[j] / i) % 10; // 현재 자릿값을 양수로 저장
else curRadix = 0;
bucket[curRadix].push(v[j]); // 버킷에 현재 수를 넣음
}
int insertIndex = 0; // 벡터에 넣을 인덱스
for (int k = 9; k >= 0; k--)
{
// 버킷에서 앞에서부터 순차적으로 빼내어 원래 벡터에 다시 저장
while (!bucket[k].empty())
{
// 버킷이 비어있지 않은 경우에 빌때까지 해당 큐에서 원소를 가져옴
v[insertIndex++] = bucket[k].front();
bucket[k].pop();
}
}
firstPlusIndex = insertIndex; // 첫번째 양수가 들어가는 인덱스 값을 lastIndex 값으로 저장
while (!bucket[10].empty())
{
// 버켓이 비어있지 않은 경우에 빌때까지 해당 큐에서 원소를 가져옴
v[insertIndex++] = bucket[10].front();
bucket[10].pop();
}
}
return firstPlusIndex;
}
int main()
{
int N;
cin >> N;
vector<int> v;
int maxVal = 0; // 최댓값을 저장할 변수
int maxRadix = 1; // 최대 자릿수를 저장할 변수
int minVal = 0; // 음수 최솟값
int minRadix = -1; // 음수의 최소 자릿수를 저장할 변수
// 원소 입력
while (N > 0)
{
int x;
cin >> x;
v.push_back(x);
N--;
maxVal = x > maxVal ? x : maxVal;
if (x < 0)
{
// 음수인 경우
minVal = x > minVal ? minVal : x;
}
}
// 8. 기수 정렬
// - 기수 = 자릿수
// - 자릿수별로 정렬하는 방식
// 1. 입력값의 최대 자릿수를 알아야 함
// 2. 처음은 1의 자릿수만 보고 차례로 버킷에 담았다가 순차적으로 빼줌
// 3. 다음은 10의 자릿수만 보고 같은 과정 반복
// 4. 최대 자릿수까지 같은 과정을 반복하면 정렬되어 있음
// 음수 정렬
// 최소 자릿수 찾기
// 마찬가지로 minRadix도 [음의 최대 자릿수 + 1] 이 됨
while (minRadix >= minVal) minRadix *= 10;
int firstPlusIndex = MinusRadixSort(v, minRadix);
// 최대 자릿수 찾기
// 이때 maxRadix는 [최대 자릿수 + 1] 이 됨
// ex) 999 -> 1000, 1000 -> 10000
while (maxRadix <= maxVal) maxRadix *= 10;
RadixSort(v, maxRadix, firstPlusIndex);
// 원소 출력
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
return 0;
}<풀이과정>
1. RadixSort()
1-1. 입력받으면서 최대값을 찾고, 해당 값을 이용해 1부터 10씩 곱해가면서 최대값보다 커지는 최대 자릿수를 찾는다.
1-2. 인자로는 벡터 v와 최대 자릿수 maxRadix, 첫번째 양수 값의 인덱스 번호 firstIndex를 받는다.
1-3. 1부터 maxRadix보다 작을 동안 10배씩 늘려가며 반복을 진행한다.
1-4. 큐를 이용해 각각의 자리값을 담은 버킷 10개를 생성한다.(0~9)
1-5. 벡터의 원소를 돌면서 각 원소들의 자릿값을 버킷의 인덱스에 맞게 넣는다.
1-6. 이때 현재 원소가 i보다 작은 경우 0을 넣고, 크다면 현재 원소의 i자리의 값은 현재 원소 v[j]를 i로 나누고 해당 수를 10으로 나눈 나머지로 구할 수 있다.
1-7. 벡터 v에 집어넣을 인덱스 insertIndex를 첫번째 양수 값의 인덱스 번호인 firstIndex부터 시작한다.
1-8. 버킷의 크기 10만큼 반복하며, 해당 버킷이 비어있지 않을 동안 반복하면서 버킷에서 원소를 가져와 v에 insertIndex번째 인덱스에 복사해주고 insertIndex에 1을 더해준 뒤, 버킷에서 원소를 빼준다.
1-9. 이렇게 모든 버킷을 도는 과정을 최대 자릿수까지 반복하면 정렬이 완료된다.
2. MinusRadixSort()
2-1. 이 함수는 음수에 대한 기수 정렬을 하는 함수이고 위의 양수 기수 정렬과 매우 유사하다.
2-2. 차이점으로는 리턴형으로 int형을 받고, 음수가 끝나고 양수가 시작되는 인덱스를 반환해준다.
2-3. 또한 버킷에서 벡터로 옮길때 음수이므로 반대 순서로 옮겨야 하고, 양수는 따로 버킷에 다른 공간에 담아서 마지막에 한번에 넣어준다.
<코멘트>
이번엔 여덟번째 방법인 기수 정렬로 풀어보았다!
원래의 기수 정렬은 양수 정렬인 것 같은데 이 문제의 경우 음수도 판단해야해서 음수 코드까지 짜느라 힘들었다.
양수, 음수 벡터를 애초에 나눠서 정의하고, 따로 기수정렬은 한 뒤 합치는 풀이가 좀 더 나을 것 같지만 오늘은 여기까지...
- 기수 정렬 -
장점
- 정렬법들 중에서 O(N) 이라는 말도 안되는 시간복잡도를 갖는 정렬법으로 엄청 빠르다.
- 비교가 이루어지지 않는다.
단점
- 버킷이라는 추가적인 메모리가 할당되어야 하므로 메모리가 소비된다.
- 데이터 타입이 일정한 경우에만 가능하다. 즉, 양수는 양수끼리, 음수는 음수끼리만 가능하다.
- 이러한 구현을 위한 조건이 굉장히 많이 붙기 때문에 많이 사용되는 방법은 아니다.
특징
1. 시간복잡도 O(n) -> O(rn) 이라고도 한다.(r : 숫자의 자릿수)
2. 공간복잡도 O(n)
3. in-place정렬
4. stable정렬 - 중복된 키 값의 순서가 정렬 후에도 유지되기 때문
<cf>
1. stable vs not-stable
- stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻함.
- 즉 , 정렬했을 때 중복된 키 값이 원래 순서대로 정렬되어있으면 stable 아니면 not-stable이다.
2. in-place vs not in-place
- in- place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻함.
- not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻함.
<제출 결과>
<기수 정렬> - 음수까지 하느라 시간이 좀 걸린듯..?
<쉘 정렬>
<병합 정렬> - 준수한 시간대
<삽입 정렬> - 버블/선택 정렬보다 빠른 시간대, 밑의 결과는 매번 swap했을 경우
<힙 정렬> - 퀵 정렬보다 느린 시간대
<퀵 정렬> - 준수한 시간대
<선택정렬> - 버블정렬에 비해 조금 더 빠르다는 것을 알 수 있음
<버블정렬>
