C++을 사용하여 $O(n\log n)$정도의 시간 복잡도를 가지는 sorting algorithm을 공부하고 구현하는 것은 쉽지가 않습니다.

가장 직접 알고리즘을 구현하는 것은 공부에 많은 도움이 되는 것은 분명하나, 간단한 프로젝트를 진행하면서도 불필요하게 모두 구현하는 것은 시간 낭비임이 분명합니다.

C++의 algorithm 헤더파일에는 sort() 함수가 있습니다.

이 함수는 C++ algorithm 헤더파일에서 제공하는 함수로 intro sort라는 algorithm으로 구현되어 있습니다.
quick sort는 일반적으로 $O(n\log n)$의 시간복잡도를 가지지만, 최악의 경우에 $O(n^2)$의 시간복잡도를 가집니다.
intro sort는 세 가지 정렬법(quick sort, heap sort, insertion sort)을 섞어 quick sort의 단점을 보완하여 어떤 상황에서도 $O(n\log n)$의 시간 복잡도를 가질 수 있는 정렬법입니다.

1. 사용법

sort(배열 시작 주소, 배열의 정렬할 마지막 인덱스, 정렬 함수);
sort(벡터 시작 iterator, 벡터 종료 iterator, 정렬 함수);

2. array 정렬

array 오름차순으로 기본 정렬

배열의 시작 주소와 끝 주소를 넣습니다.

#include <iostream>
#include <algorithm>

int main(){
    int a[]{1,9,2,3,5,7,4,17};
    
    for(int i:a) std::cout << i << ' ';
    std::cout << std::endl;

    std::sort(a, a + 8);
    
    for(int i:a) std::cout << i << ' ';
}

1 9 2 3 5 7 4 17 
1 2 3 4 5 7 9 17

array 내림차순으로 기본 정렬

일반 함수를 이용한 내림차순 정렬

#include <iostream>
#include <algorithm>

using namespace std;

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

int main(){
    int a[]{1,9,2,3,5,7,4,17};
    
    for(int i:a) cout << i << ' ';
    cout << endl;

    sort(a, a + sizeof(a)/sizeof(*a), compare); // 내림차순으로 정렬
    
    for(int i:a) cout << i << ' ';
}

람다 함수를 이용한 내림차순 정렬

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int a[]{1,9,2,3,5,7,4,17};
    
    for(int i:a) cout << i << ' ';
    cout << endl;

    sort(a, a + sizeof(a)/sizeof(*a), [](int a, int b){return a > b;}); // 내림차순으로 정렬
    
    for(int i:a) cout << i << ' ';
}

1 9 2 3 5 7 4 17
17 9 7 5 4 3 2 1

3. vector 정렬

vector 내림차순으로 정렬

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

int main(){
    vector< int > v{1,9,2,3,5,7,4,17};
    
    for(int i:v) cout << i << ' ';
    cout << endl;

    sort(v.begin(), v.end(), [](int a, int b){return a > b;}); // 내림차순으로 정렬
    
    for(int i:v) cout << i << ' ';
}

1 9 2 3 5 7 4 17 
17 9 7 5 4 3 2 1

사용자 규칙으로 vector 정렬

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

int main(){
    vector< int > v{1,9,2,3,5,7,4,17};
    
    for(int i:v) cout << i << ' ';
    cout << endl;

    sort(v.begin(), v.end(), [](int a, int b){ // 익명 함수를 이용한 compare
        if (a/10 > b/10){ // 왼쪽항의 십의 자리 수가 더 높다면
            return true; // 먼저 정렬한다.
        }
        else return a < b; // 그 외는 오름차순으로 정렬
    });
    
    for(int i:v) cout << i << ' ';
}

1 9 2 3 5 7 4 17 
17 1 2 3 4 5 7 9