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

Временная сложность сортировки, основанной на сравнениях

Объемная сложность сортировки

Устойчивость сортировки

Алгоритмы сортировки

Алгоритмы сортировки

Лекция 2

Существуют правила соединения управляющих структур.

Ø Каждая структура имеет только один вход и один выход. При последовательном соединении выход одной структуры соединяется с входом другой.

Ø Выход управляющей структуры "последовательность действий" соединен со входом управляющей структуры "выбор действия по условию", выход "выбор действия по условию" -со входом "последовательность действий".

Ø Основные управляющие структуры можно вкладывать друг в друга.

Перечисленные свойства управляющих структур лежат в основе современных методов разработки алгоритмов для сложных задач. В этих методах сначала разрабатывают решение задачи в общих чертах (без мелких деталей), а затем шаг за шагом уточняют детали алгоритмов до полного решения. Такой подход называют пошаговой детализацией алгоритма. Он относится к методу разработки "проектирование сверху -вниз". В этом методе тоже сначала определяют общее решение, а затем производят детализацию до нахождения полного решения.

Проблема упорядочивания данных с практической точки зрения: достоинства и недостатки пяти различных методов сортировки.

ü Алгоритмы внутренней сортировки (требуют произвольного доступа к элементам) обычно используются для сортировки в оперативной памяти

ü Алгоритмы внешней сортировки (обращаются к данным последовательно) применяются для сортировки файлов

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

Устойчивый алгоритм сохраняет относительный порядок следования записей с одинаковыми ключами.

Пример: сортировка алфавитного списка студентов по экзаменационной оценке.

Не все быстрые алгоритмы являются устойчивыми.

Многие алгоритмы требуют дополнительной памяти для сохранения копии сортируемого массива

Алгоритм сортировки можно представить в виде разрешающего дерева.

Число сравнений в худшем случае – высота разрешающего дерева h.
В дереве n! листьев => n! ≤ 2h => log (n!) ≤ h
=> h = Ω (n log n)

У простых алгоритмов сортировки сложность Ө(n2), у более сложных - Ө(n log n)

На i-ом шаге элемент a[i] вставляется на нужное место в уже отсортированную последовательность a[1]…a[i-1]. Для этого элемент сравнивается с предыдущим и либо ставится на место, либо предыдущий элемент сдвигается вправо, и операция повторяется со следующим элементом.

Сложность в лучшем случае Ө(n), в худшем и среднем Ө(n2).

Сортировку вставками следует применять в случае, когда последовательность почти упорядочена.