Sorting-Related STL

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

Except for the functions explicitly mentioned, the functions listed on this page are by default defined in the <algorithm> header file.

qsort

See: qsort, std::qsort

This function is an implementation of quicksort 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: the array name, the number of elements, the size of an element, and the comparison rule. The comparison rule is implemented by specifying a comparison function; different comparison functions can implement different sorting rules.

The comparison function takes two pointers of type const void as parameters. Its return value is specified to be a positive number, a negative number, or 0.

One example of a comparison function is:

int compare(const void *p1, const void *p2)  // Comparison function for an array of type int
{
  int *a = (int *)p1;
  int *b = (int *)p2;
  if (*a > *b)
    return 1;  // Returning a positive number means that a is greater than b
  else if (*a < *b)
    return -1;  // Returning a negative number means that a is less than b
  else
    return 0;  // Returning 0 means that a and b are equivalent
}

Note: replacing the positive/negative return value with the subtraction of two elements is a typical erroneous implementation, because it may cause an overflow error.

Here is an example of sorting a structure:

struct eg  // Example structure
{
  int e;
  int g;
};

int compare(const void *p1,
            const void *p2)  // Comparison function for an array of type struct eg: 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 that a is greater than b
  else if (a->e < b->e)
    return -1;  // Returning a negative number means that a is less than b
  else
    return 0;  // Returning 0 means that a and b are equivalent
}

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

std::sort

See: std::sort

Usage:

// a[0] .. a[n - 1] are the sequence of numbers to sort
// Sort a in place, arranging it 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 sort's comparison function is true or false, and true and false represent the ordering relationship between two elements. This is entirely different from the semantics of qsort's three-way comparison function. See the sort documentation given above for details.

If sort is to be simply rewritten as qsort while keeping the overall sorting order unchanged (without considering equivalent elements), return true needs to be changed to - 1, and return 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 required only that its average time complexity 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 a particular algorithm for this function's implementation; the specific implementation depends on the compiler. The implementations in libstdc++ and libc++ both use introsort.

std::nth_element

See: std::nth_element

Usage:

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

It rearranges the elements in [first, last) so that the element pointed to by nth is changed to the element that would appear at that position after [first, last) was sorted. Every element before this new nth element is less than or equal to every element after the new nth element.

The implementation algorithm is incomplete introsort.

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

It is commonly used to build a K-D Tree.

std::stable_sort

See: std::stable_sort

Usage:

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

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

The 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:

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

It sorts the first k elements in the sequence in place according to the order specified by cmp; the order of the subsequent elements is not guaranteed. 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 to execute make_heap() on the elements in the interval [first, mid) of the original container, constructing a max-heap. Then compare each element in [mid, last) with first, ensuring that the element in first is the maximum in the heap. If it is smaller than that maximum, swap the elements and adjust the elements in [first, mid) to maintain the max-heap order. After all comparisons, perform a heapsort operation 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 customizing the comparison function used when calling STL sorting functions. When calling the function, a function implementing a binary comparison can be passed as the last parameter.

For a user-defined structure, at least one relational operator must be defined before using an STL sorting function on it, or a binary comparison function must be supplied when using the function. It is generally recommended to define operator<.¹

Example:

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

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 for comparison, in ascending order
std::sort(da + 1, da + 1 + 10, cmp);  // Use the cmp function for comparison, in descending order

Strict weak ordering

See also: Applications in C++ - Order theory

The operator used for sorting must satisfy strict weak ordering; otherwise, unpredictable situations may occur (such as runtime errors or failure to sort correctly).

Common erroneous approaches:

• Using <= to define the less-than operator in sorting.
• Reading an array whose external values may change when calling the sorting operator (common in shortest-path algorithms).
• Using the result of comparing the maximum and minimum of multiple numbers as the sorting operator (such as the classic error in the Queen Game / job-shop scheduling).

External links

• A discussion of applications of adjacent-element-swap sorting and points to note

References and notes

Footnotes

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