[C++] std::sort()

algorithm 헤더에 있는 sort() 함수는 quick sort를 기반으로 평균 시간복잡도 nlogn 을 보장한다. 

 

1. 기본형:

template <class RandomAccessIterator>

 void sort (RandomAccessIterator first, RandomAccessIterator last);

마지막에 사용자가 지정한 비교함수를 argument로 주지 않으면 기본 오름차순으로 정렬된다. 

vector<int> v = {3, 4, 2, 1};

bool compare(int a, int b){
	return a>b;
}

int main(void){
  sort(v.begin(), v.end());
  sort(v.begin(), v.end(), less<int>());
  sort(v.begin(), v.end(), greater<int>();
  sort(v.begin(), v.end(), compare);
}

 

2. 커스텀:

template <class RandomAccessIterator, class Compare>

 void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

비교함수를 지정해서 인자로 넘겨줄 수 있다. 

기본적으로 주어지는 함수를 인자로 삼을 수도 있다. 

 - greater<자료형>()

 - less<자료형>0

 

보통 비교함수를 넘겨주는 경우는 구조체나 pair를 사용할 때, 멤버 중 어떤 애를 갖고 비교할지 알려주기 위해서이다. 

vector<int> v = {3, 4, 2, 1};
vector<pair<int, int> > v2;

bool compare(pair<int, int> a, pair<int, int> b){
	return a.first>b.first;
}

int main(void){
    int i=0, j=1, k=2, l=3;
    pair<int, int> x = make_pair(i, j);
    pair<int, int> y = make_pair(k, l);
    v2.push_back(x);
    v2.push_back(y);

    sort(v.begin(), v.end(), less<int>());
    sort(v.begin(), v.end(), greater<int>();
    sort(v2.begin(), v2.end(), compare);
}