C++ std::sort

The std::sort function template in C++ is part of the <algorithm> header and is used to sort elements in a range. It arranges the elements in ascending order by default, using the < operator. The function allows custom comparison functions or function objects to define alternative sorting criteria.

Syntax

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

// Sort using custom comparison function
template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
first, last
Random-access iterators defining the range [first, last) to be sorted.
comp
Binary function that accepts two elements in the range as arguments and returns a boolean. The function should return true if the first element is considered to go before the second.

Examples

Example 1: Sorting with Default Comparison

In this example, you will learn sorting a vector of integers in ascending order using std::sort function with the default comparison.

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

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

    // Sort entire vector in ascending order
    std::sort(myvector.begin(), myvector.end());

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

    return 0;
}

Output:

sorted myvector: 12 26 32 33 45 53 71 80

Explanation

  1. Initialize the vector: A std::vector named myvector is created and initialized with a list of integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains the unsorted elements to be sorted.
  2. Sort the vector: The std::sort function is called with the range myvector.begin() to myvector.end(). This sorts the entire vector in ascending order using the default comparison operator (<).
  3. Print the sorted vector: A for loop iterates over the sorted vector using a range-based loop. The elements are printed to the console with a space separator using std::cout.

Example 2: Sorting with Custom Comparison Function

In this example, you will learn sorting a vector of integers in descending order using a custom comparison function.

</>
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};

    // Sort entire vector in descending order
    std::sort(myvector.begin(), myvector.end(), descending);

    std::cout << "myvector sorted descending:";
    for (const auto& elem : myvector)
        std::cout << ' ' << elem;

    return 0;
}

Output:

myvector sorted descending: 80 71 53 45 33 32 26 12

Explanation:

  1. Define a custom comparison function: A custom function named descending is defined. This function takes two integers as arguments and returns true if the first integer is greater than the second. This ensures the sorting order will be descending.
  2. Initialize the vector: A std::vector named myvector is created and initialized with a list of integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains the unsorted elements to be sorted.
  3. Sort the vector in descending order: The std::sort function is called with three arguments: myvector.begin(), myvector.end(), and the custom comparison function descending. This sorts the elements of the vector in descending order.
  4. Print the sorted vector: A for loop iterates over the sorted vector using a range-based loop. The elements are printed to the console with a space separator using std::cout.

Example 3: Sorting with Lambda Expression

This example demonstrates sorting a vector of integers in descending order using a lambda expression as the comparison function.

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

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

    // Sort entire vector in descending order using a lambda expression
    std::sort(myvector.begin(), myvector.end(), [](int i, int j) { return i > j; });

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

    return 0;
}

Output:

myvector sorted: 80 71 53 45 33 32 26 12

Explanation:

  1. Initialize the vector: A std::vector named myvector is created and initialized with a list of integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains the unsorted elements to be sorted.
  2. Sort the vector in descending order: The std::sort function is called with three arguments:
    • myvector.begin(): Specifies the start of the range to sort.
    • myvector.end(): Specifies the end of the range to sort.
    • A lambda expression: Defines a custom comparison function [] (int i, int j) { return i > j; } to sort the elements in descending order.
    The lambda expression compares two integers and returns true if the first integer is greater than the second, ensuring a descending order sort.
  3. Print the sorted vector: A range-based for loop iterates over the sorted vector. Each element is printed to the console with a space separator using std::cout.

Example 4: Exception Handling in std::sort

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

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

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 to sort using a faulty comparison function
        std::sort(myvector.begin(), myvector.end(), faultyComparison);
    } catch (const std::exception& e) {
        std::cerr << "Exception caught during sort: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught during sort: Comparison failed for value 12.

Explanation:

  1. Define a faulty comparison function: A custom comparison function faultyComparison is defined, which:
    • Throws a std::runtime_error exception if either operand is equal to 12.
    • Returns true if the first operand is less than the second, for valid comparisons.
    This function is intentionally designed to simulate an error during sorting.
  2. Initialize the vector: A std::vector named myvector is created and initialized with a list of integers: {32, 71, 12, 45, 26, 80, 53, 33}. This vector contains the unsorted elements.
  3. Attempt to sort the vector: Inside a try block, the std::sort function is called with three arguments:
    • myvector.begin(): Specifies the start of the range to sort.
    • myvector.end(): Specifies the end of the range to sort.
    • faultyComparison: Specifies the custom comparison function.
    When the comparison function encounters the value 12, it throws a std::runtime_error, terminating the sorting process.
  4. Catch the exception: The catch block catches the exception of type std::exception. It prints the error message "Comparison failed for value 12." to the standard error stream using std::cerr.

Key Points to Remember about std::sort

  1. The std::sort function sorts elements in ascending order by default using the < operator.
  2. Custom comparison functions or lambdas can be used to define alternative sorting criteria.
  3. It requires random-access iterators, such as those from vectors, arrays, or deques.
  4. If an exception is thrown by the comparison function, the sorting process is aborted, and the exception can be caught and handled.
  5. std::sort has a time complexity of approximately O(N log N) for average cases.
  6. It does not guarantee stability, meaning equal elements might not retain their original order after sorting.