Partition Algorithms

Partition vs Stable Partition Performance

How does the partition() algorithm differ from the stable_partition() algorithm in terms of performance?

Abstract art representing computer programming

The partition() and stable_partition() algorithms in C++ are used to divide a collection into two parts based on a predicate, but they differ significantly in terms of performance.

partition()

The partition() algorithm is designed for speed and efficiency. It rearranges elements within the collection based on the predicate without caring about the order of elements within each partition.

This lack of order preservation means partition() can often be implemented with fewer swaps and less overhead, making it faster and more efficient in terms of time complexity.

It typically operates in O(n)O(n) time, where n is the number of elements in the collection.

stable_partition()

On the other hand, stable_partition() preserves the relative order of elements within each partition. This means that if two elements are equal according to the predicate, their order in the original collection is maintained in the resulting partitions.

While this stability is useful in many scenarios, it comes at a performance cost. To maintain this order, stable_partition() generally requires additional temporary storage and more complex operations, resulting in higher time and space complexity compared to partition().

It often operates in O(nlogn)O(n log n) time due to the need for additional operations to maintain order. Here’s a comparison in code:

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

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

  // Using partition()
  std::ranges::partition(A, [](int x) {
    return x < 0; });

  std::cout << "After partition: ";
  for (int x : A) std::cout << x << ", ";

  // Using stable_partition()
  std::ranges::stable_partition(A, [](int x) {
    return x < 0; });

  std::cout << "\nAfter stable_partition: ";
  for (int x : A) std::cout << x << ", ";
}
After partition: -6, 2, 7, 1, 5, 4,
After stable_partition: -6, 1, 7, 2, 5, 4,

In this example, partition() is faster but may not maintain the order of elements. stable_partition() maintains the order but at a higher computational cost.

Choose between them based on whether maintaining the order of elements is crucial for your application.

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved