<개인공부>/[C++]

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

사용자 BlockDMask 2017. 10. 17. 09:00
반응형
  • 안녕하세요

  • 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 - 오름차순)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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= {3724109856};
    Print(arr); //정렬 전 출력
    sort(arr, arr+10); //[arr, arr+10) default(오름차순)로 정렬
    Print(arr); //정렬 후 출력
    
    return 0;
}
 
cs

> 출력결과



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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}
 
cs


> 출력결과

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}
 
cs


> 출력결과


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}
 
cs

> 출력결과


<참고>

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

감사합니다.



반응형