Основы программирования на С++ для начинающих

Сортировка. STL (часть 12)

Совершенно особую группу алгоритмов составляют сортировки — сортировать в практике приходится самые разнообразные объекты и по самым разнообразным критериям. Анализ алгоритмов сортировки хорошо и обстоятельно изучен, как ни один другой раздел вычислительной математики. Основным вопросом любого алгоритма сортировки является его вычислительная сложность — число операций сравнения-обмена, требуемых для сортировки последовательности длины N, так называемое O( N ).

Неприятным обстоятельством является то, что для разных алгоритмов различаются средняя сложность (на большинстве тестовых последовательностей) и максимальная сложность (на наихудшей для метода тестовой последовательности). Для нескольких десятков алгоритмов сортировки, предлагаемых в процессе обучения программированию, показано, что подавляющее большинство из них (интуитивно понятных) является худшими и в смысле средней и в смысле максимальной сложности. Как пример, популярная у студентов пузырьковая сортировка является наихудшей из всех вообще известных.

Эффективными (по сложности) из всего множества методов являются только несколько методов быстрых рекурсивных сортировок. Они то и представлены в реализациях алгоритмов STL. Стандарты не настаивают на жёстком ограничении на внутренних механизмах их реализации, поэтому могут быть варианты в зависимости от используемой библиотеки.

Теперь, обладая некоторыми знаниями об алгоритмах, функторах и общем состоянием дел с сортировками, мы готовы рассмотреть варианты реализации всего этого в своём коде. Для начала мы разнообразными способами сортируем числовые последовательности. Пример великоват, но он предназначен не только, и не сколько, для иллюстрации, как для последующего самостоятельного экспериментирования:

Перед компиляцией программы, в MVS нажмите Alt+F7 и внесите Аргументы команды ?30 +3:сортировка в с++

 Некоторая громоздкость примера связана с тем, что мы в одном коде объединяем и все предоставленные STL алгоритмы сортировки, и разнообразные тестовые сортируемые последовательности, например:

  • Несколько случайных (?) последовательностей длины 30, сортируемых с использованием (3) функтора сравнения, и детализированным (+) выводом входной и выходной последовательности:

    сортировка в с++

  • Инверсная (обратная, убывающая) последовательность, сортируемая (6) «в куче» с использованием бинарного дерева (аргументы команды -30 +6 ):сортировка в с++

  • Длинная (1000000) последовательность, в тех же, что и предыдущий случай, условиях, но с выводом только диагностики корректности результата (аргументы команды -1000000 6 ):

    сортировка в с++

Библиотека STL предоставляет 3 группы алгоритмов сортировки:

  • sort() – наиболее быстрая сортировка в среднем ( O( N * log( N ) ), но которая может «проваливаться» в худшем случае до O( N * N ) (а это очень плохой показатель);

  • sort_heap() – сортировка в «в куче», с использованием бинарного дерева, сложность которой всегда не хуже O( N + N * log( N ) ) (это хуже sort() в среднем, но лучше в наихудшем случае);

  • stable_sort() – «устойчивая» сортировка слиянием, устойчивость которой означает, что она сохраняет относительный порядок равных элементов после сортировки. Это иногда очень важно. Сложность этого алгоритма не намного уступает sort();

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *