Метод сортировки пирамидой - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Метод сортировки пирамидой. Доклад-сообщение содержит 7 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Метод сортировки пирамидой.

Слайд 2

Описание слайда:

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия: Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия: Каждый лист имеет глубину либо d, либо d – 1,d — максимальная глубина дерева. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков. Удобная структура данных для сортирующего дерева — такой массив Array, что Array[0] — элемент в корне, а потомки элемента Array[i] являются Array[2i+1] и Array[2i+2].

Слайд 3

Описание слайда:

Алгоритм сортировки будет состоять из двух основных шагов: 1. Выстраиваем элементы массива в виде сортирующего дерева Array[i]>=Array[2i+1] Array[i]>=Array[2i+2] При 0

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Недостатки Сложен в реализации. На почти отсортированных массивах работает столь же долго, как и на хаотических данных. На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти. Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа. Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла. Поведение неестественно: частичная упорядоченность массива никак не учитывается.