O(N+K)
이다. #include <iostream>
using namespace std;
int n;
int freq[2000001];
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0;i<n;i++)
{
int a;
cin >> a;
freq[1000000+a]++;
}
for(int i = 0;i<2000001;i++)
{
while(freq[i]--)
cout << i-1000000 << '\n';
}
}
자리수 배열
에 넣는다.자리수 배열
에 넣는다. 이 과정을 최대 자리수까지 반복한다.원소의 자리수의 최대 개수가 D이면, D번의 걸쳐서 정렬을 진행한다. 이때 만약 리스트의 개수가 K개 일 때, 엄밀히 말하면 시간복잡도는 O(D(N+K))
이다. 하지만 K는 일반적으로 매우 작아 무시가 가능하므로. O(DN)
이라고 할 수 있다.
#include <bits/stdc++.h>
using namespace std;
int n = 15;
int arr[1000001] = {12, 421, 46, 674, 103, 502, 7, 100, 21, 545, 722, 227, 62, 91, 240};
// 1, 10, 100의 자리에 대해서 진행, 수가 최대 3자리수가 아닐 경우 d를 조절해야 함
int d = 3;
// p10[i] = 10의 i승
int p10[3];
// x의 10^a 자리의 값을 반환하는 함수
int digitNum(int x, int a){
return (x / p10[a]) % 10;
}
vector<int> l[10];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
p10[0] = 1;
for(int i = 1; i < d; i++) p10[i] = p10[i-1] * 10;
for(int i = 0; i < d; i++){
for(int j = 0; j < 10; j++) l[j].clear();
// 각 수를 list에 대입
for(int j = 0; j < n; j++)
l[digitNum(arr[j], i)].push_back(arr[j]);
// 0번 리스트부터 차례로 다시 arr에 넣어 재배열
int aidx = 0;
for(int j = 0; j < 10; j++){
for(auto x : l[j]) arr[aidx++] = x;
}
}
for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}
c++에서 기본적으로 제공하는 STL sort()
함수는 퀵 정렬을 기반으로 구현되어 있다. 또한, 퀵 정렬의 경우 최악의 경우 O(N^2)
의 시간복잡도를 가지지만, STL sort()
의 경우 재귀의 깊이가 너무 깊어지게 되면 O(NlogN)
이 보장되는 정렬알고리즘으로 정렬을 진행하기 떄문에 O(NlogN)
의 시간복잡도가 보장된다. 하지만, sort() 함수는 stable 정렬이 아니기때문에 주의할 필요가 있다. 이를 위해서는 stable_sort()
를 이용하면 된다.
STL에서 제공되는 Pair, Tuple 컨테이너 모두, 앞의 원소부터 먼저 비교를 진행하기때문에 편하게 사용하면 된다.
int a[5] = {2,6,1,3,7};
sort(a,a+5);
vector<int> v = {1,4,5,2,7};
sort(v.begin(), v.end());
또한 sort() 함수의 장점은 비교함수를 사용자가 직접 정의할 수 있다는 점이다.
int a[5] = {2,6,1,3,7};
bool cmp(int a, int b)
{
return b > a
}
sort(a,a+5,cmp);
위의 코드는 오름차순으로 정렬을 수행하는 경우이다. 사용자가 함수를 직접 정의하는 경우에는 원소가 같은 경우에 true
를 반환하면 절대
안된다. 런타임 오류가 발생할 가능성이 있다.
또한, 단순히 오름차순, 내림차순 정렬이 아닌 새로운 정의에 따라 sort()를 수행하도록 할 수 있다.
int a[5] = {2,6,1,3,7};
bool cmp(int a, int b)
{
if(a%5 != b%5) return a%5 < b%5
return a < b
}
sort(a,a+5,cmp);
위의 코드는 5로 나눈 나머지순으로, 5로 나눈 나머지가 같다면 크기순으로 정렬을 하는 경우이다.
또한 비교함수의 인자로 STL 객체나, 클래스 객체를 전달시 reference를 사용하는 것이 좋다.
bool cmp(string a, string b)
{
return a.back() < b.back()
}
// 아래 코드가 더 낫다.
bool cmp(string& a, string& b)
{
return a.back() < b.back()
}
불필요한 값의 복사를 줄여 시간을 약간 절약할 수 있다.