🗊Презентация Сортировка

СОРТИРОВКА

Сортировка Пусть есть последовательность a0, a1... an и функция сравнения, которая на любых двух элементах последовательности принимает одно из трех значений: меньше, больше или равно. Задача сортировки состоит в перестановке членов последовательности таким образом, чтобы выполнялось условие: ai <= ai+1, для всех i от 0 до n.

Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, как на рис. 1, а сортировка происходит по одному из них, например, по x. Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, как на рис. 1, а сортировка происходит по одному из них, например, по x.

Сортировка вставками

Анализ сортировки вставками После каждой итерации только один элемент данных помещается в свою правильную позицию. При сортировке вставками выполняется меньше перестановок, чем в пузырьковой сортировке. Наихудший случай — когда все элементы данных отсортированы в обратном порядке. Наилучший случай — когда элементы почти отсортированы в правильном порядке. Сортировка вставками легко реализуется.

Сортировка вставками со сторожевым элементом

Сортировка выбором

Анализ сортировки выбором Метод основывается на нахождении максимального (минимального) значения и перестановках. Всего потребуется n-1 раз выполнить эту последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а не отсортированная, соответственно, уменьшаться. Общее количество сравнений для сортировки выбором можно вычислить так: (п-1) + (п-2) + (п-3) +...+ [n-(n-1)] = п(п-1)/2 = п2/2 - п/2 = 0(п2) - это сценарий худшего и лучшего случаев. Сортировка выбором не учитывает частичной сортировки, которая может существовать в исходных данных.

Сортировка пузырьком

Анализ пузырьковой сортировки После каждой итерации только один элемент данных помещается в свою правильную позицию. При пузырьковой сортировке сравниваются и переставляются смежные элементы данных. Худший случай — когда элементы данных отсортированы в обратном порядке. Лучший случай — когда элементы данных уже отсортированы в правильном порядке. Пузырьковая сортировка легко реализуется и не требует дополнительной памяти.

Сортировка слиянием Метод сортировки "слиянием" состоит в разбиении данного массива на несколько частей, которые сортируются по отдельности и впоследствии "сливаются" в одну. Операция слияния: из каждой части выбирается по одному элементу, и меньший из них помещается в результирующий массив. так продолжается до тех пор, пока не будет исчерпана одна из частей, оставшаяся часть просто переносится в конец результирующего массива.

Анализ сортировки слиянием Сортировка слиянием представляет собой пример стратегии "разделяй и властвуй": В этом методе фаза разбиения очень простая: она просто делит список пополам. Фаза слияния более сложная. На каждом просмотре сортировка слиянием проходит весь список и выполняет O(n) сравнений. На первом просмотре при сортировке слиянием рассматривается только один список. На втором просмотре этот алгоритм разбивает список на две половины, а затем сортирует и сливает их. Поскольку список разбивается пополам, мы получаем не более log2 подсписков для списка из n элементов. В худшем случае сортировка слиянием имеет производительность порядка nlog2n .

Быстрая сортировка Алгоритм основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Используется рекурсивная реализация сортировки: Выбрать элемент данных и сделать его точкой разбиения таким образом, чтобы он разбивал массив на левый и правый подмассивы. Применить быструю сортировку к левому подмассиву. Применить быструю сортировку к правому подмассиву.

Анализ быстрой сортировки Быструю сортировку следует рассмотреть одной из первых при выборе метода внутренней сортировки. Этот алгоритм содержит сложную фазу разбиения и простую фазу слияния. В лучшем случае выполняется работа порядка nlog2n; в худшем случае выполненная работа эквивалентна работе при сортировке выбором, т.е. O(n2). Производительность быстрой сортировки сильно зависит от выбора точки разбиения. Лучше всего быстрая сортировка сортирует массивы, в которых порядок элементов в массиве случаен.

Сортировка Шелла

Анализ сортировки Шелла Производительность худшего случая находится в интервале от n1,5 до 1.6n1,25. Эффективность этого метода сильно зависит от выбора последовательности значений для h (число разбиений на подмассивы). Не существует идеальной формулы для выбора этой последовательности, но хорошо подобранные последовательности показывают производительность сортировки по методу Шелла порядка nlog2n. Сортировка по методу Шелла практически нечувствительна к исходным данным и показывает худшую производительность, чем пузырьковая сортировка и сортировка вставками, когда исходные данные почти отсортированы. Для случайных наборов данных сортировку Шелла следует рассматривать в числе первых.

Сортировка подсчетом Идея алгоритма состоит в следующем: для каждого элемента найти, сколько элементов, меньших определенного числа, поместить это число на соответствующие место. Особенности алгоритма: Сортировка подсчетом метод подходит для сортировки целых чисел из не очень большого диапазона. Этот простой метод не использует вложенных циклов и, учитывая небольшой диапазон значений, время его работы есть O(n).

Поразрядная сортировка Поразрядная (цифровая) сортировка является улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку. Идея состоит в следующем: Отсортировать числа по младшему разряду, Потом устойчивой сортировкой отсортировать по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы. Время работы всей сортировки есть O(n). Таким способом можно сортировать не только числа, но и строки, если же использовать сортировку слиянием в качестве устойчивой, то можно сортировать объекты по нескольким полям.

Сравнение времени сортировок

Сравнение характеристик методов сортировки