{ }codelper

Learn › C++

Going further · 17

Sorting

Put values in order: smallest first, largest first, or by a rule you choose.

Sorting puts values in order.
The example below sorts numbers smallest first and largest first, then sorts words alphabetically and "shortest first".

#include <algorithm>#include <functional>#include <iostream>#include <sstream>#include <string>#include <vector> template <typename T>void print(const std::vector<T>& v) {    for (size_t i = 0; i < v.size(); i++) std::cout << (i > 0 ? " " : "") << v[i];    std::cout << '\n';} int main() {    std::string line;    std::getline(std::cin, line);    std::istringstream in1(line);    std::vector<int> nums;    for (int x; in1 >> x;) nums.push_back(x);    std::getline(std::cin, line);    std::istringstream in2(line);    std::vector<std::string> words;    for (std::string w; in2 >> w;) words.push_back(w);     std::sort(nums.begin(), nums.end());    print(nums);    std::sort(nums.begin(), nums.end(), std::greater<int>());    print(nums);    std::sort(words.begin(), words.end());    print(words);    std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {        if (a.size() != b.size()) return a.size() < b.size();        return a < b;    });    print(words);}
stdin
10 9 1 25 3
pear fig banana kiwi apple
stdout
1 3 9 10 25
25 10 9 3 1
apple banana fig kiwi pear
fig kiwi pear apple banana

Key points

  • By default, numbers go by size and strings by dictionary order (character-code order).
  • Some sorts return a new list and some change the list in place.
    Python sorted(nums) returns a new list; nums.sort() works in place.
  • There are two ways to give a rule.
    A key function says what to compare for each value (Python key=lambda w: (len(w), w) means "by length, then alphabetically").
  • A compare function takes two values and returns a negative number if the first goes first, 0 if they tie, and a positive number if the second goes first.
  • A stable sort keeps tied values in their original order.
    With a sort that is not stable, write the tie-break (same length → alphabetical) into the compare function too.

How each language writes it

Pythonsorted(nums) (new list), nums.sort() (in place).
Largest first with reverse=True, a rule with key=lambda w: (len(w), w).
Stable
JavaScriptarr.sort((a, b) => a - b) — in place.
Without a compare function even numbers are compared as strings.
Chain rules with a.length - b.length || ....
Stable since ES2019
TypeScriptSame as JavaScript
JavaArrays.sort, Collections.sort.
Largest first with Comparator.reverseOrder(), a rule with Comparator.comparingInt(String::length).thenComparing(...).
Object arrays and Collections.sort are stable.
int[] takes no comparator
C#Array.Sort and List.Sort (in place, not guaranteed stable), LINQ OrderBy(...).ThenBy(...) and OrderByDescending (stable)
C++std::sort(v.begin(), v.end()), largest first with std::greater<int>().
A compare lambda returns a bool: "does the first go first?".
Use std::stable_sort when you need stability
Cqsort(a, n, sizeof a[0], cmp) — cmp takes two pointers and returns negative, 0 or positive.
Not guaranteed stable
Craykonlist.Sort() sorts smallest first.
Pass a compare function's name, as in list.Sort(ShortestFirst).
Stable

Common mistakes

Sorting numbers with plain sort()JavaScript · TypeScript

console.log([10, 9, 1].sort());

→ [ 1, 10, 9 ] — the numbers are compared as strings

Always pass (a, b) => a - b for numbers.

Writing nums = nums.sort()Python

nums = [3, 1, 2]
nums = nums.sort()
print(nums)

→ None — sort works in place and returns nothing

Write just nums.sort(), or nums = sorted(nums).

Passing a comparator for an int[]Java

int[] a = {3, 1, 2};
Arrays.sort(a, Comparator.reverseOrder());

→ Compile error — the int[] version of sort takes no comparator

Convert to Integer[] as the example does, or sort smallest first and read backwards.

How languages differ
Writing a C qsort comparator as return a - b; overflows int when you subtract a large positive from a large negative (e.g.
-2000000000 - 2000000000), flipping the sign and the order.
Compare instead: (a > b) - (a < b).

Practice

  1. Sort the numbers8P0036
  2. Word frequency ranking8P0034
  3. Sorting sign letters8P0253
  4. Number order and dictionary order8P0320
  5. Whose birthday comes next8P0376
  6. Score ranking8P0067
  7. Most meetings in one room8P0090
  8. Union, intersection, difference8P0099