[C++] sort algorithm 정리 및 예시

• 안녕하세요

• BlockDMask 입니다.

• 오늘은
  C++ STL 에서 제공하는 알고리즘 중에
  sort 알고리즘에 대해 알아보겠습니다.

0. sort algorithm

• sort 알고리즘은 <algorithm> 헤더파일에 속해있습니다.

• sort(start, end)를 이용하여 [start, end) 의 범위에 있는 인자(element)를 오름차순(default)으로 정렬해주는 함수 입니다.
  start를 포함하고 end를 포함하지 않는 구간. (iterator를 생각하면됩니다.)

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

1. 원형 및 사용법

• 원형

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)

2. 예제

• 예제에서는 default sort 하는법, 이항조건자를 이용한 sort 내림차순, compare 함수를 만들어서 sort 사용하는법, 연산자 오버로딩을 사용해 sort하는 방법을 알아보겠습니다. 

- 예제 1) 배열 sort (default - 오름차순)

#include<iostream>
#include<algorithm>
using namespace std;
void Print(int *arr){
    cout << "arr[i] : " ;
    for(int i=0; i<10; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main(void){
    int arr[10] = {3, 7, 2, 4, 1, 0, 9, 8, 5, 6};
    Print(arr); //정렬 전 출력
    sort(arr, arr+10); //[arr, arr+10) default(오름차순)로 정렬
    Print(arr); //정렬 후 출력
    
    return 0;
}
 

> 출력결과

- 예제 2) vector container sort (내림차순)

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;
 
void Print(vector<int> &v){
    cout << "vector : " ;
    for(int i=0; i<10; i++){
        cout << v[i] << " ";
    }
    cout << endl;
}
 
int main(void){
    srand((int)time(NULL)); //난수생성을 위해
    
    vector<int> v;
    int n = 10;
    
    for(int i=0; i<n; i++){ //vector에 1의자리 숫자를 임의로 삽입
        v.push_back(rand() % 10);
    }
    Print(v); //정렬 전 출력
    sort(v.begin(), v.end(), greater<int>()); //[begin, end) 내림차순으로 정렬
    Print(v); //정렬 후 출력
    
    return 0;
}
 

> 출력결과

- 예제 3) compare 함수를 만들어서 sort

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;
 
 
class Student{
public:
    string name;
    int age;
    Student(string name, int age):name(name),age(age){}
    
};
 
 
void Print(vector<Student> &v){
    cout << "Student : " ;
    for(int i=0; i<5; i++){
        cout << "[" << v[i].name << ", " << v[i].age << "]";
    }
    cout << endl;
}
 
bool compare(Student a, Student b){
    if(a.name == b.name){   //이름이 같으면, 나이가 적은순
        return a.age < b.age;
    }else{                  //이름 다르면, 이름 사전순
        return a.name < b.name;
    }
    
}
int main(void){
    vector<Student> v;
    
    v.push_back(Student("cc", 10));
    v.push_back(Student("ba", 24));
    v.push_back(Student("aa", 11));
    v.push_back(Student("cc", 8));  //cc는 이름이 같으니 나이 기준 오름차순 예시
    v.push_back(Student("bb", 21));
    
    Print(v); //정렬 전 출력
    sort(v.begin(), v.end(), compare); //[begin, end) compare 함수 기준 정렬
    Print(v); //정렬 후 출력
    
    return 0;
}
 

> 출력결과

- 예제 4) 연산자 오버로딩(operator overloading) 이용한 sort

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;
 
 
class Student{
public:
    string name;
    int age;
    Student(string name, int age):name(name),age(age){}
    
    bool operator<(Student s) const{  //연산자 오버로딩(operator overloading)
        if(this->name == s.name){
            return this->age < s.age;
        }else{
            return this->name < s.name;
        }
    }
};
 
void Print(vector<Student> &v){
    cout << "Student overloading : " ;
    for(int i=0; i<5; i++){
        cout << "[" << v[i].name << ", " << v[i].age << "]";
    }
    cout << endl;
}
 
int main(void){
    vector<Student> v;
    
    v.push_back(Student("cc", 10));
    v.push_back(Student("ba", 24));
    v.push_back(Student("aa", 11));
    v.push_back(Student("cc", 8));  //cc는 이름이 같으니 나이 기준 오름차순 예시
    v.push_back(Student("bb", 21));
    
    Print(v); //정렬 전 출력
    sort(v.begin(), v.end()); //[begin, end) 연산자 오버로딩 이용한 정렬.
    Print(v); //정렬 후 출력
    
    return 0;
}
 

> 출력결과

<참고>

http://www.cplusplus.com/reference/algorithm/sort/

감사합니다.