Skip to content

Sorting-related STL

This page briefly introduces the sorting algorithms implemented in the C and C++ standard libraries.

Unless otherwise specified, all functions listed on this page are defined in the header <algorithm> by default.

qsort

See: qsort, std::qsort

This function is the Quick Sort implemented in the C standard library, defined in <stdlib.h>. In the C++ standard library, this function is defined in <cstdlib>.

Comparison Function for qsort and bsearch

The qsort function has four parameters: array name, number of elements, element size, and comparison rule. The comparison rule is implemented by specifying a comparison function, and different sorting rules can be achieved by specifying different comparison functions.

The parameters of the comparison function are limited to two const void pointers. The return value is defined as positive, negative, and zero.

An example of a comparison function is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int compare(const void *p1, const void *p2)  // Comparison function for int array
{
  int *a = (int *)p1;
  int *b = (int *)p2;
  if (*a > *b)
    return 1;  // Returning a positive number means a > b
  else if (*a < *b)
    return -1;  // Returning a negative number means a < b
  else
    return 0;  // Returning 0 means a is equivalent to b
}

Note: Using the subtraction of two elements as the return value instead of positive/negative numbers is a typical error, as it may cause overflow errors.

Here is an example of sorting a structure:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
struct eg  // Example structure
{
  int e;
  int g;
};

int compare(const void *p1,
            const void *p2)  // Comparison function for struct eg array: sort by member e
{
  struct eg *a = (struct eg *)p1;
  struct eg *b = (struct eg *)p2;
  if (a->e > b->e)
    return 1;  // Returning a positive number means a > b
  else if (a->e < b->e)
    return -1;  // Returning a negative number means a < b
  else
    return 0;  // Returning 0 means a is equivalent to b
}

It can also be seen here that equivalence does not mean equality, but only that the two elements are equivalent under this comparison rule.

std::sort

See: std::sort

Usage:

1
2
3
4
5
6
// a[0] .. a[n - 1] is the sequence to be sorted
// Sorts a in-place in ascending order
std::sort(a, a + n);

// cmp is a custom comparison function
std::sort(a, a + n, cmp);

Note: The return value of the comparison function for sort is true and false, using true and false to indicate the size (order) relationship between two elements. This is completely different from the semantics of the three-valued comparison function of qsort. For details, refer to the sort documentation above.

If you want to simply rewrite sort to qsort while keeping the overall sorting order unchanged (ignoring equivalent elements), you need to change true to -1 and false to 1.

The std::sort function is the more commonly used C++ library comparison function. The last parameter of this function is a binary comparison function. When the cmp function is not specified, it sorts in ascending order by default.

Older C++ standards only required its average time complexity to reach \(O(n\log n)\). The C++11 standard and subsequent standards require its worst-case time complexity to reach \(O(n\log n)\).

The C++ standard does not strictly require the implementation algorithm of this function; the specific implementation depends on the compiler. Both libstdc++ and libc++ use Introsort.

std::nth_element

See: std::nth_element

Usage:

1
2
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, cmp);

It rearranges the elements in [first, last) such that the element pointed to by nth is changed to the element that would appear at that position if [first, last) were sorted. All elements before the new nth element are less than or equal to all elements after the new nth element.

The implementation algorithm is an incomplete introsort.

For both usages above, the C++ standard requires its average time complexity to be \(O(n)\), where n is std::distance(first, last).

It is often used to build K-D Tree.

std::stable_sort

See: std::stable_sort

Usage:

1
2
std::stable_sort(first, last);
std::stable_sort(first, last, cmp);

Stable sort, ensuring that the relative positions of equal elements after sorting are the same as in the original sequence.

Time complexity is \(O(n\log^2 n)\), and when additional memory is available, the complexity is \(O(n\log n)\).

std::partial_sort

See: std::partial_sort

Usage:

1
2
3
// mid = first + k
std::partial_sort(first, mid, last);
std::partial_sort(first, mid, last, cmp);

Sorts the first k elements in the sequence in-place according to the order given by cmp, with no guarantee on the order of the remaining elements. When the cmp function is not specified, it sorts in ascending order by default.

Complexity: Approximately \((\mathit{last}-\mathit{first})\log(\mathit{mid}-\mathit{first})\) applications of cmp.

Principle:

The idea of std::partial_sort is: perform make_heap() on the elements in the original container in the range [first, mid) to construct a max-heap, then compare each element in [mid, last) with first, ensuring that the elements in first are the maximum in the heap. If an element is less than this maximum, swap the element positions and adjust the elements in [first, mid) to maintain the max-heap property. After the comparisons, perform a heap sort sort_heap() on the elements in [first, mid) to arrange them in ascending order. Note that heap order and ascending order are different.

Custom Comparison

See: Operator Overloading

Built-in types (such as int) and user-defined structures allow customization of the comparison function used when calling STL sorting functions. You can pass a binary comparison function as the last parameter when calling the function.

For user-defined structures, at least one relational operator must be defined before using STL sorting functions, or a binary comparison function must be provided when using the function. It is usually recommended to define operator<.1

Example:

1
2
3
4
int a[1009], n = 10;
// ...
std::sort(a + 1, a + 1 + n);                  // Sort in ascending order
std::sort(a + 1, a + 1 + n, greater<int>());  // Sort in descending order


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
struct data {
  int a, b;

  bool operator<(const data rhs) const {
    return (a == rhs.a) ? (b < rhs.b) : (a < rhs.a);
  }
} da[1009];

bool cmp(const data u1, const data u2) {
  return (u1.a == u2.a) ? (u1.b > u2.b) : (u1.a > u2.a);
}

// ...
std::sort(da + 1, da + 1 + 10);  // Use the < operator defined in the structure, sort in ascending order
std::sort(da + 1, da + 1 + 10, cmp);  // Use the cmp function for comparison, sort in descending order

Strict Weak Ordering

Also see: Application in C++ - Order Theory

The operator used for sorting must satisfy Strict Weak Ordering, otherwise unpredictable situations may occur (such as runtime errors, incorrect sorting).

Common mistakes:

  • Using <= to define the less-than operator in sorting.
  • Reading external arrays whose values may change when calling the sorting operator (common in shortest path algorithms).
  • Using the result of comparing the maximum/minimum values of multiple numbers as the sorting operator (such as the classic error in the Queen's Game/Production Scheduling problem).

References and Notes

  1. Because most standard algorithms use operator< for comparison by default. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用