18_LinearSort

1.

Общие сведения о сортировках

Наименьшее время сортировки

Теорема.

–В любом алгоритме, упорядочивающем с помощью сравнения пар, на упорядочивание

последовательности из n элементов тратится не меньше, чем c nlogn сравнений, где c – константа (не зависящая от n).

Виды сортировок

Сортировки использующие сравнения:

–―пузырьком‖;

–вставками;

–выбором;

–слиянием;

–пирамидальная;

–Шелла;

–Хоара (быстрая).

Виды сортировок

Сортировки использующие сравнения

Сортировки не использующие сравнения:

–подсчѐтом;

–поразрядная.

Основные характеристики сортировок

Устойчивость

–не меняет взаимного расположения равных элементов.

Естественность поведения

–работает быстрее на уже отсортированных массивах.

Использование операции сравнения.

2.

Сортировки не использующие сравнения

2.1.

Сортировка подсчѐтом

Идея сортировки подсчѐтом

Сортировка подсчѐтом (counting sort).

Идея сортировки заключается в том, что необходимо посчитать количество элементов в исходном массиве и дальше записать их в отсортированном порядке посчитанное число раз.

Рассмотрим пример…