Как уже было сказано ранее, в языке C++ имеется встроенная функция sort, которая позволяет нам сортировать массив a[0..n-1] по неубыванию с использованием следующего простого вызова:
sort(a, a+n);
Но этого может быть недостаточно. А что если нам нужно упорядочить только часть массива? Или нужно отсортировать его не по возрастанию, а по убыванию? Или же нам необходимо упорядочить массив, элементы которого несравнимы, например, мы хотим упорядочить массив структур по какому-либо ключу или по какому-либо иному нестандартному критерию. А может обычный целочисленный массив мы хотим отсортировать не по значению элементов а по сумме их цифр... Если вы еще не сталкивались с подобным, то для вас есть хорошая новость: всё это возможно реализовать с использованием все той же функции sort, и разумеется, без какой-либо самостоятельной реализации алгоритма сортировки.
Итак, сначала поймем, что за аргументы у функции sort. Это ничто иное как указатели на элементы массива. Первый аргумент - указатель на стартовый элемент, с которого следует начать сортировку, а второй - это указатель на следующий за последним элементом отрезка сортировки. Если понимать, что само имя массива a - это указатель на значение a[0], а (a+k) - это указатель на значение a[k], то становится ясно, что sort(a, a+n) - это сортировка всего массива, содержащего все элементы с 0-го до (n-1)-го. Если мы пожелаем упорядочить элементы массива a с 3-го по 7-й включительно, то нам следует написать sort(a+3, a+8).
Рассмотрим к ряду также примеры сортировки динамического массива (вектора):
#include <vector>
#include <algorithm>
...
intn=10;
vector<int> a(n);
...
sort(a.begin(), a.end()); //сортировка массива по неубыванию
sort(a.rbegin(), a.rend()); //сортировка массива по невозрастанию
Функция sort может иметь 3 аргумента и в качестве третьего аргумента выступает имя функции-компаратора, которая описывает критерий сравнения элементов сортируемого массива. Данная функция должна иметь два параметра того же типа, что и элементы сортируемого массива, а сама должна возвращать значение логического типа: истину, если первый аргумент должен в результате сортировки иметь меньший индекс, и ложь - в противном случае. Если третий параметр у sort не указан, то используется сравнение по-умолчанию (если элементы массива сравнимы). В большинстве случаев в функцию-компаратор значения сравниваемых элементов следует передавать по ссылке, это может существенно ускорить процесс сортировки, особенно если элементы массива занимают значительный объем памяти.
Приведем пример программы, которая сортирует массив "несравнимых" структур - временных дат. Действительно, структуры в языке C++ несравнимы и без использования функции-компаратора упорядочить массив структур с помощью функции sort не представляется возможным. Реализация сортировки структур может выглядеть следующим образом:
Здесь мы имеем массив d из 9 элементов типа date, каждый из которых представляет собой структуру, в которой 3 поля: день, месяц и год. Для сортировки данного массива использована функция-компаратор cmp(a,b) (имя компаратора может быть произвольным), которая принимает по ссылке два элемента типа date и возвращает истину (true), если дата a меньше даты b (т.е. если элемент a должен иметь меньший индекс, чем b в результате сортировки). Используя данную функцию мы сортируем массив, указав её имя в качестве третьего параметра в sort.