C++ STL 정리 - 정렬

C++ 의 알고리즘 라이브러리에서 제공되는 정렬은 3가지가 있다

 

1. sort()

: 퀵소트를 기반으로하는 일반적인 정렬 방식이다.

sort() 함수 사용시 주의할 점은 RandomAccessIterator 타입만 사용이 가능하다

STL 의 컨테이너 중 Vector, Deque 만 사용 가능하다.

다른 타입의 컨테이너를 사용하면 오류발생.

 

- 기본연습문제

1. 수 정렬하기 2 www.acmicpc.net/problem/2751

(예시 코드)

#include <bits/stdc++.h>
 
#define endl "\n"
 
using namespace std;
 
int n;
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    cin >> n;
    vector<int> vec(n, 0);
    for (int i = 0; i < n; ++i) cin >> vec[i];
    
    sort(vec.begin(), vec.end());
    
    for (int i = 0; i < n; ++i) cout << vec[i] << endl; 
    return 0;
}

 

2. 수 정렬하기 4 www.acmicpc.net/problem/11931

(예시코드)

 

#include <bits/stdc++.h>
 
#define endl "\n"
 
using namespace std;
 
int n;
vector<int> vec;
 
bool comp(int& a, int& b) {
    return a > b;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        vec.push_back(num);
    }
    
    sort(vec.begin(), vec.end(), comp);
    
    for (int i = 0; i < vec.size(); ++i) cout << vec[i] << endl;
    
    return 0;
}

 

2. stable_sort()

: 정렬을 하긴 하되, 원소들의 그 순서를 보존하는 방식으로 정렬을 수행한다.

 

- 기본연습문제

: 나이순 정렬 www.acmicpc.net/problem/10814

 

위 문제를 보면 나이를 오름차순으로 정렬하되, 나이가 만약 같은 경우, 먼저 가입한 사람 (입력이 먼저된) 순서대로 정렬할것을 요구하고 있다.

이때 가장 간편하게 쓸 수 있는게 stable_sort() 이다. 

아래와 같이 코드를 작성해주면, 나이순으로 정렬하되, 나이가 동일할때 이름에 대한 입력 순서는 그대로 유지한다.

 

(예제 코드)

#include <bits/stdc++.h>
 
#define endl "\n"
 
using namespace std;
 
int n;
vector<pair<int, string>> vec;
 
bool comp(pair<int, string>& p1, pair<int, string>& p2) {
    return p1.first < p2.first;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int age;
        string name;
        cin >> age >> name;
        vec.push_back(make_pair(age, name));
    }
    
    stable_sort(vec.begin(), vec.end(), comp);
    
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i].first << " " << vec[i].second << endl;
    }
    
    return 0;
}

 

3. partial_sort()

: 일부분만 정렬하는 함수로, 기본적으로 다음과 같이 3개의 인자를 받는다

std::partial_sort(start, middle, end);

 

전체 범위 [start, end) 사이에서, [start, middle) 까지만 오름 차순으로 정렬시키고 나머지 뒷 부분은 랜덤하게 남게되는 정렬 방식이다.

 

(예시 코드)

#include <bits/stdc++.h>
 
#define endl "\n"
 
using namespace std;
 
int n = 10;
vector<int> vec;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    for (int i = 0; i < n; ++i) {
        int score;
        cin >> score;
        vec.push_back(score);
    }
    
    partial_sort(vec.begin(), vec.begin() + 5, vec.end());
    
    for (int i = 0; i < n; ++i) 
        cout << vec[i] << " ";
    
    return 0;
}

 

 

 

 

- 참조

modoocode.com/225#page-heading-1