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
// 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.
#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
-
Initialize the vector:
A
std::vector
namedmyvector
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. -
Sort the vector:
The
std::sort
function is called with the rangemyvector.begin()
tomyvector.end()
. This sorts the entire vector in ascending order using the default comparison operator (<
). -
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 usingstd::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.
#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:
-
Define a custom comparison function:
A custom function named
descending
is defined. This function takes two integers as arguments and returnstrue
if the first integer is greater than the second. This ensures the sorting order will be descending. -
Initialize the vector:
A
std::vector
namedmyvector
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. -
Sort the vector in descending order:
The
std::sort
function is called with three arguments:myvector.begin()
,myvector.end()
, and the custom comparison functiondescending
. This sorts the elements of the vector in descending order. -
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 usingstd::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.
#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:
-
Initialize the vector:
A
std::vector
namedmyvector
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. -
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.
true
if the first integer is greater than the second, ensuring a descending order sort. -
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 usingstd::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.
#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:
-
Define a faulty comparison function:
A custom comparison function
faultyComparison
is defined, which:- Throws a
std::runtime_error
exception if either operand is equal to12
. - Returns
true
if the first operand is less than the second, for valid comparisons.
- Throws a
-
Initialize the vector:
A
std::vector
namedmyvector
is created and initialized with a list of integers:{32, 71, 12, 45, 26, 80, 53, 33}
. This vector contains the unsorted elements. -
Attempt to sort the vector:
Inside a
try
block, thestd::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.
12
, it throws astd::runtime_error
, terminating the sorting process. -
Catch the exception:
The
catch
block catches the exception of typestd::exception
. It prints the error message"Comparison failed for value 12."
to the standard error stream usingstd::cerr
.
Key Points to Remember about std::sort
- The
std::sort
function sorts elements in ascending order by default using the<
operator. - Custom comparison functions or lambdas can be used to define alternative sorting criteria.
- It requires random-access iterators, such as those from vectors, arrays, or deques.
- If an exception is thrown by the comparison function, the sorting process is aborted, and the exception can be caught and handled.
std::sort
has a time complexity of approximatelyO(N log N)
for average cases.- It does not guarantee stability, meaning equal elements might not retain their original order after sorting.