→ C++

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

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

sort для вектора
sort для списка
sort для массива
Что такое компаратор

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

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

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

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

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

#include <algorithm>

1	#include <algorithm>

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

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

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

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

1	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;
}

#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 — так прибавлять к итератору можно только для вектора и массива, для других контейнеров нельзя. Подробнее почитайте про итераторы здесь.

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

sort_vector.cpp

Введите количество элементов последовательности: 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(<компаратор>);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

}

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

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

}

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

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

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

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

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

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

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

Давайте разберем пример, который был выше — 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;
}

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] (а по убыванию означает что каждый последующий элемент будет меньше предыдущего). Тоже самое с сортировкой по невозрастанию.

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

8 марта 2018

C++, Алгоритмы

Комментарии

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

Добавить комментарий Отменить ответ

Egor:

05.04.2018 в 20:31

Почему не получается передавать в компаратор параметры по ссылке? Что туда вообще нужно передавать, а что не нужно? Как отсортировать двумерный массив при помощи такой функции и почему не рабоает этот код?

Ответить
- Дмитрий:
  
  19.04.2018 в 13:47
  
  Чтобы отсортировать двумерный массив нужно чтобы 2 аргумента компаратора были массивами — int a[], int b[]. А далее сравниваете какие-либо элементы например: return a[0] > b[0]. Читайте подробнее статью.
  
  Ответить
Boris:

17.04.2018 в 15:33

Поэтому если вы хотите отсортировать именно двумерный массив, то либо функцию сортировки вам придется писать самому, либо использовать стандартную C функцию

Ответить
Даниил:

13.03.2019 в 19:59

кстати а можно ли сортом отсортировать определенный вектор в векторе и если да то как

Ответить
- Дмитрий:
  
  28.11.2020 в 21:40
  
  Да, конечно. Главное это обратиться к вектору, который находится в векторе.
  vector > vec;
  // заполнение вектора векторов
  sort(vec[0].begin(), vec[0].end());
  
  Ответить
Антон:

10.04.2020 в 12:15

Может конечно чего не понимаю, только изучаю с++, но мне кажется, что приобъявлении вектора необходимо указывать его тип

У Вас
int n; vector vec;

Должно быть
int n; vector vec;

Ответить
- Антон:
  
  10.04.2020 в 12:16
  
  то есть должно быть
  int n; vector vec;
  
  Ответить
- Дмитрий:
  
  28.11.2020 в 20:56
  
  Спасибо, исправили!
  
  Ответить
Владислав:

30.11.2020 в 12:23

Здравствуйте.

#include
#include

using namespace std;

int main()
{
int a[2],b[2];
cin >> a[0] >> a[1] >> a[2] >> b[0] >> b[1] >> b[2];
sort(a,a+3);
sort(b,b+3);
cout << a[0]*b[0]+a[1]*b[1]+a[2]*b[2];
return 0;
}

В задаче заданы два массива, надо сделать сортировку каждого, а потом соответствующие элементы перемножить, вывести сумму. Но после некоторых исследований я заметил, что когда сортируется массив b, то элементы массива a меняются. Как такое может быть?

Ответить
- Владислав:
  
  30.11.2020 в 12:24
  
  Только там ещё библиотеки и не отправились, написал уже тут.
  
  Ответить
- Дмитрий:
  
  07.12.2020 в 18:50
  
  Здравствуйте, вам нужно присоздании массива изменить его размер, потому что у вас используются три ячейки в каждом. Но при создании создаются только два int a[2], b[2]. Нужно заменить на int a[3], b[3].
  
  Ответить
Денис:

29.12.2020 в 21:42

В разделе «Как создать компаратор»:

bool comp (, ) {

return ;

— здесь нужно быть аккуратным…

Возможно, тут опечатка. В return должно быть «первый аргумент»?

Сайт очень классный, все очень легко и доступно написано, спасибо Вам огромное!
С Наступающим!

Ответить
Антон:

22.09.2021 в 20:15

Тут в статье не сказано, но очень хотелось бы знать.
Как сортировать обычный массив sort-ом кратные 3 или, например, стоящие на четных позициях? Заранее спасибо

Ответить
- Дмитрий:
  
  01.02.2023 в 11:56
  
  Вам нужно создать структуру которая будет хранить значение и индекс, эти поля вы сможете использовать в компараторе.
  struct Elemennt { int value; // значение int index; // index }
  
  Ответить
Вадим:

30.09.2021 в 14:12

Можно ли в компараторе указать сортировку элементов массива по значению, а повторяющиеся ещё и по индексу?

Ответить
- Дмитрий:
  
  01.02.2023 в 11:57
  
  Вам нужно создать структуру которая будет хранить значение и индекс, эти поля вы сможете использовать в компараторе.
  struct Elemennt { int value; // значение int index; // index }
  
  Ответить
Игорь:

21.06.2022 в 12:06

За статью спасибо, однако …

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

Вместо реализации
bool comp (vector <pair> a, vector<pair> b)
{
return a[0].second < b[0].second;
}

следовало бы использовать
bool comp (const vector <pair> & a, const vector<pair> & b)
{
return a[0].second < b[0].second;
}

иначе вы рискуете прождать множественные вызовы конструкторов копирования, а сравнивать будете не те объекты, которые в исходном массиве, а их копии. И не факт, что корректно сравнивать копии вместо объектов — кто знает, как реализованы эти конструкторы.

Ответить

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

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

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

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

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

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

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

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

Поделиться ссылкой:

Добавить комментарий Отменить ответ