개인적인 공부 목적으로 정리한 내용입니다.
☁ 기본적인 사용법과 사용자 정의 비교 함수를 사용한 다양한 예시를 포함하였다.
sort() 함수
C++의 sort() 함수는 STL(Standard Template Library, 표준 템플릿 라이브러리)의 알고리즘 라이브러리에 포함된 함수로, 배열이나 벡터와 같은 컨테이너의 요소들을 정렬하는 데 사용된다.
지정된 범위에 있는 요소는 기본적으로 오름차순으로 정렬되며, 커스텀(사용자 정의) 비교 함수를 사용하여 다양한 방식으로 정렬할 수 있기 때문에 자주 사용되는 함수다.
🔎 참고로 sort()는 안정 정렬이 아니다!
안정 정렬이란?
비교하는 두 값이 동일할 경우 원래의 순서를 유지하면서 정렬한다.
sort()경우 안정 정렬을 지원하지 않으므로 안정 정렬을 하려면 stable_sort()를 이용하자.
(예시들 중 stable_sort()도 추가했습니다.)
sort() 함수의 헤더파일 및 사용
- #include <algorithm>
- sort()는 알고리즘 라이브러리에 정의된 함수이다.
- using namespace std; 를 사용하면 std::sort() 대신 sort() 로 간략하게 사용이 가능하다. (네임스페이스 생략)
- std::sort(시작 주소, 끝 주소)
- std::sort(시작 주소, 끝 주소, 사용자 정의 조건 함수)
간단한 sort() 사용 예시
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2};
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);
for(int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
// 💻출력: 1 1 2 3 4 5 9
return 0;
}
sort() 기본 사용법
배열 정렬 (오름차순 / 내림차순)
- 배열을 오름차순으로 정렬하는 방법
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2};
int n = sizeof(arr) / sizeof(arr[0]);
/* 오름차순 */
sort(arr, arr + n);
for(int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
// 💻출력: 1 1 2 3 4 5 9
return 0;
}
- 배열을 내림차순으로 정렬하는 방법
1. std::greater<> 이용
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2};
int n = sizeof(arr) / sizeof(arr[0]);
/* 내림차순 */
sort(arr, arr + n, greater<int>());
for(int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
// 💻출력: 9 5 4 3 2 1 1
return 0;
}✒ std::greater<>란?
std::greater<>는 비교 함수 객체로, 기본적으로 > 연산자를 활용하여 두 값의 순서를 결정한다.
2. 배열을 정렬한 후, std::reverse()를 이용해 뒤집기
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2};
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n); // 오름차순 정렬
reverse(arr, arr + n); // 배열 뒤집기
for(int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
// 💻출력: 9 5 4 3 2 1 1
return 0;
}
벡터 정렬 (오름차순 / 내림차순)
- 벡터를 오름차순으로 정렬하는 방법
int main() {
vector<int> vec = {3, 1, 4, 1, 5, 9, 2};
/* 오름차순 */
sort(vec.begin(), vec.end());
for(int i : vec) {
cout << i << " ";
}
// 💻출력: 1 1 2 3 4 5 9
return 0;
}
- 벡터를 내림차순으로 정렬하는 방법
1. 역방향 반복자 이용 (rbegin(), rend())
int main() {
vector<int> vec = {3, 1, 4, 1, 5, 9, 2};
/* 내림차순 */
sort(vec.rbegin(), vec.rend());
for(int i : vec) {
cout << i << " ";
}
// 💻출력: 9 5 4 3 2 1 1
return 0;
}
2. greater<> 이용
int main() {
vector<int> vec = {3, 1, 4, 1, 5, 9, 2};
/* 내림차순 */
sort(vec.begin(), vec.end(), greater<int>());
for(int i : vec) {
cout << i << " ";
}
// 💻출력: 9 5 4 3 2 1 1
return 0;
}
부분 정렬
- 컨테이너의 일부 범위만 정렬하는 방법
int main() {
vector<int> vec = {3, 1, 4, 1, 5, 9, 2};
/* 벡터의 처음부터 4번째 요소까지만 정렬 */
sort(vec.begin(), vec.begin() + 4);
for(int i : vec) {
cout << i << " ";
}
// 💻출력: 1 1 3 4 5 9 2
return 0;
}
구조체 또는 클래스 객체 정렬
객체를 정렬할 때는 멤버 변수 또는 조건에 따라 정렬할 수 있다.
- 객체를 정렬하는 방법 (User 구조체를 정렬하는 예시)
struct User {
string name;
int score;
};
/* 정렬 기준: 점수 기준으로 오름차순 */
bool compare(User a, User b) {
return a.score < b.score;
}
int main() {
vector<User> users = {
{"김전사", 400},
{"이궁수", 200},
{"박법사", 450}
};
/* compare함수 조건에 맞게 정렬 */
sort(users.begin(), users.end(), compare);
for(const auto& user : users) {
cout << user.name << " " << user.score << "\n";
}
// 💻출력: 이궁수 200
// 김전사 400
// 박법사 450
return 0;
}
안정 정렬 (stable_sort)
sort()는 안정 정렬이 아니다.
안정 정렬이 필요하다면 stable_sort()를 사용하자.
- stable_sort()을 이용해 안정 정렬하는 방법
struct User {
string name;
int score;
};
int main() {
vector<User> users = {
{"김전사", 400},
{"이궁수", 200},
{"박법사", 400},
{"김오크", 200}
};
/* 안정 정렬 */
stable_sort(users.begin(), users.end(), [](User a, User b) {
return a.score < b.score;
});
for(const auto& user : users) {
cout << user.name << " " << user.score << "\n";
}
// 💻출력: 이궁수 200
// 김오크 200
// 김전사 400
// 박법사 400
return 0;
}
sort() 사용자 정의 비교 함수 사용법
짝수 우선 정렬
- 짝수를 우선으로 정렬하고, 짝수끼리는 오름차순, 홀수끼리는 내림차순으로 정렬하는 방법
bool customSort(int a, int b) {
if (a % 2 == 0 && b % 2 != 0) {
return true; // a가 짝수이고 b가 홀수면 a가 앞에 온다
} else if (a % 2 != 0 && b % 2 == 0) {
return false; // b가 짝수이고 a가 홀수면 b가 앞에 온다
} else if (a % 2 == 0 && b % 2 == 0) {
return a < b; // 둘 다 짝수면 오름차순
} else {
return a > b; // 둘 다 홀수면 내림차순
}
}
int main() {
vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 7};
sort(vec.begin(), vec.end(), customSort);
for(int i : vec) {
cout << i << " ";
}
// 💻출력: 2 4 6 9 7 5 3 1 1
return 0;
}
절댓값 기준 정렬
- 절대값 기준으로 정렬하는 방법
bool compare(int a, int b) {
return abs(a) < abs(b);
}
int main() {
vector<int> vec = {3, -1, 4, -1, 5, -9, 2};
sort(vec.begin(), vec.end(), compare);
for(int i : vec) {
cout << i << " ";
}
// 💻출력: -1 -1 2 3 4 5 -9
return 0;
}
문자열 길이 기준 정렬
- 문자열의 길이를 기준으로 정렬하는 방법 (길이가 같은 경우는 사전순으로 정렬)
bool customSort(const string &a, const string &b) {
if (a.length() == b.length()) {
return a < b; // 길이가 같으면 사전순으로 정렬
}
return a.length() < b.length(); // 길이가 다르면 짧은 것부터 정렬
}
int main() {
vector<string> vec = {"apple", "banana", "pear", "grape", "kiwi"};
sort(vec.begin(), vec.end(), customSort);
for(const string &s : vec) {
cout << s << " ";
}
// 💻출력: kiwi pear apple grape banana
return 0;
}
문자열의 마지막 문자 기준 정렬
- 문자열의 마지막 문자를 기준으로 정렬하는 방법. 만약 마지막 문자가 같다면 전체 문자열을 사전순으로 정렬.
bool customSort(const string &a, const string &b) {
if (a.back() == b.back()) {
return a < b; // 마지막 문자가 같으면 사전순으로 정렬
}
return a.back() < b.back(); // 마지막 문자 기준으로 정렬
}
int main() {
vector<string> vec = {"apple", "banana", "cherry", "kiwi", "grape"};
sort(vec.begin(), vec.end(), customSort);
for(const string &s : vec) {
cout << s << " ";
}
// 💻출력: banana apple grape kiwi cherry
return 0;
}
2차원 좌표 정렬
- 2차원 좌표를 (x, y) 순으로 정렬하고, x가 같으면 y를 기준으로 오름차순으로 정렬하는 방법
struct Point {
int x, y;
};
bool customSort(const Point &a, const Point &b) {
if (a.x == b.x) {
return a.y < b.y; // x가 같으면 y 기준으로 정렬
}
return a.x < b.x; // x가 다르면 x 기준으로 정렬
}
int main() {
vector<Point> points = {{3, 4}, {1, 2}, {3, 2}, {2, 2}, {2, 3}};
sort(points.begin(), points.end(), customSort);
for(const Point &p : points) {
cout << "(" << p.x << ", " << p.y << ") ";
}
// 💻출력: (1, 2) (2, 2) (2, 3) (3, 2) (3, 4)
return 0;
}
구조체의 두 멤버를 복합적으로 사용한 정렬
- 두 멤버 변수를 사용하여 복합적으로 정렬하는 방법. (예를 들어, 유저들의 레벨과 점수로 정렬하고, 레벨이 같으면 점수로 정렬하는 방식)
struct User {
string name;
int level;
int score;
};
bool customSort(const User &a, const User &b) {
if (a.level == b.level) {
return a.score > b.score; // 레벨이 같으면 점수 기준으로 내림차순 정렬
}
return a.level < b.level; // 레벨이 다르면 레벨 기준으로 오름차순 정렬
}
int main() {
vector<User> users = {
{"김새우깡", 5, 190},
{"박나나킥", 3, 285},
{"이몽쉘", 5, 195},
{"김콘칩", 3, 280}
};
sort(users.begin(), users.end(), customSort);
for(const User &u : users) {
cout << u.name << " (Lv." << u.level << " " << u.score << "점)\n";
}
// 💻출력: 박나나킥 (Lv.3 285점)
// 김콘칩 (Lv.3 280점)
// 이몽쉘 (Lv.5 195점)
// 김새우깡 (Lv.5 190점)
return 0;
}
참고
<algorithm> 함수
함수에 대해 자세히 알아보기
learn.microsoft.com