[C++] 함수 템플릿 std::sort 정리

참고 링크

https://blockdmask.tistory.com/178
http://www.cplusplus.com/reference/algorithm/sort/

함수 원형
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

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)

C++ STL에서 제공하는 알고리즘 중 하나인 sort 알고리즘은

• <algorithm> 헤더파일에 속해 있다.
• sort(start, end)를 이용하여 [start, end) 의 범위에 있는 인자(element)를 오름차순(default)으로 정렬해주는 함수이다.
  start를 포함하고 end를 포함하지 않는 구간.
• quick sort(퀵 정렬)을 기반으로 함수가 구현되어 있어서 평균 시간복잡도는 nlogn이다. 따로 quick sort를 구현할 필요 없이 C++ STL에서 제공해주는 sort 함수를 이용하면 편하게 정렬할 수 있다.
• 값이 중복되는 원소들의 상대적인 순서가 보장되지 않는 unstable sort이다.

예제1: 정수 배열 정렬하기

#include<iostream>
#include<algorithm> // std::sort
using namespace std;

void printArray(int* arr, const int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
int main() 
{
    const int n = 10;
    int arr[n] = { 3, 7, 2, 4, 1, 0, 9, 8, 5, 6 };

    // 정렬 전
    printArray(arr, n);

    // 오름차순 정렬 후
    sort(arr, arr + n); // [arr, arr + n)
    printArray(arr, n); // 0 1 2 3 4 5 6 7 8 9

    // 내림차순 정렬 후
    sort(arr, arr + n, greater<int>());
    printArray(arr, n); // 9 8 7 6 5 4 3 2 1 0


    return 0;
}

예제2: vector 컨테이너 정렬하기

#include <iostream>
#include <algorithm> // sort
#include <vector>
#include <cstdlib> // rand, srand
#include <ctime> // time
using namespace std;

void print(vector<int>& v, const int n) {
    for (int i = 0; i < n; i++)
        cout << v[i] << " ";
    cout << endl;
}
int main() 
{
    srand((int)time(NULL)); // 항상 변하는 seed값으로 rand 함수 초기화

    vector<int> v;
    const int n = 10;

    for (int i = 0; i < n; i++) {
        // 0~(n-1) 범위의 난수를 생성해서 벡터에 추가
        v.push_back(rand() % n); 
    }
    
    // 정렬 전
    print(v, n);

    // [begin, end) 내림차순 정렬
    sort(v.begin(), v.end(), greater<int>()); 

    // 정렬 후
    print(v, n);

    return 0;
}

실행 결과 (중복되는 원소들의 순서는 보장되지 않는다.)

예제3: compare 함수 정의해서 정렬하기

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

class Person {
public:
    string name;
    int age;
    Person(string name, int age) : name(name), age(age) {}
};

void print(vector<Person>& v) {
    for (int i = 0; i < 5; i++)
        cout << "[" << v[i].name << ", " << v[i].age << "] ";
    cout << endl;
}

bool compare(Person a, Person b) {
    // 이름이 같을 경우, 나이 순으로 정렬
    if (a.name == b.name)
        return a.age < b.age; // a가 b보다 나이가 적으면 true

    // 이름이 다르면, 알파벳 순으로 정렬
    return a.name < b.name; // a가 b보다 사전 순으로 더 앞에 오면 true
}


int main(void) {
    vector<Person> v;

    v.push_back(Person("cc", 40));
    v.push_back(Person("ba", 10));
    v.push_back(Person("aa", 32));
    v.push_back(Person("cc", 22));  // cc는 이름이 같으므로 나이순 정렬
    v.push_back(Person("bb", 55));

    print(v); 

    // [begin, end) 사용자 정의 함수 compare를 기준으로 정렬
    sort(v.begin(), v.end(), compare); 

    print(v);

    return 0;

}

예제4: 연산자 오버로딩으로 객체 정렬하기

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

class Student {
public:
    string name;
    int age;
    Student(string name, int age) :name(name), age(age) {}

    // 연산자 오버로딩 (operator overloading)
    bool operator < (Student s) const {
        if (this->name == s.name)
            return this->age < s.age;

        return this->name < s.name;
    }
};

void print(vector<Student>& v) {
    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));
    v.push_back(Student("bb", 21));

    print(v); // 정렬 전 출력

    // 연산자 오버로딩으로 객체 정렬
    sort(v.begin(), v.end());

    print(v); // 정렬 후 출력

    return 0;
}