C++ Partition Algorithms: partition, stable_partition &

What Does Partition Do?

A partition rearranges a range so that all elements satisfying a predicate come before all elements that don’t:

Before: {1, 2, 3, 4, 5, 6}
Predicate: x % 2 == 0 (is even)

After partition: {2, 4, 6, 1, 3, 5}
                  ─────────  ─────────
                  true group false group
                            ↑
                         partition point

The relative order within each group is not guaranteed by partition. If order matters, use stable_partition.

---

std::partition

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

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

    // Partition into even/odd
    auto pivot = std::partition(v.begin(), v.end(),
        [](int x) { return x % 2 == 0; });

    std::cout << "Evens: ";
    for (auto it = v.begin(); it != pivot; ++it) {
        std::cout << *it << ' ';  // the true group
    }

    std::cout << "\nOdds: ";
    for (auto it = pivot; it != v.end(); ++it) {
        std::cout << *it << ' ';  // the false group
    }
    // Note: order within each group not preserved
}

Return value: iterator to the first element of the false group (the partition point). The range [first, pivot) contains all elements where the predicate returned true; [pivot, last) contains all elements where it returned false.

Practical Uses

// Separate positive from negative numbers
std::vector<int> nums = {-3, 1, -1, 4, -2, 2, 0};
auto pos = std::partition(nums.begin(), nums.end(),
    [](int x) { return x > 0; });
// [pos, end) contains zero and negative numbers

// Move completed tasks to the back
struct Task { bool done; std::string name; };
std::vector<Task> tasks = {
    {true, "write tests"}, {false, "fix bug"}, {true, "deploy"}
};

auto incomplete = std::partition(tasks.begin(), tasks.end(),
    [](const Task& t) { return !t.done; });
// [begin, incomplete) = undone tasks
// [incomplete, end) = done tasks

---

std::stable_partition

stable_partition preserves the original relative order of elements within each group. The cost is O(n log n) time, or O(n) time with O(n) extra memory:

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

struct Employee {
    std::string name;
    std::string department;
    bool active;
};

int main() {
    std::vector<Employee> employees = {
        {"Alice", "Engineering", true},
        {"Bob",   "Marketing",   false},
        {"Carol", "Engineering", true},
        {"Dave",  "HR",          false},
        {"Eve",   "Engineering", true},
    };

    // Separate active/inactive while preserving chronological order
    auto pivot = std::stable_partition(
        employees.begin(), employees.end(),
        [](const Employee& e) { return e.active; }
    );

    std::cout << "Active employees (in original order):\n";
    for (auto it = employees.begin(); it != pivot; ++it) {
        std::cout << "  " << it->name << '\n';
    }
    // Active: Alice, Carol, Eve (original order preserved)

    std::cout << "Inactive employees (in original order):\n";
    for (auto it = pivot; it != employees.end(); ++it) {
        std::cout << "  " << it->name << '\n';
    }
    // Inactive: Bob, Dave (original order preserved)
}

partition vs stable_partition

	partition	stable_partition
Order within groups	Not preserved	Preserved
Time complexity	O(n)	O(n log n) or O(n)†
Extra memory	O(1)	O(n)†
Use when	Order doesn’t matter	Order matters

†With sufficient extra memory, stable_partition achieves O(n) time.

---

std::partition_point

If a range is already partitioned (all true elements before false elements), partition_point finds the boundary in O(log n) using binary search. This requires the predicate to be monotonic over the partitioned range — all trues come before all falses.

#include <algorithm>
#include <vector>

int main() {
    // Pre-sorted and partitioned: all < 6 come first
    std::vector<int> v = {1, 2, 3, 4, 5, 7, 9, 11};

    auto pivot = std::partition_point(v.begin(), v.end(),
        [](int x) { return x < 6; });

    std::cout << "First element >= 6: " << *pivot << '\n';  // 7

    // Elements before pivot satisfy pred
    for (auto it = v.begin(); it != pivot; ++it) {
        std::cout << *it << ' ';  // 1 2 3 4 5
    }
}

partition_point is related to lower_bound: on a sorted range, lower_bound(first, last, value) is equivalent to partition_point(first, last, [&](const T& x){ return x < value; }).

---

std::partition_copy

Copy elements into two separate output ranges based on the predicate, without modifying the source:

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> evens, odds;

    std::partition_copy(
        src.begin(), src.end(),
        std::back_inserter(evens),   // elements where pred is true
        std::back_inserter(odds),    // elements where pred is false
        [](int x) { return x % 2 == 0; }
    );

    // src unchanged
    // evens: {2, 4, 6, 8}
    // odds:  {1, 3, 5, 7}
}

Use partition_copy when:

• You need to keep the source unmodified
• You want the two groups in separate containers

---

std::is_partitioned

Check whether a range is already partitioned:

std::vector<int> v1 = {2, 4, 6, 1, 3, 5};
std::vector<int> v2 = {2, 1, 4, 3, 6, 5};

bool p1 = std::is_partitioned(v1.begin(), v1.end(),
    [](int x) { return x % 2 == 0; });  // true — evens before odds

bool p2 = std::is_partitioned(v2.begin(), v2.end(),
    [](int x) { return x % 2 == 0; });  // false — interleaved

Useful for assertions and precondition checks before calling partition_point.

---

The Quicksort Connection

Quicksort is built on partition: choose a pivot value, then partition the array into elements less than the pivot and elements greater than or equal to the pivot. Recursively sort each half.

// Manual quicksort to illustrate the partition step
void quicksort(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;

    int pivot = v[hi];  // last element as pivot (simplified)

    // Partition: elements < pivot go left, >= pivot go right
    auto it = std::partition(v.begin() + lo, v.begin() + hi,
        [pivot](int x) { return x < pivot; });

    int mid = it - v.begin();
    std::swap(*it, v[hi]);  // place pivot at partition point

    quicksort(v, lo, mid - 1);
    quicksort(v, mid + 1, hi);
}

In practice, std::sort implements introsort — quicksort that falls back to heapsort when recursion depth gets too deep, avoiding O(n²) worst case.

---

Choosing the Right Algorithm

Need to split a range by condition?
├── Source must remain unmodified → partition_copy
├── Relative order matters within groups → stable_partition
├── Speed matters, order doesn't → partition
└── Range is already partitioned, need the boundary → partition_point

Need to check if already partitioned?
└── is_partitioned

---

Key Takeaways

• std::partition rearranges in O(n) — all elements satisfying the predicate come first, returns iterator to the boundary
• std::stable_partition does the same but preserves relative order within each group — O(n log n), O(n) with extra memory
• std::partition_point binary-searches a pre-partitioned range for the boundary in O(log n) — requires monotonic predicate
• std::partition_copy copies elements into two separate outputs without modifying the source
• std::is_partitioned checks whether a range satisfies the partition property — useful for precondition assertions
• Partition is the core step in quicksort — std::sort uses introsort which includes it

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Split ranges with std::partition and stable_partition; find boundaries with partition_point and is_partitioned. Covers s… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ Algorithm Sort | ‘정렬 알고리즘’ 가이드
• C++ Algorithm Set | ‘집합 알고리즘’ 가이드
• C++ Algorithm Reverse | reverse·rotate·reverse_copy 완벽 정리

---

이 글에서 다루는 키워드 (관련 검색어)

C++, Algorithm, partition, STL, sort 등으로 검색하시면 이 글이 도움이 됩니다.