[C++] STL 알고리즘: Sort
정렬 알고리즘 O(n^2)
1. selection sort(선택 정렬) : [i, n] 범위를 훑으며 가장 작은 원소를 v[i]에 대입하는 걸 반복
2. insertion sort(삽입 정렬) : [1, i) 범위가 정렬되어있을 때 v[i]를 앞의 i - 1개의 원소 사이에 끼워넣음
3. bubble sort(버블 정렬) : v[i - 1] > v[i]인 경우 swap해주는 걸 n번 반복함
O(n^2) 정렬 알고리즘은 비교적 구현이 간단하고 n <= 1,000인 경우엔 O(nlogn)과 속도 면에서 거의 차이가 없음
정렬 알고리즘 O(nlogn)
1. merge sort(병합 정렬) : 최악의 경우도 O(nlogn)이라 STL 없이 구현할 때 좋음
2. heap sort(힙 정렬) : 최악의 경우도 O(nlogn)이라 STL 없이 구현할 때 좋음
3. quick sort(퀵 정렬) : 가장 빠르지만 최악의 경우 O(n^2)이 되기 때문에 pivot을 잘 골라야 함
4. intro sort(인트로 정렬) : heap + quick + insertion, std::sort의 내부 구현에 사용되며 각 정렬 방법의 장점을 가져와서 성능이 좋음
정렬 알고리즘 O(n)
1. counting sort(계수 정렬) : cnt 배열을 선언해두고 직접 개수를 셈. 원소의 범위가 작을 때 사용 가능함.
2. radix sort(기수 정렬) : 자릿수 기준으로 버킷을 만들어서 정렬을 수행함. 정수 자료형에만 사용 가능함.
특수한 경우 사용할 수 있는 O(n) 정렬 방법임.
counting sort는 수의 범위가 작으면 가끔 사용할 수 있고, radix sort는 극한의 최적화에 사용하는 흑마법 같은 알고리즘임.
--------------------------------기본------------------------------------
내림차순 정렬
방법 1: STL 자료구조의 reverse_iterator를 이용
v.rbegin()은 vector의 맨 마지막 원소를 가리키고, v.rend()는 맨 처음 원소의 앞의 위치를 가리키며 reverse_iterator는 ++을 했을 때 더 앞쪽 원소로 이동하기 때문에 less<>{}를 이용해 정렬해도 내림차순으로 정렬이 됨.
방법 2: greater<> functor를 이용
a > b를 리턴하는 greater<> functor를 이용하며, 자료형의 > 정의에 맞게 v[i] >= v[i + 1]
(정확히는 !(v[i ] < v[i+1]))를 만족하도록 배열을 정렬해줌
int main() {
fastio;
vector<int> v{ 1,2,3,4,5 };
sort(v.rbegin(), v.rend());
for (auto& i : v) cout << i << ' '; cout << '\n';
sort(v.begin(), v.end(), greater<>{});
for (auto& i : v) cout << i << ' '; cout << '\n';
}
동일한 결과 출력
Partial sort (잘 안 씀 skip!)
int main() {
fastio;
vector<int> v{ 3,1,4,1,5,9,2,6,5,3,5 };
partial_sort(v.begin(), v.begin() + 5, v.end());
for (auto& i : v) cout << i << ' '; cout << '\n';
}
배열의 모든 구간을 정렬할 필요 없이 v[0] ~ v[k - 1]까지 k개의 원소만 제대로 정렬된 상태로 만드는 경우임
즉, i < k에 대해 v[i]에 i번째로 작은 원소가 오도록 정렬하면 됨
이런 경우엔 전체를 정렬하는 것보다 partial_sort(start, middle, end)을 사용하는게 더 좋음
이 함수는 [st, en) 범위의 원소들을 부분적으로 정렬해서 [st, mid) 범위에 올바른 값이 들어가도록 만들어줌
함수의 시간복잡도는 O((en - st)log(mid - st))임
nth_element
int main() {
fastio;
vector<int> v{ 3,1,4,1,5,9,2,6,5,3,5 };
nth_element(v.begin(), v.begin() + 3, v.end());
cout << v[3] << '\n';
for (auto& i : v) cout << i << ' '; cout << '\n'; }
평균 시간복잡도 O(n)에 k번째 원소를 구하는 함수임
내부 구현은 quick select를 이용
일반적으로 nth_element는 배열을 직접 정렬하는 것보다 빠르게 작동함
nth_element(st, mid, en)
[st, en) 범위의 원소들을 정렬했을 때 v[mid]에 위치할 원소를 v[mid]에 오도록 하고,
[1, mid) 범위의 i에 대해 v[i] <= v[mid]를, (mid, n - 1] 범위의 i에 대해 v[mid] <= v[i]를 만족하도록
v 배열을 이분함(mid 보다 작은 건 앞에, 큰 건 뒤에 / but 정렬되지는 않음)
이때 [1, mid), (mid, n - 1] 범위의 원소들은 v[mid]에 대해 구분되어있을 뿐이며 정렬이 되어있진 않음
is_sorted
int main() {
fastio;
vector<int> v{ 3, 1, 4, 1, 5, 9, 2 };
vector<int> w{ 1, 2, 3, 3, 4, 5, 5 };
cout << is_sorted(v.begin(), v.end()) << '\n'; // 0
cout << is_sorted(w.begin(), w.end()) << '\n'; // 1 }
배열이 정렬된 상태인지 O(n)에 확인해주는 함수임
--------------------------------심화------------------------------------
형식 1
sort(start, end, cmp = less<>{})
예시)
vector<int> v = { 3,1,4,1,5,9,2 }; //벡터
int w[5] = { 1,2,3,4,5 }; //배열
string s = "minji80"; //string
sort(v.begin(), v.end());
sort(w, w + 5, greater<>{}); //w+5는 {1,2,3,4,5}에서 5 다음 위치를 가리킨다.
sort(s.begin(), s.end());
for (auto& i : v) cout << i << ' '; cout << '\n'; // 1 1 2 3 4 5 9
for (auto& i : w) cout << i << ' '; cout << '\n'; //5 4 3 2 1
cout << s << '\n'; //08iijmn
<주의>
end는 마지막 원소 다음을 가리켜야 한다.
greater<>{}를 안 넣으면 default는 less<>{}.
정렬은 임의 위치 접근만 가능하면 vector, 배열, string이건 상관없이 가능
하지만 list, stack, queue와 같이 v.begin() + i 등의 연산이 불가능한 container는 std::sort를 사용할 수 없음
(v.begin() + i와 같이 임의 위치에 접근하는 연산이 가능한 iterator를 random access iterator라고 함)
형식 2
struct Info{
int val;
bool operator < (const Info& i) const{
//첫번째 const == i가 변하지 않는다 + 두번째 const == operator<가 구조체의 멤버 변수를 수정하지 않는다
return val>i.val; // < 으로 두 Info 객체를 비교
//val>i.val이 true이면 5>3 이므로 위치 그대로 5 3 으로 적히게 된다.
}
};
int main() {
fastio;
vector<Info> v;
for(int i=1; i<=5; i++) v.push_back(Info{i}); // v에 Info{1}..Info{5}가 있게 됨
sort(v.begin(), v.end());
for(auto& i:v) cout<<i.val<<' '; cout<<'\n';
}
<주의>
왜 const를 사용하는가?
const 키워드가 붙은 멤버 함수는 상수 객체(const object)에서도 호출될 수 있음
만약 operator<에 const가 붙어 있지 않다면, 상수 객체에서는 이 함수를 호출할 수 없음
const Info a{5};
const Info b{3};
bool result = a < b; // 만약 operator<가 const가 아니면 컴파일 에러 발생
왜냐하면 a와 b는 const로 선언되었으니 해당하는 operator<도 const로 맞춰져야 함
형식 3
람다함수 사용
int main(){
fastio;
vector<string> v{ "stack", "queue", "list", "set", "map" };
sort(v.begin(), v.end(), [](const string&a, const string&b) -> bool{
if(a.size() != b.size()) return a.size() < b.size(); //길이가 다르면 짧은 문자열이 먼저 오도록 정렬
return a>b; //길이가 같으면 문자열을 a,b,c순으로 비교
});
for(auto&i :v) cout<<i<<' '; cout<<'\n';
} //set map list stack queue 출력
형식 4
Bool으로 전역 함수를 함수 포인터로 넘기기
bool Cmp(const string& a, const string& b) {
if (a.size() != b.size()) return a.size() < b.size(); //사이즈가 다르면 짧은 문자열이 먼저 오도록 정렬
return a > b; // 사이즈가 같으면 사전순으로 정렬
}
Struct으로 () 연산자 정의하기
struct Cmp {
bool operator() (const string& a, const string& b) const {
if (a.size() != b.size()) return a.size() < b.size();
return a > b;
}
};
int main() {
fastio;
vector<string> v{ "stack", "queue", "list", "set", "map" };
sort(v.begin(), v.end(), Cmp 또는 Cmp()); // bool이면 Cmp, struct이면 Cmp()임.
for (auto& i : v) cout << i << ' '; cout << '\n'; // set map list stack queue
}
람다식이나 전역 함수는 자료형만 가지고선 () 연산자를 정의할 수 없기 때문에 priority_queue 등의 생성자에 매개변수로 넘겨줘야 한다. 하지만 struct는 자료형만 넘겨주면 알아서 자료형에 정의된 () 연산자를 사용하기 때문에 매개변수로 또 넘겨줄 필요가 없기 때문이다.
따라서 sort, lower_bound, max_element 등 비교 함수 객체의 자료형을 명시적으로 넣어줄 필요가 없는 STL 알고리즘 함수들은 람다식이나 전역함수를 사용한다. priority_queue, set, map 등의 STL 자료구조는 struct를 이용하면 좋다.
2751번
오름차순 정렬하기
n<=1,000,000이므로 O(nlogn)으로 처리하기 위해 sort(v.begin(), v.end())으로 처리한다.
2750번의 경우 n<=1000이므로 O(n^2)도 괜찮아서 for문을 돌린다.
int main() {
fastio;
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
for (auto& i : v) cout << i << '\n';
}
10989번
n <= 10,000,000인데 메모리 제한이 8MB으로 되어있다.
int가 4byte인 걸 생각해보면 1MB 당 25만개의 int를 저장할 수 있으니 8MB에는 대략 200만개의 int를 저장할 수 있다.
따라서 문제의 제한으로는 입력된 수를 모두 저장하는 것도 불가능ㅎ