сортировка в C++

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

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

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

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

принцип сортировки

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

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

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

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

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

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

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

  • В строках 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 для массива (array)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

  • Egor:

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

    • Дмитрий:

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

  • Boris:

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