[알고리즘 공부] sort (C++ STL)

C++ STL  ❯❯  sort()

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int a[10] = {9,3,5,4,1,10,8,6,7,2};
    sort(a, a+10);	// 메모리 주소를 넣어주면 됨
    for (int i = 0; i < 10; i++)
        cout << a[i] << ' ';
    
    return 0;
}

 

- sort 함수에는 메모리의 시작 주소, 시작주소 + 원소개수 를 넣어주면 됨.

- sort 함수가 강력한 이유: 정렬할 기준을 마음대로 정의할 수 있음.
   정렬할 기준을 매개변수에 넣어줘서 의도한 대로 정렬을 작동시킬 수 있음.

 

#include <iostream>
#include <algorithm>

using namespace std;

// a < b 일 때 true 반환 => 오름차순
bool compare1(int a, int b) {
    return a < b;
}

// a > b 일 때 true 반환 => 내림차순
bool compare1(int a, int b) {
    return a > b;
}

int main() {
    int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
    sort(a, a + 10, compare1);	// 1 2 3 4 5 6 7 8 9 10
    sort(a, a + 10, compare2);	// 10 9 8 7 6 5 4 3 2 1
    for (int i = 0; i < 10; i++)
        cout << a[i] << ' ';
    return 0;
}

 

위와 같은 단순 데이터 정렬 기법은 실무에서 사용하기에 부적합.

실무 프로그래밍 시에는 모든 데이터들이 객체로 정리되어 여러 개의 변수를 포함하고 있기 때문.

=> 특정한 변수를 기준으로 정렬하는 것이 가장 중요한 정렬 방식.

 

데이터를 묶어서 정렬하는 법

 

#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 <(const Student &student) {
        return this->score < student.score;
    }
};

bool compare(Student a, Student b) {
    return a.score > b.score;
}

int main() {
    Student students[] = {
        Student("강모씨", 90),
        Student("김모씨", 93),
        Student("노모씨", 97),
        Student("최모씨", 87),
        Student("이모씨", 92)
	};
    // sort(students, students + 5);		// 오름차순
    sort(students, students + 5, compare);	// 내림차순
    for (int i = 0; i < 5; i++)
        cout << students[i].name << ' ';
}

 

다만 클래스를 정의하는 방식은 실무에 적합한 방식이지, 속도 측면에서는 별로 유리하지 않음.

대회처럼 빠른 개발이 필요할 때는 페어(Pair) 라이브러리를 사용하는 것이 더 효율적.

 

변수가 2개일 때 '1개'의 변수를 기준으로 정렬하는 법

- 벡터, 페어 라이브러리 사용

#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());
    for (int i = 0; i < v.size(); i++) {
        cout << v[i].second << ' ';
    }
    return 0;
}

 

- vector STL은 배열과 같이 작동하면서 원소를 선택적으로 삽입(push), 삭제(pop) 할 수 있음.
  => 배열을 보다 사용하기 쉽게 개편한 자료구조

- pair STL은 한 쌍의 데이터를 처리할 수 있게 해주는 자료구조.

 

변수가 3개일 때 '2개'의 변수를 기준으로 정렬하는 법

Q. 학생의 이름, 성적, 생년월일에 대해 성적 순서대로 나열한다. 성적이 동일할 경우 나이가 더 어린 학생이 우선순위가 높다.

#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>>("강모씨", pair<int, int>(90, 19970507)));
    v.push_back(pair<string, pair<int, int>>("김모씨", pair<int, int>(97, 19961222)));
    v.push_back(pair<string, pair<int, int>>("노모씨", pair<int, int>(95, 19970924)));
    v.push_back(pair<string, pair<int, int>>("최모씨", pair<int, int>(90, 19970421)));
    v.push_back(pair<string, pair<int, int>>("이모씨", pair<int, int>(88, 19971226)));

    sort(v.begin(), v.end(), compare);
    for (int i = 0; i < v.size(); i++) {
        cout << v[i].first << ' ';
    }

    return 0;
}

 

※ 대회 Tip

• 2개 이하의 변수를 기준으로 할 때는 vector, pair를 함께 사용해 짧고 빠르게 풀자.
• 3개 이상의 변수를 기준으로 할 때부터는 pair를 사용하는게 더 복잡해질지도 - class 를 정의해서 푸는 게 더 나을 수 있음.