1. Сортировка и поиск

Применение и виды сортировки

Сортировку необходимо применять в следующих случаях:
1. В условии задачи явно указано необходимость сортировки выводимых результатов или входных данных.
Примеры задач:
1126. ICQ
1504. Резервное копирование

2. После выполнения сортировки входных данных решение задачи сводится к последовательной обработке введенной информации (задаче сканирования)
Примеры задач:
174. Различные числа
50. Закраска прямой

3. Необходимо часто выполнять поиск значений в какой-то последовательности. После сортировки этой последовательности время поиска значения уменьшится с `O(N)` до `O(log\ N)`.
Примеры задач:
141. Шпионское сообщение
1521. Пирамиды

Для сортировки можно использовать следующие алгоритмы:
1. Сортировка пузырьком
Реализация этого алгоритма весьма проста, но время работы этого алгоритма равно `O(N^2)`, следовательно, его можно применять только в случае, если `N` не превосходит 1000.
Пример реализации и применения:
Разбор задачи 1126. ICQ

2. Сортировка подсчетом
Время работы этого алгоритма равно `O(N)`, но его можно применять только в случае, если диапазон сортируемых значений не превосходит 1000000.
Пример реализации и применения:
Разбор задачи 163. Анаграммы

3. Быстрая сортировка
На применение алгоритма нет ограничений и его время работы равно `O(N\ log\ N)`.
Пример реализации и применения:
Разбор задачи 50. Закраска прямой

Для поиска значения в отсортированной последовательности применяется бинарный поиск.
Пример реализации и применения:
Разбор задачи 1366. Дипломы