<STL> sort 함수

sort 함수는 C++ STL에서 제공하는 알고리즘이다.

sort는 인자에 있는 start와 end의 범위내 요소(element)를 default로 오름차순으로 정렬해 주는 함수이다.

sort(array.start(), array.end());

 

sort는 quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 O(n log n)이다.
따로 quick sort를 구현할 필요 없이 C++ STL에서 제공해주는 sort 함수를 이용하면 편리하게 정렬 할 수 있다.

 

함수의 원형은 아래와 같다.

template <typename T>
void sort(T start, T end);

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)

 

사용 예시 1)

#include<iostream>
#include<algorithm>
using namespace std;

int main(void){
    int arr[10] = {3, 7, 2, 4, 1, 0, 9, 8, 5, 6};
    sort(arr, arr+10); //[arr, arr+10) default(오름차순)로 정렬
    
    return 0;
}

 

사용 예시 2)

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;
 
 
class Element{
public:
    string str;
    int number;
    Element(String str, int number)
    	{this->str = str; this->number = number;}
    
};
 
bool compare(Element a, Element b){
    return a.number < b.number;
    
}
int main(void){
    vector<Element> v;
    
    v.push_back(Element("cc", 10));
    v.push_back(Element("ba", 24));
    v.push_back(Element("aa", 11));
    v.push_back(Element("cc", 8));  //Element의 number를 기준으로 오름차순 정렬
    v.push_back(Element("bb", 21));
    
    sort(v.begin(), v.end(), compare); //compare 함수 기준 정렬
    
    return 0;
}