17 일차

정렬과 탐색 (std::sort() 함수 사용)

∙std::sort() 함수

- 순차 컨테이너에 대해 (first, last) 범위의 원소들을 정해진 방법으로 정렬(기본값 : 오름차순)

- 같은 값을 갖는 원소의 순서는 보장되지 않음(순서를 유지하려면 std::stable_sort() 함수 사용)

- std::sort() 함수는 O(n log n)으로 동작해야 하며, 실제 구현은 컴파일러에 따라 다를 수 있음

- C 스타일 배열, vector, deque, array를 정렬할 때 주로 사용 (list, forward_list는 자체 멤버 함수 사용)

- comp 인자에 비교 함수 객체를 전달할 수 있음

- <algorithm>에 정의되어 있음

 

∙ 소스 코드 (오름차순 정렬)

#include <algorithm>
#include <vector>

int main()
{
	int arr[5] = {4, 2, 3, 5, 1};
    sort(arr, arr + 5); //[1, 2, 3, 4, 5]
    // sort(begni(arr), end(arr)); // 이런 형식도 가능함
    
    // vector를 사용한 정렬
    vector<string> vec = {"orange", "banana", "apple", "lemon"};
    sort(vec.begin(), vec.end()); // ["apple", "banana", "lemon", "orange"]
}

 

∙ 소스 코드 (내림차순 정렬)

#include <algorithm>
#include <vector>

int main()
{
	int arr[5] = {4, 2, 3, 5, 1};
    sort(begni(arr), end(arr), greater<>()); //[5, 4, 3, 2, 1]
    
    // vector를 사용한 정렬
    vector<string> vec = {"orange", "banana", "apple", "lemon"};
    sort(vec.begin(), vec.end(), greater<>()); //["orange", "lemon", "banana", "apple"]
}

 

∙ 소스 코드 (함수 포인터)

bool abs_cmp(const int a, const int b)
{
	return std::abs(a) < std::abs(b);
}

int main()
{
	vector<int> nums = {10, 2, -3, 5, 7}
    sort(nums.begin(), nums.end(), abs_cmp); // [2, -3, 5, 7, 10] 절대값 정렬
}

 

∙ 소스 코드 (오버로딩한 객체의 정렬)

// 클래스 정의
class Person
{
public:
	string name;
    int age;
    
    void print() const
    {
    	cout << name << ", " << age << endl;
    }
};

int main()
{
	vector<Person> v;
    v.push_back({"Olivia", 29});
    v.push_back({"Sophia", 40});
    
    sort(v.begin(), v.end()); // 여기서 에러가 생김 (어떤 기준을 정렬을 해야할지 모르기때문)
    
    for (auto& p : v)
    	p.print():
    
}

- sort 오류 해결 코드

// 클래스 정의
class Person
{
public:
	string name;
    int age;
    
    // 사람의 age로 비교하라고 정의하면 된다
    bool operator<(const Person& a) const
    {
    	return this -> age < a.age;
    }
    
    void print() const
    {
    	cout << name << ", " << age << endl;
    }
};

int main()
{
	vector<Person> v;
    v.push_back({"Olivia", 29});
    v.push_back({"Sophia", 40});
    
    sort(v.begin(), v.end()); // age으로 정렬
    
    for (auto& p : v)
    	p.print():
    
}

 

 

∙ 전체 실습 소스 코드

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Person
{
public:
	string name;
	int age;

	bool operator<(const Person& p) const
	{
		return this->age < p.age;
	}

	void print() const
	{
		cout << name << ", " << age << endl;
	}
};

bool abs_cmp(const int a, const int b)
{
	return std::abs(a) < std::abs(b);
}

int main()
{
	// 배열의 정렬

	int arr[5] = {4, 2, 3, 5, 1};
	sort(arr, arr + 5); // 오름 차순, [1, 2, 3, 4, 5]
//	sort(begin(arr), end(arr)); // std::begin(), std::end()
//	sort(begin(arr), end(arr), greater<>()); // 내림 차순, [5, 4, 3, 2, 1]

	for (const auto& a : arr)
		cout << a << ", ";
	cout << endl;

	// 벡터의 정렬

	vector<string> vec = {"orange", "banana", "apple", "lemon"};
	sort(vec.begin(), vec.end()); // ["apple", "banana", "lemon", "orange"]
//	sort(vec.begin(), vec.end(), less<>()); // ["apple", "banana", "lemon", "orange"]
//	sort(vec.begin(), vec.end(), greater<>()); // ["orange", "lemon", "banana", apple"]
//	sort(begin(vec), end(vec));

	for (const auto& a : vec)
		cout << a << ", ";
	cout << endl;

	// 비교 방법 지정 예제

	struct AbsCmp {
		inline bool operator()(int a, int b) const
		{
			return std::abs(a) < std::abs(b);
		}
	};

	vector<int> nums = {10, 2, -3, 5, 7};
	sort(nums.begin(), nums.end(), AbsCmp());  // [2, -3, 5, 7, 10]
//	sort(nums.begin(), nums.end(), abs_cmp);  // [2, -3, 5, 7, 10]
//	sort(nums.begin(), nums.end(), [](int a, int b) {
//		return std::abs(a) < std::abs(b);
//	});  // [2, -3, 5, 7, 10]

	for (const auto& a : nums)
		cout << a << ", ";
	cout << endl;

	// 비교 연산자를 오버로딩한 클래스 객체의 정렬
	vector<Person> v;
	v.push_back({"Amelia", 29});
	v.push_back({"Noah", 25});
	v.push_back({"Olivia", 31});
	v.push_back({"Sophia", 40});
	v.push_back({"George", 35});

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

	for (const auto& p : v)
		p.print();
}