🎓 A1Learner
🔍
0 of 34 lessons completed

C++ Sorting

Sorting is putting the values in a collection in order. The algorithm library provides a ready-made sort that orders any vector.

Checking order by hand

This program finds the largest value with a hand-written loop. It also checks by hand whether the values already sit in order.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> values = {42, 18, 73, 29};
  int largest = values[0];
  for (int value : values) {
    if (value > largest) {
      largest = value;
    }
  }
  bool ordered = true;
  for (int i = 1; i < 4; i++) {
    if (values[i] < values[i - 1]) {
      ordered = false;
    }
  }
  std::cout << std::boolalpha;
  std::cout << "Largest: " << largest << "\n";
  std::cout << "Ordered: " << ordered << "\n";
  return 0;
}

Sorting from smallest to largest

std::sort orders the whole vector in one call. The loop then prints the values in their new order.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> values = {42, 18, 73, 29};
  std::sort(values.begin(), values.end());
  for (int value : values) {
    std::cout << value << "\n";
  }
  return 0;
}

Sorting from largest to smallest

std::greater<int>() is passed as the comparison. The same values now print in reverse order.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main() {
  std::vector<int> values = {42, 18, 73, 29};
  std::sort(values.begin(), values.end(), std::greater<int>());
  for (int value : values) {
    std::cout << value << "\n";
  }
  return 0;
}

Sorting structs by a field

A named function compares two players by score. std::sort uses it to order the players from the highest score to the lowest.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

struct Player {
  std::string name;
  int score;
};

bool byScore(const Player& a, const Player& b) {
  return a.score > b.score;
}

int main() {
  std::vector<Player> players = {{"Ana", 72}, {"Bo", 91}, {"Cleo", 85}};
  std::sort(players.begin(), players.end(), byScore);
  for (const Player& player : players) {
    std::cout << player.name << " " << player.score << "\n";
  }
  return 0;
}

Example

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> scores = {58, 91, 73, 84, 66};
  std::sort(scores.begin(), scores.end());
  std::cout << scores[4] << "\n";
  std::cout << scores[3] << "\n";
  std::cout << scores[2] << "\n";
  return 0;
}

Key points

  • The #include <algorithm> line brings in std::sort.
  • std::sort takes the begin and end positions of the part to order.
  • With no extra argument, std::sort orders values from smallest to largest.
  • std::greater<int>() is a ready-made comparison object that reverses the order.
  • A named comparison function can order structs by one field.
  • The comparison function returns true when the first value belongs before the second.

In this example, std::sort orders the five scores from smallest to largest. The last three positions hold the three highest scores. The prints read those positions from the end, so the top three scores print from highest to lowest.

Note

Sorting changes the order of the values inside the vector itself.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

What does std::sort do to a vector when no comparison is passed?