When we think about sorting algorithms, we think about algorithms that put elements of a list (either an array or linked list) into some order (usually numerically or lexicographically).
In terms of time complexity, consider this chart:
List
Language-specific
In C++, the standard library (in <algorithm>
) provides an sorting algorithm with std::sort()
. We can pass in either two iterators, or the structure itself. Note that pairs, tuples, are primarily sorted by the first element, then by successive elements. For user-defined structs, we need to overload with an operator>
function, custom function, or lambda.
Mainly, the best way is to use a comparison function.
std::stable_sort()
takes the same parameters, but sorts while preserving the relative order of the elements.