STL
- Standard Template Library(표준 템플릿 라이브러리)
- 프로그램에 필요한 자료구조와 알고리즘을 Template으로 제공한다. (Template으로 제공하는 덕분에 어떠한 데이터 타입도 사용이 가능하다.)
-종류 : 등
algorithm 라이브러리
컨테이너에 반복자들을 가지고 정렬, 검색 등의 작업을 쉽게 수행할 수 있도록 도와주는 라이브러리
sort(정렬) 알고리즘
sort
-
Quick Sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 O(NlgN)이다. 따로 quick sort를 구현할 필요 없이 C++ STL에서 제공해주는 sort 함수를 이용하면 편리하게 정렬 할 수 있다.
-
sort(start, end)
[start, end) 의 범위에 있는 인자(element)를 오름차순(default)으로 정렬
start를 포함하고 end를 포함하지 않는 구간. (iterator를 생각하면됩니다.)
- 원형
template <typename T>
void sort(T start, T end, Compare comp);3번째 인자를 넣지 않으면 default로 오름차순으로 정렬
3번째 인자에 사용자가 정의한 함수를 기준으로 정렬을 할 수 있다. (이항조건자를 이용할 수도 있습니다.)
- 사용법
sort(arr, arr+n);
sort(v.begin(), v.end());
sort(v.begin(), v.end(), compare); //사용자 정의 함수 사용
sort(v.begin(), v.end(), greater<자료형>()); //내림차순 (Descending order)
sort(v.begin(), v.end(), less<자료형>()); //오름차순 (default = Ascending order)compare (비교 함수) 수정 가능
first 값으로 내림차순 하되 만약 first 값이 같다면 second 값으로 내림차순 하게 만들어준다.
비교함수는 순서가 올바른 경우는 true를, 올바르지 않는 경우는 false를 반환한다.
stable_sort
- Merge Sort(퀵 정렬)을 기반으로 함수가 구현되어있다.
- 정렬을 하되 원소들 간의 순서를 보존한다. 그래서 stable이 붙음.
ex. 만약에 벡터에 [a, b] 순으로 있었는데 a 와 b 가 크기가 같을 때
sort : 그 순서가 랜덤으로 정해진다. ([a,b] or [b,a])
stable_sort : 처음에 넣었던 순서를 반드시 보존한다. 컨테이너 상에서 [a,b] 순으로 있었다면 정렬 시에도 (크기가 같다면) [a,b] 순으로 나온다.
여러 값들이 묶여 있을 때, 하나의 요소로 정렬할 경우 다른 요소들의 정렬 순서도 정렬 전과 같이 그대로 유지될수 있도록 하는 정렬이다.
차차 추가 예정
💡 참고 포스팅
C++, STL이란?
[C++]C++, STL이란?
[C++] sort algorithm 정리 및 예시
씹어먹는 C++ - <10 - 3. C++ STL - 알고리즘(algorithm)>
C++ STL 알고리즘(Algorithm)
[C++] STL pair를 sort 함수로 내림차순 정렬하기
[C++]stable_sort이란?
