정렬

• sort사용

퀵 정렬 (sort)

오름차순

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

using namespace std;

template <typename T>
void print_vector_all(vector<T>& vec) {
	for (typename vector<T>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {
	vector<int> vec = { 7, 6, 3, 5, 4, 1, 2, 0, 8 };
	sort(vec.begin(), vec.end());
	print_vector_all(vec);
	return 0;
}

내림차순

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

using namespace std;

template <typename T>
void print_vector_all(vector<T>& vec) {
	for (typename vector<T>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {
	vector<int> vec = { 7, 6, 3, 5, 4, 1, 2, 0, 8 };
    //내림차순 greater<int>() 넣기
	sort(vec.begin(), vec.end(), greater<int>());
	print_vector_all(vec);

	return 0;
}

사용자 정의 기준 정렬

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

using namespace std;

struct Person {
	string name;
	int age;
	int height;
	int weight;
};

void print_person_all(vector<Person>& vec) {
	for (vector<Person>::iterator it = vec.begin(); it != vec.end(); ++it) {
		cout << "이름: " << it->name << " 나이: " << it->age << " 키: " << it->height << " 몸무게: " << it->weight << endl;
	}
}

//나이 오름차순
bool compare(const Person& lhs, const Person& rhs) {
	return lhs.age < rhs.age;
}

int main() {
	Person p[5] = {
		{"Brain", 24, 180, 70},
		{"Jessica", 22, 165, 55},
		{"James", 30, 170, 65},
		{"Tom", 12, 155, 46},
		{"Mary", 18, 172, 62},
	};

	vector<Person> vec;
	vec.push_back(p[0]);
	vec.push_back(p[1]);
	vec.push_back(p[2]);
	vec.push_back(p[3]);
	vec.push_back(p[4]);

	cout << "----정렬전----" << endl;
	print_person_all(vec);
	cout << endl;

	//첫번째 인자로 전달한 벡터의 나이 정보가 두번째 인자로 전달한 벡터의 나이정보보다 작으면
	//(lhs.age < rhs.age)True를 반환
    //compare 함수 기준으로 비교해서 정렬
	sort(vec.begin(), vec.end(), compare);

	cout << "----정렬후----" << endl;
	print_person_all(vec);
	return 0;
}

안정정렬(stable_sort)

• 안정정렬: 같은 원소가 정렬 후에도 원본의 순서와 일치
• 분안정정렬: 같은 원소가 정렬후에는 원본의 순서와 불일치 (퀵정렬)

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

using namespace std;

bool compare_pairs(const pair<int, string>& a, const pair<int, string>& b) {
	return a.first < b.first;
}

int main() {
	vector<pair<int, string>> pairs = {
		{5, "apple"},
		{2, "orange"},
		{5, "banana"},
		{3, "grape"}
	};

	stable_sort(pairs.begin(), pairs.end(), compare_pairs);

	for (vector < pair<int, string>>::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
		const pair<int, string>& pair = *it;
		cout << pair.first << ": " << pair.second << endl;
	}

	return 0;
}

부분 정렬 (partial_sort)

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

using namespace std;

int main() {
	vector<int> numbers = { 7, 2, 5, 1, 8, 9, 3, 6, 4 };

	//앞에 3개만 정렬 1 2 3은 확정
	//뒤에는 정렬 x
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());

	for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) {
		cout << *it << " ";
	}
	return 0;
}

찾기 & 이진탐색

찾기

• distance : 두 반복자 사이의 거리(원소개수)를 계산하는 함수
• find : target과 일치하는 첫번째 원소를 가르키는 반복자를 반환

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

using namespace std;

int main() {
	vector<int> numbers = { 1, 2, 3, 4, 5 };

	cout << "찾고싶은 숫자를 입력하세요: ";
	int target;
	cin >> target;

	//해당 숫자를 찾고, 그 위치를 출력
	//target과 일치하는 첫번째 원소를 가르키는 반복자를 반환
	vector<int>::iterator it = find(numbers.begin(), numbers.end(), target);

	if (it != numbers.end()) {
		//distance : 두 반복자 사이의 거리(원소개수)를 계산하는 함수
		cout << "찾은 위치: " << distance(numbers.begin(), it) << endl;
	}
	else {
		cout << "찾을 수 없음" << endl;
	}
	return 0;
}

• 연산자 오버로딩 operator== 오버로딩

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

using namespace std;

class my_class {
public:
	int value;
	string name;

	//find 함수는 비교할 때 ==연산 함
	//==연산자 오버로딩
	bool operator==(const my_class& other) const {
		return value == other.value && name == other.name;
	}
};

int main() {
	vector<my_class> objects = {
		{1, "one"},
		{2, "two"},
		{3, "three"},
		{4, "four"},
		{5, "five"}
	};

	//== 연산자 오버로딩 함수 탐
	vector<my_class>::iterator it = find(objects.begin(), objects.end(), my_class{ 3, "three" });

	if (it != objects.end()) {
		cout << "찾은 위치: " << distance(objects.begin(), it) << endl;
	}
	else {
		cout << "찾을 수 없음" << endl;
	}
	return 0;
}

이진탐색

• 정렬되어있어야 함
• 정렬되어있지 않으면 결과가 불확실 하거나 실패

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	vector<int> numbers = { 8, 3, 1, 7, 4, 5, 9, 2, 6 };

	//정해진 범위에서 빠른 이진탐색을 수행함으로
	//binary_search를 사용하려면 정렬해야함
	//정렬하지 않으면 결과가 불확실하거나 실패함
	sort(numbers.begin(), numbers.end());

	int target;
	cout << "검색하고싶은 숫자를 입력하세요: ";
	cin >> target;

	bool found = binary_search(numbers.begin(), numbers.end(), target);

	if (found) {
		cout << "찾음" << endl;
	}
	else {
		cout << "못찾음" << endl;
	}
	return 0;
}