C++ std::partial_sort Function Template

The std::partial_sort function template in C++ is part of the <algorithm> header and is used to rearrange elements in a range such that the elements before a specified middle position are the smallest elements in the entire range and are sorted in ascending order. The remaining elements are left without any specific order.

std::partial_sort is particularly useful when you need only a subset of the smallest elements sorted, rather than sorting the entire range.

Syntax

</>
Copy
// Default partial sort using operator<
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

// Partial sort using custom comparison function
template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
first, last
Random-access iterators defining the range [first, last) to be partially sorted. The range includes all elements between first and last, excluding the element pointed to by last.
middle
Random-access iterator pointing to the element within the range [first, last) that is used as the upper boundary of the elements that are fully sorted. Elements in the range [first, middle) will be the smallest elements in the entire range and will be sorted in ascending order.
comp
Binary function that accepts two elements in the range as arguments and returns a value convertible to bool. The value returned indicates whether the element passed as the first argument is considered to go before the second in the specific strict weak ordering it defines. The function shall not modify any of its arguments.

Examples

Example 1: Partial Sorting with Default Comparison

This example demonstrates partial sorting of a vector of integers in ascending order using the default comparison. The goal is to sort the first three elements to be the smallest in the entire range.

</>
Copy
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> myvector = {32, 71, 12, 45, 26, 80, 53, 33};

    // Partial sort: first three elements will be the smallest in ascending order
    std::partial_sort(myvector.begin(), myvector.begin() + 3, myvector.end());

    std::cout << "myvector contains:";
    for (const auto& elem : myvector)
        std::cout << ' ' << elem;
    std::cout << std::endl;

    return 0;
}

Output:

myvector contains: 12 26 32 45 71 80 53 33

The first three elements are the smallest in the entire range and are sorted in ascending order. The order of the remaining elements is unspecified.

Explanation:

  1. Initialize the vector: A std::vector named myvector is created and initialized with the integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains unsorted elements to demonstrate the partial sorting process.
  2. Perform partial sorting: The std::partial_sort function is called with three arguments:
    • myvector.begin(): Specifies the start of the range to be considered for sorting.
    • myvector.begin() + 3: Specifies the middle position. The smallest three elements in the range will be sorted and placed at the start of the vector, up to this position.
    • myvector.end(): Specifies the end of the range to consider for sorting.
    The function ensures that the first three elements are the smallest in the entire range and are sorted in ascending order. The rest of the elements in the range remain unsorted.
  3. Print the sorted vector: A range-based for loop iterates over the vector. Each element is printed to the console using std::cout, separated by spaces.

Example 2: Partial Sorting with Custom Comparison Function

This example demonstrates partial sorting of a vector of integers in descending order using a custom comparison function. The goal is to sort the first three elements to be the largest in the entire range.

</>
Copy
#include <iostream>
#include <algorithm>
#include <vector>

// Custom comparison function
bool descending(int i, int j) {
    return i > j;
}

int main() {
    std::vector<int> myvector = {32, 71, 12, 45, 26, 80, 53, 33};

    // Partial sort: first three elements will be the largest in descending order
    std::partial_sort(myvector.begin(), myvector.begin() + 3, myvector.end(), descending);

    std::cout << "myvector contains:";
    for (const auto& elem : myvector)
        std::cout << ' ' << elem;
    std::cout << std::endl;

    return 0;
}

Output:

myvector contains: 80 71 53 45 26 12 32 33

The first three elements are the largest in the entire range and are sorted in descending order. The order of the remaining elements is unspecified.

Explanation:

  1. Define a custom comparison function: The function descending is defined to compare two integers. It:
    • Returns true if the first integer is greater than the second.
    • Ensures that the sorting order is in descending order.
  2. Perform partial sorting: The std::partial_sort function is called with four arguments:
    • myvector.begin(): The starting point of the range to be considered for sorting.
    • myvector.begin() + 3: The middle position. The largest three elements in the range will be sorted in descending order and placed at the start of the vector, up to this position.
    • myvector.end(): The end of the range to consider for sorting.
    • descending: The custom comparison function that defines the sorting order.
    This ensures that the first three elements of the vector are the largest in descending order, while the rest of the elements remain unsorted.

Example 3: Exception Handling in std::partial_sort

This example demonstrates how exceptions can be thrown and handled during the execution of std::partial_sort. If the comparison function throws an exception, the sorting process is interrupted, and the exception can be caught using a try-catch block.

</>
Copy
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdexcept>

// Custom comparison function with intentional exception
bool faultyComparison(int a, int b) {
    if (a == 12 || b == 12) {
        throw std::runtime_error("Comparison failed for value 12.");
    }
    return a < b;
}

int main() {
    std::vector<int> myvector = {32, 71, 12, 45, 26, 80, 53, 33};

    try {
        // Attempt partial sort with faulty comparison function
        std::partial_sort(myvector.begin(), myvector.begin() + 3, myvector.end(), faultyComparison);
    } catch (const std::exception& e) {
        std::cerr << "Exception caught during partial sort: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught during partial sort: Comparison failed for value 12.

Explanation:

  1. Define a custom comparison function: The function faultyComparison is designed to simulate an intentional error during sorting:
    • If either operand is 12, the function throws a std::runtime_error exception with the message "Comparison failed for value 12.".
    • Otherwise, it returns true if the first operand is less than the second, ensuring ascending order for valid comparisons.
  2. Initialize the vector: A std::vector named myvector is created and initialized with integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains the unsorted elements for partial sorting.
  3. Attempt partial sorting: The std::partial_sort function is called within a try block with the following arguments:
    • myvector.begin(): The start of the range to be considered for sorting.
    • myvector.begin() + 3: The middle position, where the smallest three elements should be sorted in ascending order.
    • myvector.end(): The end of the range to consider for sorting.
    • faultyComparison: The custom comparison function that may throw an exception.
    When faultyComparison encounters the value 12, it throws a std::runtime_error, interrupting the sorting process.
  4. Catch and handle the exception: The catch block catches the exception of type std::exception. It:
    • Prints an error message to the console using std::cerr.
    • The message displayed is: "Exception caught during partial sort: Comparison failed for value 12.".

Key Points to Remember about std::partial_sort

  1. The std::partial_sort function arranges the smallest (or largest) elements in the specified range [first, middle) in sorted order.
  2. It leaves the rest of the elements in the range [middle, last) without any specific order.
  3. Custom comparison functions can be used to define alternative sorting criteria, such as descending order.
  4. If a comparison function throws an exception, the sorting process is interrupted, and the exception can be caught and handled appropriately.
  5. It requires random-access iterators, such as those from vectors, arrays, or deques.