Использование стандартной сортировки
Для сортировки массивов и векторов в STL есть функции sort и stable_sort (последняя реализует устойчивую сортировку, которая не меняет порядок элементов массива, если они равны).
Для сортировки вектора A алгоритм сортировки нужно вызывать так:
Для сортировки массива A из n элементов функцию сортировки нужно вызывать так:
Но в некоторых случаях необходимо использовать более сложные, настраиваемые функции сортировки, использующие нестандартный порядок. Есть несколько способов задавать настраиваемый порядок сортировки.
Функция-компаратор
Алгоритм сортировки сравнивает элементы при помощи операции «меньше». Можно самостоятельно реализовать операцию «меньше» и использовать её в алгоритме сортировки. Например, давайте упорядочим числа по последней цифре, а если последние цифры равны, то порядок неопределён. В этом случае мы вводим между ними отношение порядка, обозначим его \(\prec\). Например, следующие отношения будут верны, так как последняя цифра левого числа меньше, чем последняя цифра правого числа:
А следующие отношения порядка неверны:
Отношение порядка должно удовлетворять следующим свойствам:
2. Если \(a\prec b\), то \(b\nprec a\).
3. Если \(a \prec b\) и \(b \prec c\), то \(a \prec c\).
Для того, чтобы использовать функцию-компаратор, необходимо объявить функцию, которая получает на вход два сравниваемых значения и возвращает значение типа bool, при этом она возвращает true, если первый аргумент меньше второго аргумента, то есть обязан в упорядоченном массиве идти раньше второго.
Пример реализации такой функции для сортировки значений по последней цифре:
bool cmp(int a, int b)
return a % 10 < b % 10;
>
Эта функция передается в функцию sort третьим параметром:
sort(a.begin(), a.end(), cmp);
Если есть два элемента \(a\) и \(b\), такие, что \(a\nprec b\) и \(b\nprec a\), то с точки зрения сортировки эти элементы «равны». В нашем примере это два числа, оканчивающиеся на одинаковые цифры. Тогда их порядок не определен, если используется функция sort. Если же использовать функцию stable_sort, то эта функция не переставляет равные элементы, то есть сохраняется тот же порядок, который был в массиве до сортировки.
Приведем еще один пример сортировки двух чисел — по возрастанию последней цифры числа, а если последние цифры равны — то по убыванию самих чисел.
Заметим также, что в функцию-компаратор лучше передавать объекты не по значению, а по ссылке, в этом случае они не будут копироваться (что может занимать значительное время при передачи крупных объектов, например, строк, векторов и т.д.). Тогда функцию нужно объявлять так:
Структура pair
В библиотеке STL есть шаблон класса pair .
Класс pair — это два значения, то есть «пара». У объектов этого класса два поля, первое называется first , второе называется second . Например, класс pair можно использовать для хранения точек плоскости (точка — это две координаты) или рациональных дробей (дробь — два числа).
Один экземпляр объектов класса pair определяется так:
Теперь p — это структура с двумя полями, типа int каждое, им можно присваивать значения:
p.first = 1;
p.second = 2;
Можно сразу присвоить значение «паре» целиком, здесь может оказаться полезным функция make_pair , у которой два аргумента, и которая возвращает объект класса pair , поля которого равны двум аргументам. Например:
p = make_pair(1, 2);
Можно создавать массивы и векторы из pair , например:
pair сортируются в лексикографическом порядке, то есть сначала они упорядочиваются по значению поля first , а при равном значении поля first — по значению поля second . Поэтому для решения задачи сортировки, например, чисел по последней цифре можно создать pair , у которой поле first будет равно последней цифре числа, а поле second — самому числу. Рассмотрим два примера реализации считывания и создания такого массива:
int n;
cin >> n;
vector > a(n);
for (int i = 0; i < n; ++i) cin >> a[i].second;
a[i].first = a[i].second % 10;
>
А в следующем примере будем использовать функцию make_pair для создания пары и добавления ее в конец вектора:
int n;
cin >> n;
vector > a;
for (int i = 0; i < n; ++i) int num;
cin >> num;
a.push_back(make_pair(n % 10, n));
>
Элементами пары могут быть объекты разных типов, не только числа.
Другое типичное применение pair в сортировке — сортировка данных с сохранением информации об их порядке. Например, пусть дана последовательность строк, их нужно отсортировать по алфавиту, но нужно для каждой строки запомнить ее номер во входных данных. В этом случае нужно использовать pair , у которой первое поле — строка, а второе поле — число, в котором будет храниться номер:
Структура tuple
Допустим, в одной переменной нужно хранить не два, а большее число полей. Например, информация о человеке может содержать поля имя, фамилия, возраст, и необходимо как-то сортировать эти данные.
Возможные варианты решения:
1. Создание собственной структуры данных с указанием нужных полей. Например,
struct person string lastname;
string firstname;
int age;
>
В этом случае придется объявлять саму структуру, затем реализовывать операцию сравнения, что может занимать достаточно много кода.
2. Использовать pair, один из элементов которого также является pair.
Например, можно объявить переменную так:
pair > person;
person.first = lastname;
person.second.first = firstname;
person.second.second = age;
Это не требует объявления структуры, но достаточно неудобно обращаться к полям структуры через конструкции вида .second.first .
Начиная со стандарта C++11 в STL есть класс tuple (кортеж), который предоставляет возможность создавать аналоги pair из любого количества полей. Например, для представления класса из трех полей типа string , string , int можно объявить класс следующим образом:
Для доступа к полям tuple используется конструкция get следующим образом:
get(p) = lastname;
get(p) = firstname;
get(p) = age;
Параметр, передаваемый функции get в угловых скобках — это номер поля, индексация начинается с нуля. Это значение должно быть константой, то есть определено на момент компиляции программы, нельзя в качестве этого значения использовать переменную.
Например, объявим класс person как tuple из трех полей при помощи typedef (для упрощения последующего использования)
Или можно использовать функцию make_tuple , аналогичную make_pair:
typedef tuple
int n;
cin >> n;
vector p;
for (int i = 0; i < n; ++i) string lastname, firstname;
int age;
cin >> lastname >> firsstname >> age;
p.push_back(make_tuple(lastname, firstname, age));
>
Tuple сортируются также в лексикографическом порядке — сначала по первому полю, при равенстве первого поля — по второму, затем по третьему и т.д.
Std sort c как работает
Функция std::sort() из заголовочного файла предназначена для сортировки диапазон элементов. Первые два параметра функции представляют начальный и конечный итераторы сортируемого диапазона. Третий необязательный параметр представляет функцию сравнения или компаратор. Если компаратор не указан, то элементы сортируются по возрастанию (например, строки сортируются в лексикографическом порядке).
Например, отсортируем вектор строк по умолчанию:
#include #include #include int main() < std::vectorpeople ; std::sort(begin(people), end(people)); // сортируем вектор people for(const auto& person: people ) < std::cout >
В данном случае сортируем весь вектор people, поэтому в функцию std::sort передаются итераторы на начало и конец вектора. И в данном случае мы получим следующий результат:
Alice Bob Kate Sam Tom
То есть строки сортируются в лексикографическом порядке (как идут в алфавите начальные буквы строк). Теперь применим компаратор, например, отсортируем вектор в зависимости от длины строк:
#include #include #include bool compare(const std::string& left, const std::string& right) < return left.length() < right.length(); >int main() < std::vectorpeople ; std::sort(begin(people), end(people), compare); for(const auto& person: people ) < std::cout >
В качестве компаратора здесь определена функция compare. Компаратор должен принимать два значения и возвращать значение типа bool — если первое значение должно идти до второго, то возвращается true . И в случае выше функция compare принимает две строки и возвращает true , если длина первой строки меньше второй. Соответственно теперь консольный вывод будет следующим:
Tom Bob Sam Kate Alice
То есть строки отсортированы по длине по возрастанию.
std::ranges::sort()
Начиная со стандарта C++20 также для сортировки элементов контейнера можно использовать упрощенный подход — функцию std::ranges::sort() , которая в качестве параметра принимает сортируемый контейнер:
#include #include #include #include // для std::ranges int main() < std::vectorpeople ; std::ranges::sort(people); // сортируем вектор people for(const auto& person: people ) < std::cout >
По умолчанию данные сортируются по возрастанию (в случае со строками в лексикографическом порядке)
Alice Bob Kate Sam Tom
Также в качестве второго параметра можно передать функцию компаратора, которая определяет принцип сравнения значений:
#include #include #include #include // для std::ranges bool compare(const std::string& left, const std::string& right) < return left.length() < right.length(); >int main() < std::vectorpeople ; std::ranges::sort(people, compare); // сортируем вектор people с помощью компаратора compare for(const auto& person: people) < std::cout >
С помощью функции-компаратора compare упорядочиваем элементы по возрастанию их длин:
Tom Bob Sam Kate Alice
Сортировка с проекцией
Функция std::ranges::sort поддерживает проекцию данных для функции компаратора. Например:
#include #include #include #include class Person < public: Person(std::string name): name<> std::string getName() const private: std::string name; >; bool compare(const std::string& left, const std::string& right) < return left.length() < right.length(); >std::string personToString(const Person& person) < return person.getName();>int main() < std::vectorpeople , Person, Person, Person>; std::ranges::sort(people, compare, personToString); for(const auto& person: people ) < std::cout >
Здесь сортируемый вектор содержит объекты Person, который хранит имя в строковом поле name. Мы могли бы определить для сравнения данных Person еще одну функцию компаратора. Но в данном случае мы также можем использовать и ранее определенную функцию компаратора для сравнения строк. Но в этом случае в std::ranges::sort() в качестве третьего параметра передается функция проекции из Person в std::string — функция personToString, которая возвращает имя объекта Person. Именно эти данные и будут передаваться в функцию компаратора при сравнении двух объектов.
Отсортировать контейнер по модулю. Как работает sort?
Выполнял задание по отсортировке массива состоящего из целых чисел по модулю. Решение через функцию abs видел. До того как обратиться к интернету, попробовал сам и вышло это:
#include "pch.h" #include #include #include bool modul(int a, int b) < if (a >0 && b > 0) < return (a >b); > else if (a < 0 && b < 0) < if (-1 * a >-1 * b) < return (a >b); > else if (-1 * a < -1 * b) < return (a < b); >> else if (a < 0 && b >0) < if (-1 * a >b) < return (a >b); > else if (-1 * a < b) < return (a < b); >> else if (a > 0 && b < 0) < if (a >-1 * b) < return (a >b); > else if (a < -1 * b) < return (a < b); >> > int main() < int q = 0; std::cin >> q; std::vector modul_sort; for (std::size_t index1 = 0; index1 < q; index1++) < int n = 0; std::cin >> n; modul_sort.push_back(n); > std::sort(modul_sort.begin(), modul_sort.end(), modul); for (const auto& item : modul_sort) < std::cout std::cout
У меня ничего не получилось. Но вот нет понимания, что именно пошло не так. Я наверное просто не понимаю как работает sort или bool функции или ещё что-то. Прошу, подскажите где я напортачил?
Std sort c как работает
atcoder_official → AtCoder Beginner Contest 335 (Sponsored by Mynavi) Announcement
maomao90 → I am top 1 contributor. AMA!
MikeMirzayanov → Codeforces Single Account Policy: zh0ukangyang is Removed from the Rating
maomao90 → Editorial for Hello 2024
DottedCalculator → I am a Specialist. Ask Me Almost Anything!
YaMakhich → я гей
Hexagons → [OFF TOPIC] Hollow Knight radiant tutorial for bossfight "Markoth"
SAD_IN_NIGHTMARE → 2024 OIs
Alfar_ABI → проблема
pajenegod → The Ultimate Reroot Template
CheaterExposer → [UPDATE] Codeforces Cheater IOI Medalist
triumphh → What rating on codeforces should I aim for to crack ZCO and INOI?
stefdasca → Easy and Quick Video Tutorials for the CSES Problem Set
sahal → CSES Problemset Editorials (almost all section editorial collection)
Zlobober → Checkers with testlib.h
oversolver → Expert for the first time since 2011, AMA
Algorithms_with_Shayan → How to approach DP problems & DP playlist
Nurali16 → tourist is not noob . he is genius
AminAnvari → Segment Tree Problems
P etr → A 1:1 week
TurtleZW → Codeforces Round #828 (Div. 3)
flash_7 → Digit DP
tourist → Разбор задач Codeforces Beta Round #17
vrintle → Invitation to Gym Contest — Alpha IV (by AlgoRave)
vrooooom → USACO Bronze/Silver Classes offered for Spring 2024
Блог пользователя alexlampdeveloper
Как работает sort()?
Автор alexlampdeveloper, 9 лет назад ,
Добрый вечер, всем жителям CodeForces!=) Я помню, что когда-то прочитал такую интересную статейку, что sort() в плюсах работает чуть быстрее за n*log(n). И мне теперь стало интересно правда ли это? Если да, то не подскажете по какому алгоритму он работает?
c++, sort, n*log(n), алгоритм
Комментарии (5)
9 лет назад , # |
← Rev. 3 → 
+5 
Стандартом не оговаривается какой именно алгоритм должен быть под капотом std::sort. Однако можно подглядеть как реализован std::sort, например, в gcc.
Там работает QuickSort, который переключается на HeapSort если глубина рекурсии превышает 2 логарифма от количества элементов. Также для количества элементов меньше 16 включается сортировка вставками. Опорный элемент для QuickSort выбирается как медиана из первого, последнего и элемента посередине.
Сложность сей конструкции всё равно N * Log(N)
9 лет назад , # |
← Rev. 3 → +5
Introsort. Сначала quicksort, но если глубина рекурсии слишком большая, переключается на heap sort; таким образом, сложность равна O(n log n) и в среднем, и в худшем случае, но в среднем случае используется самый быстрый алгоритм с этой сложностью. Плюс для пущей скорости на маленьких отрезках делается ни то и ни другое, а insertion sort (но это не влияет на асимптотику).
Как отметили выше, стандарт не оговаривает конкретный алгоритм, но сложность обязательно должна быть O(n log n). Таким образом, простой quicksort недопустим (потому что у него в худшем случае n²), но разрешается не только introsort, но и, например, heap sort, merge sort или ещё что-нибудь более экзотическое. Однако на практике introsort быстрее всего и поэтому используется именно он.
9 лет назад , # ^ |
← Rev. 2 → +14
Полагаю, что доп.память использовать он тоже не может(точнее не должен падать, если памяти не хватает) и поэтому mergesort не пойдет.