_C++_알고리즘_Part_1

STL의 정렬 알고리즘은 순차 컨테이너와 배열에 적용할 수 있다.

list, forword_list는 컨테이너 내부 구조에 최적화된 정렬 기능을 제공하기 때문에 굳이 사용할 필요가 없다.

vector, deque, array클래스 및 배열에 대해서는 유용하게 사용할 수 있다.

#include<algorithm>으로 사용할 수 있다.

---

정렬 알고리즘

sort()

sort는 정렬을 도와준다. sort의 시간 복잡도는 N에 대해 O(NlogN).

int arr[5] {3, 5, 1, 2, 6};
sort(arr, arr+5); // arr 정렬

vector<int> v{3, 5, 1, 2, 6};
sort(v.begin(), v.end()); // v 정렬
sort(v.begin(), v.end(), greater<>()); // v 역순 정렬, greater부분에 정한 규칙을 넣을 수 있음.

---

merge()

병합을 도와준다. merge의 시간복잡도는 N에 대해 O(N).

vector<int> v1 {1, 3, 5, 7, 9}, v2 {2, 4, 6, 8, 10}, v3(10);

merge(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend(), v3.begin()); //v3에 병합

---

nth_element()

주어진 정렬에서 n번째 아이템을 찾아준다. 선형 시간복잡도를 가짐.

퀵 소트의 원리를 이용

vector<int> v{1, 2, 3, ..... 50};
nth_element(v.begin(), v.begin() + k, v.end()); // 첫번째와 세번째는 작업위치, 두번째는 찾을위치
cout << v[k];

---

partition()

주어진 조건에 맞는 항목은 앞으로, 그렇지 않은 항목은 뒤로 배치. 선형 시간 복잡도를 가짐.

vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
partition(v.begin(), v.end(), [](int x) {
	return (x & 1) == 0; // 비트연산자. 짝수는 앞으로, 홀수는 뒤로 배치
});

---

random_shuffle()

항목을 랜덤으로 섞음. 선형 시간 복잡도 가짐.

C++20부터는 std::range::shuffle 함수로 대체됨.

#include <algorithm>
#include <random> // random_device 정의
#include <vector>
using namespace std;

int main()
{
	vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	random_device rd; // 물리적 난수 생성기
	mt19937 gen(rd()); // 의사난수 생성기 중 하나
	shuffle(v.begin(), v.end(), gen);
	for (auto x : v)
		cout << x << ' ';
}

---

작업 알고리즘

for_each()

지정된 항목열을 순회하면서 특정 콜백 함수를 실행해줌. 순회할 범위를 지정하는 두 반복자와 각 항목에 대해 호출될 함수 객체를 인자로 받는데 람다 표현식이 주로 사용됨.

vector<int> vec = {1, 2, 3, 4, 5};
for_each(vec.begin(), vec.end(), [](int& x) {
	cout << ++x << ' ';
});// vector를 순회하며 각 항목의 바꿔서 출력해줌.