Функция sort и компаратор в C++: что это такое

Привет, дорогие читатели! Этот урок посвящен встроенной сортировке C++ и ее учителю - компаратору.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Что такое функция sort

Это функция, которая может сортировать указанный контейнер или обычный массив. По умолчанию она сортирует по неубыванию, но это можно изменить путем применения компаратора, об этом поговорим позже.

Принцип работы построен на алгоритме быстрой сортировки (quicksort), так что за быстроту можно не волноваться.

Также в C++ имеется другая сортировка - qsort, но она работает значительно медленнее текущей.

Чтобы нам оперировать данной функцией понадобится для начала подключить библиотеку - <algorithm>.

#include <algorithm>

Многие языки не могут похвастаться такой гибкостью. Например, Pascal, там придется самостоятельно писать алгоритм сортировки (который составляет несколько десятков строк !).

Функция sort для вектора

Вот как выглядит конструкция вызова:

sort (<начало>, <конец>, <компаратор>);

• <начало> - здесь мы должны указать стартовую точку сортировки, необязательно это должно быть начало.
• <конец> - тут аналогично, только уже указываем конец.
• <компаратор> - его использовать в аргументах функции не обязательно. Подробнее о нем мы поговорим ниже.

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

using namespace std;

int main () {
  setlocale(0, "");
  int n; vector <int> vec;

  cout << "Введите количество элементов последовательности: "; cin >> n;

  int a;
  for (int i = 0; i < n; i++) {
    cout << i + 1 << ") "; cin >> a;
    vec.push_back(a);
  }

  cout << "Вот как выглядит последовательность до: ";

  for (int i = 0; i < n; i++) {
    cout << vec[i] << " ";
  }

  sort (vec.begin(), vec.end());  // сортировка
  cout << endl << "После сортировки: ";

  for (int i = 0; i < n; i++) {
    cout << vec[i] << " ";
  }

  sort(vec.begin() + n / 2, vec.end(), comp);
  cout << endl << "А вот еще раз: ";

  for (int i = 0; i < n; i++) {
    cout << vec[i] << " ";
  }
  system("pause");
  return 0;
}

• В строках 14 - 17: добавляем элементы в вектор vec.
• В строке 25: сортируем последовательность.
• В строке 32: нашей стартовой точкой стала n / 2, а также мы применили компаратор, из-за которого смогли поменять сторону сортировки (по не возрастанию). vec.begin() + n / 2 - так прибавлять к итератору можно только для вектора и массива, для других контейнеров нельзя. Подробнее почитайте про итераторы здесь.

Вот как выглядит пример запуска программы:

Введите количество элементов последовательности: 10
1) 1
2) 4
3) 2
4) 8
5) 9
6) 5
7) 3
8) 7
9) 10
10) 6

Вот как выглядит последовательность до: 1 4 2 8 9 5 3 7 10 6
А вот как после: 1 2 3 4 5 6 7 8 9 10
А вот еще раз: 1 2 3 4 5 10 9 8 7 6
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Функция sort для списка

Для списка list, функция sort() превращается в префиксный метод:

<имя списка>.sort(<компаратор>);

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Функция sort для массива (array)

Чтобы отсортировать массив нам нужно использовать схему ниже:

sort(<имя массива>, <имя массива> + <размер массива>, компаратор);

Имя массива указывает на первую ячейку -[0].

• В первый аргумент записываем имя массива.
• Далее также записываем имя массива, но уже через плюс указываем сколько ячеек надо отсортировать.

Так, например можно:

• Отсортировать только первую половину массива, если укажем (... , <имя массива> + n / 2) (n - размер массива).
• Или начать сортировку со второй ячейки (<имя массива> + 2, ...).

Что такое компаратор

Компаратор - это функция, которая как бы учит сортировать sort. Так например можно сортировать по:

• Кратности на 3.
• Четности или нечетности.
• Изменить сторону сортировки на - по убыванию.

sort передает элементы компаратору, а компаратор проверяет их по вашему алгоритму и передает true или false.

Обычно его используют когда имеется например - vector < vector <pair <int, int> > > vec и нужно отсортировать вектора по второму элементу первой ячейки (vec[i][0].second).

Как создать компаратор

Самого начала создаём функцию, которая и будет компаратором.

bool comp (<первый элемент>, <второй элемент>) {

  return <первый элемент> <условный оператор> <второй аргумент>;

}

1. <первый и второй аргумент> - здесь нужно быть аккуратным, потому что если мы укажем неправильно аргументы - никакая сортировка не произойдет.
2. return - эта строчка является основной в этом коде, так как именно она изменяет сортировку.

В аргументах нужно всего лишь указать имя компаратора.

sort (vec.begin(), vec.end(), comp);

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Как правильно создавать компаратор чтобы он работал

Чтобы правильно создать компаратор нужно знать это:

1. Когда вызывается компаратор ему передается тип сортируемого объекта.

Давайте разберем пример, который был выше - vector < vector < pair <int, int> > >. Для него этим типом будет - vector < pair <int, int> >.

bool comp (vector < pair <int, int> > a, vector <pair <int, int> > b) {
  return a[0].second < b[0].second;
}

Этот компаратор будет сортировать вектора по второму элементу первой ячейки (по неубыванию).

Для массивов “типом сортируемого объекта” и будет тип массива. Например pair <int, int> p[20] -> ... (pair <int, int> a, ...) {

По неубыванию означает, что элемент arr[i] может быть равным arr[i - 1] (а по убыванию означает что каждый последующий элемент будет меньше предыдущего). Тоже самое с сортировкой по невозрастанию.

Надеемся вы нашли в этой статье то что искали. Если есть вопрос задайте его в комментариях. Удачи!