Сортировки

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

Задачи на сортировку можно разделить на две группы: сортировки компараторами (сравнениями) и типизированные сортировки.
Сортировки компараторами используются в тех случаях, когда мы можем сравнить любую пару объектов и узнать какой из них больше. Это наиболее общий тип сортировок. Такие сортировки строятся на основе некоторой функции (компаратора), которая может сравнить два объекта сортируемого типа и возвращает true если первый аргумент меньше второго или false если наоборот. Алгоритм сравнения может быть таким, как Вам нужно для конкретной задачи. Сортировка компараторами имеет эффективную реализацию sort() в составе стандартной библиотеки (подключается через ). Асимптотически вычислительная сложность алгоритма характеризуется как [latex]O \left( n \cdot \ln n \right)[/latex]. Это лучший из теоретически возможных вариантов для сортировки сравнениями.

Типизированные сортировки строятся на использовании какой-либо дополнительной информации о специфических свойствах и методах сортируемых объектов. Например, может быть заранее известен перечень всех возможных значений, встречающихся в сортируемом множестве и их не слишком много, то можно применить сортировку подсчётом. Это очень эффективный алгоритм с линейной характеристикой вычислительной сложности, однако он требует дополнительной памяти для размещения счётчиков.
Если сортируются числа известной разрядности (или строки фиксированной длины), то может оказаться эффективной поразрядная LSD сортировка (Least Significant Digit radix sorts). Асимптотическая сложность таких алгоритмов может быть лучше чем для сортировок компараторами часто линейная [latex]O \left( n \right)[/latex]. Однако иногда где-нибудь всё же прячется логарифм. Например в поразрядной сортировке количество повторов равно числу разрядов в сортируемых числах, а это логарифм от максимального сортируемого числа.

Рассмотрим пример вызова функции sort() для сортировки массива целых чисел.

#include <iostream>
#include <algorithm>

using namespace std;

int main () {
	int x[] = {2, 4, 1, 7, 8, 0, 9};
	sort(x, x + sizeof(x) / sizeof(int));
	for (int y: x) cout << ' ' << y;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main () {

int x[] = {2, 4, 1, 7, 8, 0, 9};

sort(x, x + sizeof(x) / sizeof(int));

for (int y: x) cout << ' ' << y;

}

Выполнить код
Как видите, здесь нет функции компаратора. Т.е. используется стандартная сортировка целых чисел по возрастанию.

А если нужно отсортировать по убыванию? Пишем компаратор.

#include <iostream>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
	return (a > b); 
}

int main () {
	int x[] = {2, 4, 1, 7, 8, 0, 9};
	sort(x, x + sizeof(x) / sizeof(int), compare);
	for (int y: x) cout << ' ' << y;
}

#include <iostream>

#include <algorithm>

using namespace std;

bool compare(int a, int b) {

return (a > b);

}

int main () {

int x[] = {2, 4, 1, 7, 8, 0, 9};

sort(x, x + sizeof(x) / sizeof(int), compare);

for (int y: x) cout << ' ' << y;

}

Выполнить код

Задача 1. Попробуйте так написать компаратор, чтобs вначале шли все нечётные числа по возрастанию, а потом — все чётные, но по убыванию.

Продолжение следует…

Если со всем разобрались, то можно приступать к решению задач своего варианта. Или можно посмотреть как решали задачи другие студенты.

Решения задач

acm.timus.ru №2002. Тестовое задание Опубликовал 09/12/2015Швандт Максим Альбертович
Автор задачи: Кирилл Бороздин Источник задачи: Уральская региональная командная олимпиада по программированию 2013 Ограничения: Время: 0.5 секунды Память 64 Мб Условие Это было обычное хмурое октябрьское утро. Небо ...
e-olymp 138. Банкомат Опубликовал 20/09/2015Женя Максимова
Задача. В банкомате имеются в достаточном количестве купюры номиналом гривен. Найти минимальное количество ...
e-olymp 145. Квадраты Опубликовал 25/06/2019Алина Гук
Задача взята с сайта e-olymp Задача Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять ...
e-olymp 1462. Хитрая сортировка Опубликовал 25/02/2020Нина Хоробрых
Задача Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих ...
e-olymp 1462. Хитрая сортировка Опубликовал 26/02/2020Николай Жирко
Задача Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих ...
e-olymp 2662. Метод минимума Опубликовал 01/02/2020Виктория Крачилова
Условие задачи Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент? Входные данные Первая строка содержит количество ...
e-olymp 2663. Сортировка пузырьком Опубликовал 28/01/2020Даниил Кадочников
Условие Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива. Входные данные В первой строке содержится количество элементов $n$ ($1 ...
e-olymp 333. Детская железная дорога-2 Опубликовал 18/06/2017Антон Куперман
Задача После того как мама запретила Витэку заниматься неизвестным языком и забрала у него все кубики, не относящиеся к латинскому алфавиту, ...
e-olymp 3835. Минимальный каркас Опубликовал 13/07/2021Yezhkova
Задача В связном графе найдите остовное дерево минимального веса. Входные данные Первая строка содержит два натуральных числа $n$ и $m$ $($$1 \leqslant n ...
e-olymp 4003. Топологическая сортировка Опубликовал 26/03/2016Сплошнов Кирилл
Задача взята отсюда. Условие Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать. Входные данные В первой строке содержатся два натуральных числа 1 \leq n ...
e-olymp 6. Путёвки Опубликовал 21/12/2015Александр Коломеец
Постановка задачи e-olymp 6. Путёвки Туристическая фирма не успела из-за больших морозов продать ) путёвок на горнолыжные базы, срок ...
e-olymp 7241. Transit Опубликовал 06/03/2021Дарієнко Дмитро
Задача Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний ...
e-olymp 972. Сортировка времени Опубликовал 20/06/2019Виктор Иванов
Задача Отсортируйте время согласно заданному критерию. Входные данные Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. ...
OCPC2021 D: Столовая Опубликовал 13/11/2021Мазурок Игорь Евгеньевич
Вы можете зарегистрироваться и решать эту задачу здесь. Ограничение времени: 2 с Ограничение реального времени: 5 с Ограничение памяти: 256M Столовая В столовой заведения «Покосившийся Скворечник» имеется ровно k тарелок, ...
А808 б Опубликовал 20/12/2014Сіренко Валерія Сергіївна
Задача : Дан текст. Группы символов, разделенные пробелами (одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как и ...
М16. Freshly Pressed Juice Опубликовал 29/11/2014Іванов Вячеслав Володимирович
Формулировка задачи Известно, что каждый посетитель фруктового бара просит сделать наиболее дешевый коктейль из свежевыжатого сока. Объем стакана для сока V. ...
Ю12.19 Опубликовал 24/11/2014Марченко Філіп Олександрович
Задача: В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть ...