Using sort() in the C++ Standard Library
Introduction
Sorting is a fundamental operation in programming that involves arranging items in a specific order. These items can belong to a sequence, array, or any other data structure. In C++, the Standard Library provides the built-in std::sort() function, which simplifies sorting operations with remarkable efficiency.
This updated tutorial dives into the usage, variations, and nuances of the std::sort() function in C++. Let’s begin!
What is std::sort()?
The std::sort() function is a powerful utility in the C++ Standard Library, defined in the <algorithm> header. It allows you to sort data structures like arrays and vectors in ascending or descending order and even lets you define custom sorting criteria.
Syntax
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
first: Iterator pointing to the first element of the range to be sorted.last: Iterator pointing to one past the last element of the range.comp(optional): A comparison function or callable object that defines the sorting order. If omitted, the elements are sorted in ascending order usingstd::less<>().
Key Details:
- By default,
std::sort()uses Introsort, a hybrid algorithm combining Quick Sort, Heap Sort, and Insertion Sort. - Its time complexity is
O(Nlog(N))in the average and worst cases.
Sorting data using the sort() Function in C++
1. Sorting in Ascending Order
By default, std::sort() arranges elements in ascending order when the comp parameter is not provided.
Example:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int demo[5] = {5, 4, 3, 2, 1};
int len = sizeof(demo) / sizeof(demo[0]);
cout << “Before sorting: “;
for (int i = 0; i < len; i++) cout << demo[i] << ” “;
std::sort(demo, demo + len); // Default ascending sort
cout << “\nAfter sorting: “;
for (int i = 0; i < len; i++) cout << demo[i] << ” “;
return 0;
}
Output:
Before sorting: 5 4 3 2 1
After sorting: 1 2 3 4 5
2. Sorting in Descending Order
To sort in descending order, provide a comparator like std::greater<int>() as the third argument.
Example:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int demo[5] = {44, 22, 55, 33, 66};
int len = sizeof(demo) / sizeof(demo[0]);
cout << “Before sorting: “;
for (int i = 0; i < len; i++) cout << demo[i] << ” “;
std::sort(demo, demo + len, greater<int>()); // Descending sort
cout << “\nAfter sorting: “;
for (int i = 0; i < len; i++) cout << demo[i] << ” “;
return 0;
}
Output:
Before sorting: 44 22 55 33 66
After sorting: 66 55 44 33 22
Alternatively, you can use a lambda function for custom descending sorting:
Example with Lambda:
std::sort(demo, demo + len, [](int a, int b) { return a > b; });
3. Sorting with User-Defined Order
The comp parameter allows you to define custom sorting logic. For instance, you can sort elements based on their remainder when divided by 10.
Example:
#include <iostream>
#include <algorithm>
using namespace std;
bool customSort(int a, int b) {
return (a % 10) < (b % 10);
}
int main() {
int demo[5] = {18, 45, 34, 92, 21};
int len = sizeof(demo) / sizeof(demo[0]);
cout << “Before sorting: “;
for (int i = 0; i < len; i++) cout << demo[i] << ” “;
std::sort(demo, demo + len, customSort); // Sort based on remainder when divided by 10
cout << “\nAfter sorting: “;
for (int i = 0; i < len; i++) cout << demo[i] << ” “;
return 0;
}
Output:
Before sorting: 18 45 34 92 21
After sorting: 21 92 34 45 18
Complexity of std::sort()
The complexity of std::sort() is O(Nlog(N)) in the worst and average cases, making it highly efficient for large datasets.
Best Practices and Tips
- Use Appropriate Iterators: Ensure the iterators passed to
std::sort()are random-access iterators (e.g., for arrays or vectors). - Prefer Inline Lambda Functions for Simplicity: Inline lambda functions are often cleaner and more concise for custom sorting.
- Optimize for Readability: Use meaningful names for custom comparator functions or lambdas to clarify their purpose.
- Sort Non-Array Containers: The
std::sort()function also works with other containers likestd::vectorandstd::deque.
Example: Sorting a std::vector:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {3, 1, 4, 1, 5};
std::sort(vec.begin(), vec.end()); // Ascending sort
cout << “Sorted vector: “;
for (int v : vec) cout << v << ” “;
return 0;
}
