Сортировки

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

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

Задачи на сортировку можно разделить на две группы: сортировки компараторами (сравнениями) и типизированные сортировки.
Сортировки компараторами используются в тех случаях, когда мы можем сравнить любую пару объектов и узнать какой из них больше. Это наиболее общий тип сортировок. Такие сортировки строятся на основе некоторой функции (компаратора), которая может сравнить два объекта сортируемого типа и возвращает 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() для сортировки массива целых чисел.

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

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

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

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

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

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

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

  • acm.timus.ru №2002. Тестовое задание
    Опубликовал 09/12/2015 Швандт Максим Альбертович

    Автор задачи: Кирилл Бороздин Источник задачи: Уральская региональная командная олимпиада по программированию 2013 Ограничения: Время: 0.5 секунды Память 64 Мб Условие Это было обычное хмурое октябрьское утро. Небо ...

  • e-olymp 138. Банкомат
    Опубликовал 20/09/2015 Женя Максимова

    Задача. В банкомате имеются в достаточном количестве купюры номиналом гривен. Найти минимальное количество ...

  • e-olymp 333. Детская железная дорога-2
    Опубликовал 18/06/2017 Антон Куперман

    Задача После того как мама запретила Витэку заниматься неизвестным языком и забрала у него все кубики, не относящиеся к латинскому алфавиту, ...

  • e-olymp 4003. Топологическая сортировка
    Опубликовал 26/03/2016 Сплошнов Кирилл

    Задача взята отсюда. Условие Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать. Входные данные В первой строке содержатся два натуральных числа 1 \leq n ...

  • e-olymp 6. Путёвки
    Опубликовал 21/12/2015 Александр Коломеец

    Постановка задачи e-olymp 6. Путёвки Туристическая фирма не успела из-за больших морозов продать ) путёвок на горнолыжные базы, срок ...

  • А808 б
    Опубликовал 20/12/2014 Сіренко Валерія Сергіївна

    Задача : Дан текст. Группы символов, разделенные пробелами (одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как и ...

  • Ю12.19
    Опубликовал 24/11/2014 Марченко Філіп Олександрович

    Задача:  В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть ...

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)