

排序相关 STL

sort

The standard C library implements quick sort, which is qsort in stdlib.h.

But in OI-related competitions, the library sorting function more commonly used is the std::sort from the C++ algorithm library.

The C++ standard does not strictly specify the implementation of this function and it depends on the compiler used.

The old version of the C++ standard only requires its average time complexity to reach $O(n\log n)$ , but the C++11 standard requires its worst time complexity to reach $O( n\log n)$ . You can refer to std::sort().

在 libstdc++ 和 libc++ 中使用的都是 Introsort 。

In both libstdc++ and libc++, introsort is used.

Introsort limits the divide and conquer depth of quicksort. When divide and conquer reaches a certain depth, use a sorting algorithm (such as heap sort) with the worst time complexity of $O(n\log n)$ to sort the sub-arrays.

This limitation of Introsort makes its worst time complexity $O(n\log n)$ .

Usage:

// a[0] .. a[n - 1]: array needs to be sorted
std::sort(a, a + n);
// The above code directly modifies the order of elements in the array so that it is now sorted ascendingly.

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

nth_element

The function is to find with the $k$-th largest number in the selected interval, put all the elements smaller and larger than it on both sides respectively, and return its address.

The principle is the unfinished quick sort.

Usage:

std::nth_element(begin, mid, end);
std::nth_element(begin, mid, end, cmp);

Time complexity: Expected value of $O(n)$.

Often used to build K-D Tree.

stable_sort

Stable $O(n\log n)$ sort means that the relative positions of equal elements after the sorting are the same as the original sequence.

Usage:

std::stable_sort(begin, end);
std::stable_sort(begin, end, cmp);

partial_sort

Place the top $k$ smallest elements in the first $k$ positions in the sequence (the order of equal elements is not guarnteed), and the order of the remaining elements is not specified.

Time complexity: $O(n\log k)$

Usage:

std::partial_sort(begin, begin + k, end);
std::partial_sort(begin, begin + k, end, cmp);

Principle:

The principle of implementing partial_sort is to perform the make_heap() operation on the elements in the interval $[first, middle)$ in the original sequence to construct a max heap, and then take each element in $[middle, last)$ to compare with the $first$ — the maximum value in the heap. If it is less than the maximum value, the two elements are swapped, and the elements in $[first, middle)$ are adjusted to maintain the max heap. After the comparison, the elements in $[first, middle)$ are sorted by sort_heap() in ascending order. Please note that heap order is different ascending order.

Define operator

For both built-in types (such as int) and user-defined structures, you can define the less than operator when calling the STL sorting function. You can pass a comparison operator function (usually the last parameter) when calling the function, or directly override the default operator of this type. See cppreference.

Here are a few examples:

int a[1009], n = 10;
// ......
std::sort(a + 1, a + 1 + n);                  // sort ascendingly
std::sort(a + 1, a + 1 + n, greater<int>());  // sort descendingly

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 to sort ascendingly
std::sort(da + 1, da + 1 + 10, cmp);  // use cmp function to compare, sort descendingly

Strictly weak order

The sorting operator must satisfy the strict weak ordering, otherwise there will be unpredictable situations (such as runtime error, can not be sorted correctly, etc).

The requirements of the strict weak order:

1. $x \not< x$ (non-reflexive)
2. If $x < y$ , then $y \not< x$ (asymmetry)
3. If $x < y, y < z$ , then $x < z$ (transitivity)
4. If $x \not< y, y \not< x, y \not< z, z \not< y$ , then $x \not< z, z \not< x$ (incomparable transitivity)

Common mistakes:

• Use <= to define the less-than operator in sorting.
• When calling the sorting operator, reading the external value may change the array. (commonly seen in the shortest path algorithm)
• The result of comparing the maximum and minimum values of multiple numbers is used as a sorting operator. (For example, the classic error in queens game/processing production scheduling, you may refer to the article Talking about the application of neighbor exchange sorting and problems that need attention (Original link in Chinese).

---

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

评论