[Algorithm] C++ STL sort 함수

C++ 언어의 경우 훌륭한 정렬 관련 Library가 존재한다.

 

기본 사용법

Code - 기본

#include <iostream>
#include <algorithm> // sort()는 algorithm library에 포함되어있음
using namespace std;

int main(void){
    int a[10] = {4, 7, 6, 2, 1, 5, 8, 10, 3, 9};
    sort(a, a+10); // 정렬할 배열의 메모리 주소, 정렬할 마지막 원소의 메모리 주소
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

 

Code - 정렬할 기준 정하는 방식

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

// 오름차순 정렬
bool comp_up(int a, int b){ // true, false를 기준으로 정렬 기준을 판단
    return a < b; // a가 b보다 작으면 정렬
}

// 내림차순 정렬
bool comp_down(int a, int b){
    return a > b; // a가 b보다 크면 정렬
}

int main(void){
    int a[10] = {4, 7, 6, 2, 1, 5, 8, 10, 3, 9};
    sort(a, a+10, comp_up);
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    sort(a, a+10, comp_down);
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10 
10 9 8 7 6 5 4 3 2 1

 

Code - Data를 묶어서 정렬

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

// class: 하나의 객체를 정의함으로써 여러 개의 변수를 정의
// 일종의 새로운 자료형
class Student{
public:
    string name;
    int score;
    // 생성자: 특정 객체 초기화
    Student(string name, int score){
        this->name = name;
        this->score = score;
    }
    // 정렬 기준: 점수가 낮은 순서
    bool operator <(Student &student){
        return this->score < student.score;
    }
};

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

int main(void){
    // 5명의 학생
    Student students[] = {
        Student("student1", 90),
        Student("student2", 80),
        Student("student3", 79),
        Student("student4", 66),
        Student("student5", 78)
    };
    sort(students, students+5); // 이미 Class 안에 정렬 기준을 정의해두었으니 변수의 이름만 넣어주면 됨
    for(int i=0;i<5;i++)
        cout << students[i].name << " ";
    cout << endl;
    return 0;
}

출력

student4 student5 student3 student2 student1

 

Code - Pair library를 이용한 정렬

Vector: 마치 배열과 같이 작동하는데 원소를 선택적으로 삽입(Push) 및 삭제(Pop)할 수 있는 단순한 배열을 사용하기 쉽게 개편한 자료구조

Pair: 한 쌍의 데이터를 처리할 수 있도록 해주는 자료구조

#include <iostream>
#include <algorithm>
#include <vector> // 연결리스트 형태로 표현되는 자료구조
using namespace std;

int main(void){
    // 한 쌍의 데이터를 묶어서 사용할 수 있는 library
    // 기본적으로 first, second 인자를 가짐
    vector<pair<int, string>> v;
    v.push_back(pair<int, string> (90, "student1"));
    v.push_back(pair<int, string> (79, "student2"));
    v.push_back(pair<int, string> (88, "student3"));
    v.push_back(pair<int, string> (69, "student4"));
    v.push_back(pair<int, string> (95, "student5"));

    sort(v.begin(), v.end());

    for(int i=0;i<v.size();i++){
        cout << v[i].second << ' ';
    }
    return 0;
}

출력

student4 student2 student3 student1 student5

 

Code - 정렬 기준을 명시하는 Pair 사용

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

bool comp(pair<string, pair<int, int>> a,
          pair<string, pair<int, int>> b){
    // 성적이 같으면 생년월일이 더 느린 학생이 높은 우선순위 가짐
    if(a.second.first == b.second.first)
        return a.second.second > b.second.second;
    // 성적이 다르면 성적이 더 높은 학생이 높은 우선순위 가짐
    else
        return a.second.first > b.second.first;
}

int main(void){
    vector<pair<string, pair<int, int>>> v;
    v.push_back(pair<string, pair<int, int>> ("student1", pair<int, int>(90, 970416)));
    v.push_back(pair<string, pair<int, int>> ("student2", pair<int, int>(87, 990722)));
    v.push_back(pair<string, pair<int, int>> ("student3", pair<int, int>(93, 891130)));
    v.push_back(pair<string, pair<int, int>> ("student4", pair<int, int>(87, 920631)));
    v.push_back(pair<string, pair<int, int>> ("student5", pair<int, int>(84, 950718)));

    sort(v.begin(), v.end(), comp);

    for(int i=0;i<=v.size();i++)
        cout << v[i].first << ' ';
    return 0;
}

출력

student3 student1 student2 student4 student5