Chapter2. 알고리즘 Part.1
1. 정렬 알고리즘
STL의 제너릭 정렬 알고리즘은 순차 컨테이너와 배열에만 적용할 수 있다. 순차 컨테이너 중 list와 forward_list는 컨테이너의 내부 구조에 최적화된 더 효율적인 정렬 기능을 메서드로 제공하기 때문에 이 제너릭 정렬 알고리즘을 적용할 필요가 없다. 결과적으로 vector, deque, array 클래스나 배열에 대해서만 유용하게 사용될 수 있다.
- sort()
반 개방형 범위를 지정하는 두개의 반복자를 받아 주어진 범위의 항목열을 정렬한다. 시간 복잡도는 항목의 개수 N에 대해 O(NlogN)이다. 정렬 기준은 기본적으로 항목 타입에 대한 operator <이다. 다만 세번째 인자로서 정렬을 위한 비교함수 객체를 넘겨줄 수 있다. 세번째 인자를 넘지기 않는다면 항목 타입이 operator <를 지원해야만 한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int arr[6] { 8, 7, -5, 0, -1, 4 };
sort(arr, arr + 6); //배열에 대해서는 반복자 대신 포인터를 전달하여 범위를 지정
for (int i = 0; i < 6; ++i)
cout << arr[i] << ' ';
cout << endl;
vector<int> v{ 8, 7, -5, 0, -1, 4 };
sort(v.begin(), v.end(), greater<>()); //greater<>의 인스턴스를 넘겨주면 operator >를 기준으로 정렬
for (auto item : v)
cout << item << ' ';
cout << endl;
sort(v.begin(), v.end(), [](const int& a, const int& b) { //클로져를 넘겨 정렬 방법을 커스텀
return abs(a) < abs(b);
});
for (auto item : v)
cout << item << ' ';
}sort는 stable한 정렬을 해주지는 않는다. 즉, 비교함수 기준으로 동일한 값으로 취급하는 두 항목에 대해서는 원래의 정렬 순서를 유지해주지 않는다. stable 정렬이 필요하다면 stable_sort 함수를 사용하면 되지만 stable_sort가 필요한 경우는 흔치 않아 잘 사용되지 않는다.
- merge()
병합 정렬 알고리즘에서 병합과정만 수행해주는 함수이다. 따라서 병합의 대상이 되는 두 컨테이너는 먼저 정렬되어 있어야만 올바른 결과를 얻을 수 있다. 병합될 두 컨테이너의 크기 합 N에 대하여 O(N)의 시간 복잡도 성능을 갖는다.
vector<int> v1 {1, 3, 5, 7, 9}, v2 {2, 4, 6, 8, 10}, v3(10);
//병합 결과가 저장될 v3는 미리 충분한 크기를 확보해야 함
merge(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend(), v3.begin());
for (auto item : v3)
cout << item << ' ';- nth_element()
C++의 STL에서는 다른 언어에서 찾아보기 힘든 특별한 정렬 알고리즘이 제공된다. nth_element는 주어진 범위의 정렬 결과에서 n번째 아이템을 찾아주는 함수이다. 실제로 주어진 범위 전체를 정렬한 후 룩업하는 방식으로 구현할 수도 있으나 nth_element는 이 작업을 선형 시간 복잡도로 처리해준다. 그 비결은 퀵 소트의 원리를 응용한 것이다. 퀵 소트는 정렬할 항목열에서 하나의 기준 항목(피벗)을 정하고 피벗보다 작은 항목들과 큰 항목들을 모아두어 두개의 부분 문제로 나누고 재귀적으로 해결해나가는 분할 정복 알고리즘이다. 각 단계에서 피벗의 위치는 정확하게 결정되기 때문에 찾고자 하는 n번째 위치가 피벗의 위치라면 n번째 항목을 찾은 셈이 된다. 피벗이 n번째 위치가 아니라면 나뉜 두개의 부분 문제 중 하나만 해결하면 된다. 따라서 퀵 소트와 다르게 선형시간 복잡도를 갖는 알고리즘이 된다.
이 함수의 목적은 탐색이지만 주어진 범위의 항목열 일부를 정렬하기 때문에 정렬 알고리즘으로 분류한다.
vector<int> v;
//...항목 삽입 생략
nth_element(v.begin(), v.begin() + k, v.end());
//첫 번째와 세 번째 파라미터는 작업할 범위를, 두 번째 파라미터는 찾을 위치를 나타냄
cout << v[k];- partition()
주어진 조건에 맞는 항목들은 앞쪽으로, 그렇지 않은 항목들은 뒤쪽으로 배치해준다. stable하지 않고 선형 시간 복잡도를 갖는다. stable하게 처리해주는 stable_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++17까지 사용할 수 있고 C++20에서는 std::range::shuffle 함수로 대체되었다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector 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 << ' ';
}2. 작업 알고리즘
- for_each()
지정된 항목열을 순회하면서 특정 콜백 함수를 실행해준다. 순회할 범위를 지정하는 두 반복자와 각 항목에 대해 호출될 함수 객체를 인자로 받는데 람다 표현식이 주로 사용된다.
다음 예제는 벡터를 순회하며 각 항목의 값을 바꾸고 출력한다.
vector<int> vec = {1, 2, 3, 4, 5};
for_each(vec.begin(), vec.end(), [](int& x) {
cout << ++x << ' ';
});