Sorting in C++

algorithm c++14 intermediate

The C++ Standard Library provides the std::sort function from the <algorithm> header to sort arrays, vectors, strings and more. sort takes three parameters: the start of a sequence to sort, the end of the same sequence, and the “compare operation” to perform when sorting. By default the compare operation is the less than operator (<) which will sort items in ascending order. Here’s a simple example:

#include <algorithm> // std::sort
#include <vector>
#include <iostream>

int main() {
  std::vector<int> nums{20, 20, 1, 8, 18, 4, 19, 15, 5, 2};

  // Sort a C++ std::vector 
  std::sort(nums.begin(), nums.end());
  for (const int& n : nums) {
    std::cout << n << " ";
  }
  std::cout << "\n";

  // Sort a C array
  int c_array[] = {20, 20, 1, 8, 18, 4, 19, 15, 5, 2};
  std::sort(std::begin(c_array), std::end(c_array));
  for (int n : c_array) {
    std::cout << n << " ";
  }
  std::cout << "\n";
}

1 2 4 5 8 15 18 19 20 20 
1 2 4 5 8 15 18 19 20 20 

We can pass the function std::greater to sort in descending order:

#include <algorithm> // std::sort
#include <functional> // std::greater
#include <vector>
#include <iostream>

void print_vec(const std::vector<int>& v) {
  for (const int& n : v) {
    std::cout << n << " ";
  }
  std::cout << "\n";
}

int main() {
  std::vector<int> nums{20, 20, 1, 8, 18, 4, 19, 15, 5, 2};

  // Sort in descending order
  std::sort(nums.begin(), nums.end(), std::greater<int>());
  print_vec(nums);
}

20 20 19 18 15 8 5 4 2 1 

We can sort subranges by changing the start and end of the sequence to sort:

#include <algorithm> // std::sort
#include <vector>
#include <iostream>

void print_vec(const std::vector<int>& v) {
  for (const int& n : v) {
    std::cout << n << " ";
  }
  std::cout << "\n";
}

int main() {
  std::vector<int> nums{20, 20, 1, 8, 18, 4, 19, 15, 5, 2};

  // Sort the first half in ascending order
  auto midpoint = nums.begin() + (nums.size() / 2);
  std::sort(nums.begin(), midpoint);
  print_vec(nums);
}

1 8 18 20 20 4 19 15 5 2 

Custom Compare

The compare function is a function that accepts two arguments and returns true if the first parameter should be ordered before the second.

#include <algorithm> // std::sort
#include <vector>
#include <iostream>

void print_vec(const std::vector<int>& v) {
  for (const int& n : v) {
    std::cout << n << " ";
  }
  std::cout << "\n";
}

// Returns true if "a" is even
bool evens_before_odds(const int& a, const int& b) {
  return a % 2 == 0;
}

int main() {
  std::vector<int> nums{20, 20, 1, 8, 18, 4, 19, 15, 5, 2};

  std::sort(nums.begin(), nums.end(), evens_before_odds);
  print_vec(nums);
}

2 4 18 8 20 20 1 19 15 5 

The compare function can be a lambda:

#include <algorithm> // std::sort
#include <vector>
#include <iostream>

void print_vec(const std::vector<int>& v) {
  for (const int& n : v) {
    std::cout << n << " ";
  }
  std::cout << "\n";
}

int main() {
  std::vector<int> nums{20, 20, 1, 8, 18, 4, 19, 15, 5, 2};

  std::sort(nums.begin(), nums.end(),
    [](const auto& a, const auto& b) {
      return a % 2 == 0;
    });
  print_vec(nums);
}

2 4 18 8 20 20 1 19 15 5 

Sorting Strings

std::string supports the less than operator < to perfrom lexicographic sorting:

#include <algorithm> // std::sort
#include <vector>
#include <string>
#include <iostream>

int main() {
  std::vector<std::string> names{"Maria",
                                 "Jose",
                                 "Nushi",
                                 "Mohammed"};

  std::sort(names.begin(), names.end());

  for (const auto& n : names) {
    std::cout << n << "\n";
  }
}

Jose
Maria
Mohammed
Nushi

We can use a custom compare function to instead sort by string length:

#include <algorithm> // std::sort
#include <vector>
#include <string>
#include <iostream>

int main() {
  std::vector<std::string> names{"Maria",
                                 "Jose",
                                 "Nushi",
                                 "Mohammed"};

  auto compare_size = [](const auto& a, const auto& b) {
    return a.size() < b.size();
  };

  std::sort(names.begin(), names.end(), compare_size);

  for (const auto& n : names) {
    std::cout << n << "\n";
  }
}

Jose
Maria
Nushi
Mohammed