Простые сортировки

Задача сортировки

Содержание

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

Лекция 4.

Лекция 4. 1

Задача сортировки. 1

Простые сортировки. 2

Сортировка простыми вставками. 2

Алгоритм ПрВст. 2

Реализация алгоритма ПрВст. 2

Метод прямых вставок с барьером (ПрВстБар) 3

Эффективность алгоритма ПрВстБар. 3

Пример сортировки. 3

Сортировка бинарными вставками. 4

Реализация алгоритма БинВст. 5

Эффективность алгоритма БинВст. 5

Сортировка простым выбором.. 6

Сортировка простыми обменами. 7

Улучшенные сортировки. 7

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

Пирамидальная сортировка. 11

Пример результата просеивания. 12

Эффективность алгоритма УлПир. 15

Быстрая сортировка. 15

Эта лекция посвящена сугубо алгоритмической проблеме упорядочения данных.

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

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

Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами)1).

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

К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С - некоторая константа.

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

Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время. Однако точные значения удается найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием "пропорционально", которое не учитывает конкретные значения констант, входящих в итоговую формулу. Общую же эффективность алгоритма обычно оценивают "в среднем": как среднее арифметическое от сложности алгоритма "в лучшем случае" и "в худшем случае", то есть (Eff_best + Eff_worst)/2.

Дата добавления: 2013-12-13