[C++] STL - 알고리즘(algorithm)

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이란?