정렬 Sort C++

개요

정렬은 배열이나 벡터의 인자들을 내가 원하는 대로 순서를 재배치 할 수 있다.

C++에서는 algorithm 클래스를 include 해주어야 사용 가능하고 파이썬의 경우에는 내장 함수로 사용 가능하다.

lambda등과 결합하면 꽤나 큰 효과를 볼 수 있다.

 

예제

1. 배열의 정렬

코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[11] = { 1, 33, 77, 13, 21, 67, 91, 21, 17, 93, 99 };
int main() {
	sort(arr, arr + 11);
	for (int i = 0; i < 11; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";
}

 

출력

1 13 17 21 21 33 67 77 91 93 99

 

2. 벡터의 정렬

코드

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

using namespace std;

vector<int> v = {1, 33, 77, 13, 21, 67, 91, 21, 17, 93, 99 };
int main() {
	sort(v.begin(), v.end());
	for (int i = 0; i < 11; i++) {
		cout << v[i] << " ";
	}
	cout << "\n";
}

 

출력

1 13 17 21 21 33 67 77 91 93 99

 

3. 내림차순 정렬

코드

내장 함수 사용

sort(v.begin(), v.end(), greater<int>()); // greater<int>() 를 넣어주면 내림차순으로 정렬 됨

 

커스텀 함수 사용

bool cmp(int left, int right) {
	return left > right;
}

 

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

 

 

출력

99 93 91 77 67 33 21 21 17 13 1

 

4. 커스텀 정렬

원하는 정렬 방식을 직접 함수를 구현하여 적용할 수 있다. 아래 예시는 짝수를 우선적으로 왼쪽으로 밀고 이후 오름차순으로 정렬하는 함수를 구현하여 적용한 케이스

 

코드

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

using namespace std;

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
bool cmp(int left, int right) {
	// 1. 짝수 우선
	if (left % 2 == 0 && right % 2 == 1) return true;
	if (left % 2 == 1 && right % 2 == 0) return false;
	// 2. 숫자 크기 비교 left < right
	if (left < right) return true;
	if (left > right) return false;
	return false;
}
int main() {
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < 11; i++) {
		cout << v[i] << " ";
	}
}

 

출력

2 4 6 8 10 1 3 5 7 9 11

 

5. 구조체 정렬

코드

Case. 1 커스텀 함수 사용

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

using namespace std;

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
struct rnwhcp {
	int row, col;
};

bool cmp_rnwhcp(rnwhcp left, rnwhcp right) {
	//1. row 가 큰것 우선
	if (left.row > right.row) return true;
	if (left.row < right.row) return false;
	//2. col 이 작은 것 우선
	if (left.col < right.col) return true;
	if (left.col > right.col) return false;
	return false;
}
int main() {
	rnwhcp rnwh[4] = {
		{1, 4},
		{1, 3},
		{4, 3},
		{5, 4}
	};

	sort(rnwh, rnwh + 4, cmp_rnwhcp);

	for (int i = 0; i < 4; i++) {
		cout << rnwh[i].row << " , " << rnwh[i].col << "\n";
	}
}

 

 

Case. 2 < 연산자를 직접 오버로딩

bool operator<(rnwhcp left, rnwhcp right) {
	//1. row 가 큰것 우선
	if (left.row > right.row) return true;
	if (left.row < right.row) return false;
	//2. col 이 작은 것 우선
	if (left.col < right.col) return true;
	if (left.col > right.col) return false;
	return false;
}

sort(rnwh, rnwh + 4); // 3번째 인자를 생략해도 됨

 

출력

5 , 4
4 , 3
1 , 3
1 , 4

 

P.S 구조체 초기화 시 직접 함수를 넣어놔도 된다.

struct rnwhcp {
	int row, col;
	bool operator<(rnwhcp right) {
		//1. row 가 큰것 우선
		if (row > right.row) return true;
		if (row < right.row) return false;
		//2. col 이 작은 것 우선
		if (col < right.col) return true;
		if (col > right.col) return false;
		return false;
	}
};