📌 Sorting

• 특정 범위의 원소들을 특정 조건에 알맞게 순서를 정하는 것
• <algorithm> header
• std::sort

sort([first iterator], [last iterator], [compare])

[compare] default : less<[type]>()

• 범위에 해당하는 iterator와 비교 함수 필요
• 비교 함수가 없는 경우, 기본값으로 오름차순 정렬

---

✔ 일반 정렬

오름차순 정렬

// 배열 정렬
int arr[8] = { 3, 2, 1, 8, 3, 4, 5, 1 };
sort(arr, arr + 8);
for (int n : arr) cout << n << ' ';
cout << '\n';

// 문자열 정렬
string str = "eafdigbhc";
sort(str.begin(), str.end());
cout << str << '\n';

// 벡터 정렬
vector<string> words = { "cycle", "baseball", "aqua" };
sort(words.begin(), words.end());
for (string word : words)
	cout << word << ' ';

• output:

1 1 2 3 3 4 5 8
abcdefghi
aqua baseball cycle

• 타입에 관계없이 주어진 범위의 원소들을 오름차순으로 정렬
  
  

내림차순 정렬

vector<int> numbers = { 25, 61, 39, 93, 55 };
sort(numbers.begin(), numbers.end(), greater<int>());
for (int n : numbers)
	cout << n << ' ';

• output: 93 61 55 39 25
• 원소들의 타입 type에 대해 greater<type>()을 인자로 주는 경우, 오름차순으로 정렬

---

✔ 객체 정렬

pair & tuple 정렬

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

using namespace std;

int main()
{
	// pair 정렬
	pair<int, int> pairs[5] = {
		make_pair(30, 50),
		make_pair(20, 30),
		make_pair(30, 20),
		make_pair(30, 70),
		make_pair(20, 50)
	};

	sort(pairs, pairs + 5);
	
	cout << "정렬된 pair 배열: \n";
	for (pair<int, int> p : pairs)
		cout << p.first << ' ' << p.second << '\n';
	
	// tuple 정렬
	tuple<int, int, int> tuples[5] = {
		make_tuple(10, 20, 30),
		make_tuple(20, 60, 40),
		make_tuple(10, 30, 50),
		make_tuple(10, 20, 70),
		make_tuple(20, 40, 30)
	};

	sort(tuples, tuples + 5);

	cout << "\n정렬된 tuple 배열: \n";
	for (tuple<int, int, int> t : tuples)
		cout << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << '\n';

	return 0;
}

• output:

정렬된 pair 배열:
20 30
20 50
30 20
30 50
30 70

정렬된 tuple 배열:
10 20 30
10 20 70
10 30 50
20 40 30
20 60 40

• pair, tuple의 경우, 먼저 오는 값이 높은 우선순위로 정렬
• ex) 첫번째 값이 같은 경우, 두번째 값으로 오름차순
  
  

정렬 조건 설정

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

using namespace std;

// 절대값 기준 내림차순 비교 함수
bool comp(int x, int y) { return abs(x) > abs(y); }

int main()
{
	vector<int> numbers = { -6, -4, -2, 0, 1, 3, 5, 7 };
	sort(numbers.begin(), numbers.end(), comp);
	for (int n : numbers)
		cout << n << ' ';

	return 0;
}

• output: 7 -6 5 -4 3 -2 1 0
• bool type의 비교 함수를 직접 정의하여 인자로 주는 경우, 해당 조건에 알맞게 정렬 가능

vector<int> numbers = { -6, -4, -2, 0, 1, 3, 5, 7 };
sort(numbers.begin(), numbers.end(), [](int x, int y) { return abs(x) > abs(y); });
for (int n : numbers)
	cout << n << ' ';

• output: 7 -6 5 -4 3 -2 1 0
• 위와 같이 람다식으로도 설정 가능
  
  

구조체 정렬

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

using namespace std;

struct Person
{
	string name;
	int age; 
};

// 나이 내림차순, 이름 오름차순 비교 함수
bool comp(Person x, Person y) { return x.age != y.age ? x.age > y.age : x.name < y.name; }

int main()
{
	vector<Person> people = {
		{ "Mike", 26 },
		{ "Alice", 30 },
		{ "Lisa", 27 },
		{ "Peter", 30 }
	};

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

	for (Person p : people)
		cout << p.name << '(' << p.age << ")\n";

	return 0;
}

• output:

Alice(30)
Peter(30)
Lisa(27)
Mike(26)

• 구조체의 경우, 정렬 조건을 정의한 비교 함수가 항상 필요
• 구조체에 대한 복잡한 조건 설정 가능

// 나이 내림차순, 이름 오름차순 비교 함수
bool comp(Person x, Person y) { return make_pair(-x.age, x.name) < make_pair(-y.age, y.name); }

• 차순 기준이 두개인 경우 위와같이 pair로 묶어서 조건 설정 가능

sort(people.begin(), people.end(), 
		[](Person x, Person y) { return x.age != y.age ? x.age > y.age : x.name < y.name; });

• 위와 같이 람다식으로도 설정 가능