[자료구조] c++ sort함수를 활용한 정렬

안녕하세요 주인장 H입니다. 

오늘은 기존에 배운 정렬보다 좀더 빠르고 쉽게 정렬을 진행하려 합니다. 

 

sort함수는 기본적으로 quicksort와 유사하게 진행 되지만 차이점으로 

O(log N * N)가 보장된다는 장점이 있죠 

 

간단하게 예시 코드를 보겠습니다. 

#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;
	}
};

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

int main(void) {
	Student students[] = {
		Student("kim",90),
		Student("choi",93),
		Student("pack",97),
		Student("heo",87),
		Student("lee",92),
	};

	sort(students, students + 5);
	for (int i = 0; i < 5; i++) {
		cout << students[i].name << ' ';
	}
}

 주석처리된 compare 함수를 이용하면 오름차순과 내림차순으로 정렬이 가능하지만, 지금은 class 내 비교군이 없기 때문에 사용하진 않겠습니다. 

 

하지만 class는 실제 실무에서 많이 쓰이고 알고리즘 대회에선 shotcoding 이 중요하기 때문에 사용하진 않는다고 합니다. 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 

//백터 라이버리리와 페어 라이브러리를 이용한 숏코딩
int main(void) {
	vector<pair<int, string>> v; 
	v.push_back(pair<int, string>(90,"park"));
	v.push_back(pair<int, string>(85, "lee"));
	v.push_back(pair<int, string>(82, "na"));
	v.push_back(pair<int, string>(87, "kang"));
	v.push_back(pair<int, string>(79, "choi"));

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

이렇게 벡터와 페어 라이브러리를 이용하면 훨신 빠르게 코드를 짜실 수 있습니다. 

 

그럼 마지막으로 세가지 데이터를 비교해보는 코드를 적어보겠습니다. 

//학생을 나타낼 수 있는 정보가 이름, 성적,생년월일일 때
//학생을 성적 순서대로 나열하고자 한다. 
//다만 성적이 동일한 경우 나이가 더 어린 학생이 더 우선순위가 높다. 

//먼저 성적에 따라 정렬 후, 성적이 같은 경우 나이가 더 어린 사람

#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(void) {
	vector<pair<string, pair<int, int>>> v;
	v.push_back(pair<string, pair<int, int>>("나동빈", make_pair(90, 19961212)));
	v.push_back(pair<string, pair<int, int>>("이태일", make_pair(97, 19930518)));
	v.push_back(pair<string, pair<int, int>>("박한울", make_pair(95, 19930203)));
	v.push_back(pair<string, pair<int, int>>("이상욱", make_pair(90, 19921207)));
	v.push_back(pair<string, pair<int, int>>("강종구", make_pair(88, 19900302)));

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

 

해당 예제는 아래 프로그램을 따라 공부했습니다. 

https://blog.naver.com/ndb796/221227975229

8. C++ STL sort() 함수 다루기 ①