정렬과 분할: sort, stable_partition
std::sort와 std::stable_partition으로 컨테이너를 정렬하고 분할합니다.
정렬과 분할: sort, stable_partition은(는) CoddyKit의 무료 C++ Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C++ Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C++ Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
std::sort
대표적인 정렬 알고리즘입니다. 평균 시간 복잡도는 O(N log N)입니다. 제자리에서 동작하며, 안정적인 정렬은 보장되지 않습니다.
#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending사용자 지정 비교 함수
다른 기준으로 정렬하려면 비교 함수(람다 또는 함수 객체)를 전달합니다.
std::sort(v.begin(), v.end(),
[](int a, int b) { return a > b; }); // descending사용자 정의 형식 정렬
특정 멤버를 비교하는 비교 함수를 제공하거나, 해당 형식에 operator<를 정의합니다.
struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) { return a.age < b.age; });std::stable_sort
sort와 같지만, 값이 같은 요소들의 상대적 순서를 유지합니다. 조금 더 느리며(일반적으로 추가 메모리는 O(N log^2 N)입니다),
std::partial_sort
가장 작은 k개의 요소를 정렬된 상태로 앞에 배치합니다. 나머지 요소의 순서는 지정되지 않습니다. 상위 k개만 필요할 때 전체 정렬보다 빠릅니다.
std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sortedstd::nth_element
nth 위치의 요소가 전체 범위를 정렬했을 때의 위치에 오도록 분할합니다. 앞쪽의 모든 요소는 해당 요소보다 작거나 같고(≤), 뒤쪽의 모든 요소는 해당 요소보다 크거나 같습니다(≥). 평균 시간 복잡도는 O(N)입니다.
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest elementstd::is_sorted
범위가 이미 정렬되어 있는지 확인합니다.
if (std::is_sorted(v.begin(), v.end())) {
std::cout << "already sorted";
}std::partition
조건자를 만족하는 요소가 앞에 오도록 범서를 재배치합니다. 조건을 만족하지 않는 첫 요소를 가리키는 반복자를 반환합니다. 안정적이지 않습니다.
std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
// even numbers come first, then oddstd::stable_partition
partition과 같지만, 각 그룹 안에서 요소들의 상대적 순서를 유지합니다.
여러 키로 정렬하기
주 키를 비교하고, 주 키가 같으면 보조 키를 비교하는 비교 함수를 사용합니다.
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
if (a.age != b.age) return a.age < b.age;
return a.name < b.name;
});정렬된 범위에서 이진 검색
정렬한 후 std::lower_bound, std::upper_bound, std::binary_search를 사용하면 O(log N) 시간에 검색할 수 있습니다.
빠른 확인
정렬한 뒤 값이 같은 요소들의 상대적 순서를 유지하는 알고리즘은 무엇입니까?
복습
일반적인 정렬에는 std::sort를 사용하고, 같은 값의 순서가 중요할 때는 std::stable_sort를 사용합니다. 상위 k개를 구할 때는 std::partial_sort, 선택에는 std::nth_element, 그룹화에는 std::partition/std::stable_partition을 사용합니다.
자주 묻는 질문
“정렬과 분할: sort, stable_partition” 강의는 무료인가요?
네 — “정렬과 분할: sort, stable_partition” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C++ Academy 강의 전체를 잠금 해제할 수 있습니다. C++ Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“정렬과 분할: sort, stable_partition”에서 뭘 배우나요?
std::sort와 std::stable_partition으로 컨테이너를 정렬하고 분할합니다. 브라우저에서 직접 실행하는 실습 코드로 C++ Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C++ Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C++ Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“정렬과 분할: sort, stable_partition” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C++ Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C++ Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 비수정 알고리즘: find, count, all_of
- 수정 알고리즘: transform, copy_if, replace
- 정렬과 분할: sort, stable_partition
- 수치 알고리즘: accumulate, reduce, transform_reduce