정렬(sorting) - C++ STL sort() 함수

sort()함수

C++에는 sort()라는 함수가 있는데, 실제 프로그래밍 대회나 실무에서는 정렬관련 문제가 나오면 C로 일일히 구현하기보단 이러한 sort() 함수를 사용한다고 한다. 나는 C++ 언어에 대해 아직 학습하지 않아서 이에 대해 알지 못했어서 놀라웠다. 더 이상 미루지말고 C++에 대해 학습해야겠다는 생각이 들었다.

 

그럼 sort() 함수에 대해 알아보자.

먼저 sort() 함수의 포맷은 sort(정렬할 배열의 시작 주소, 정렬할 배열의 끝 주소) 이다. 이해하기 쉽게 코드를 보면 아래와 같다. sort() 함수는 올림차순으로 정렬하는 것을 기본으로 한다.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main() {
    int a[10] = { 10,2,7,8,3,1,4,6,5,9 };
    sort(a, a + 10);
    //print sort
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
 
}

 

추가로, sort(정렬할 배열의 시작 주소, 정렬할 배열의 끝 주소, 정렬 기준) 과 같이 사용할 수 있는데, 이도 코드로 알아보면 아래와 같다.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
bool compare(int a, int b) {
    return a > b;
}
 
int main() {
    int a[10] = { 10,2,7,8,3,1,4,6,5,9 };
    sort(a, a + 10, compare);
    //print sort
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
 
}

위 코드를 실행하면 a>b인 compare의 조건대로 내림차순으로 정렬되게 된다.

 

그런데, 실무에서는 묶인 데이터들을 정렬하는 경우가 많다. 즉, 정렬할 데이터들이 객체로 정리되어 있어 내부적으로 여러개의 변수를 포함하고 있는 것인데, 이 경우에는 특정한 변수를 기준으로 정렬하는 것이 가장 중요하다. 아래와 같이 예제 코드를 살펴보자.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
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;
    }
};
 
int main() {
    Student students[] = { 
        Student("이준호",90), 
        Student("이재현",92), 
        Student("김주연",88), 
        Student("김인성", 91), 
        Student("톰홀랜드",81) };
 
    sort(students, students + 5);
 
    //print sort
    for (int i = 0; i < 5; i++) {
        cout << students[i].name << ' ';
    }
 
}

 

위 코드를 실행하면 점수가 작은 순서대로 "톰홀랜드 김주연 이준호 김인성 이재현"의 결과가 나온다.

 

추가로, '특정한 변수'를 기준으로 정렬하는 방법에 대해 알아보자.

위와 같이 클래스를 이용하는 방법은 속도 측면에서 유리하지 않기 때문에, 주로 실무에서 많이 쓰인다. 프로그래밍 대회 같은 경우는 클래스보다는 페어를 사용하는 것이 더 효율적이다.

그럼 예제 코드를 살펴보자.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    vector<pair<int, string>> v;
    v.push_back(pair<int, string>(90, "이재현"));
    v.push_back(pair<int, string>(85, "김주연"));
    v.push_back(pair<int, string>(82, "김인성"));
    v.push_back(pair<int, string>(98, "이준호"));
    v.push_back(pair<int, string>(79, "톰홀랜드"));
 
    sort(v.begin(), v.end());
 
    //print sort
    for (int i = 0; i < 5; i++) {
        cout << v[i].second << ' ';
   }
}

위 소스코드를 실행하면 '톰홀랜드 김인성 김주연 이재현 이준호'의 결과가 나온다. 위 소스코드는 벡터와 페어 라이브러리를 통해 클래스로 정렬하였던 것을 대체한 것이다. 이처럼 벡터와 페어를 사용해 쓴 코드가 클래스를 사용하는 것보다 소스코드의 길이가 짧아지는데, 이를 숏코딩이라고 한다.

 

벡터는 배열을 사용하기 쉽게 개편한 자료구조로 선택적으로 삽입(push), 삭제(pop)할 수 있다.

페어는 한 쌍의 데이터를 처리할 수 있도록 해주는 자료구조이다.

 

그러면 여러가지의 변수가 있을때 2개이상의 변수를 기준으로 정렬하는 방법에 대해 살펴보자.

아래는 변수가 3개일 경우 두개의 변수를 기준으로 정렬하는 문제이다.

 

학생이 이름, 성적, 생년월일의 정보를 가지고 있을 때 성적 순서대로 학생을 나열하시오.(이때, 성적이 동일한 경우 나이가 더 어린 학생이 우선순위가 더 높다.)

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool compare(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() {
    vector< pair<string, pair<int, int>>> v;
    v.push_back(pair<string, pair<int, int>>("이재현", make_pair(90,19961222)));
    v.push_back(pair<string, pair<int, int>>("김주연", make_pair(90, 19930518)));
    v.push_back(pair<string, pair<int, int>>("김인성", make_pair(95, 19990922)));
    v.push_back(pair<string, pair<int, int>>("이준호", make_pair(97, 19921207)));
    v.push_back(pair<string, pair<int, int>>("톰홀랜드", make_pair(88, 19951224)));
 
    sort(v.begin(), v.end(), compare);
 
    //print sort
    for (int i = 0; i < 5; i++) {
        cout << v[i].first << ' ';
    }
 
}

 

위 코드를 실행하면 '톰홀랜드 김주연 이재현 김인성 이준호'가 나온다.

 

이처럼 오늘은 C++ sort()함수에 대해 알아보았다. C++에 대해 학습해 본 적이 없어서 새로운 것들이 많았는데, 나중에 따로 C++을 학습해보아야겠다는 생각이 들었다.