Улучшенные сортировки. Метод Шелла (Лекция 11) - презентация, доклад, проект скачать

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

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №1

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №2

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №3

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №4

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №5

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №6

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №7

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №8

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №9

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №10

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №11

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №12

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №13

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №14

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №15

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №16

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №17

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №18

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №19

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №20

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №21

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №22

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №23

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №24

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №25

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №26

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №27

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №28

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №29

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №30

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №31

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №32

Улучшенные сортировки. Метод Шелла (Лекция 11), слайд №33

Содержание ▲

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

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

Слайд 1

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

Лекция 11 Улучшенные сортировки

Слайд 2

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

Сортировка включениями с убывающим шагом. Метод Шелла Хоар, Флойд, Шелл: для алгоритмов сортировки, перемещающих в последовательности запись вправо или влево только на одну позицию, среднее время работы будет в лучшем случае пропорционально N2. Хотелось бы, чтобы записи перемещались «большими скачками, а не короткими шажками». Д. Шелл предложил в 1959 г. метод, названный сортировкой с убывающим шагом.

Слайд 3

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

Пример работы сортировки Шелла На первом проходе выделим в подпоследовательности элементы, отстоящие друг от друга на четыре позиции: Полученные 4 последовательности отсортируем на месте независимо друг от друга методом простых включений. Этот процесс называется 4-сортировкой.

Слайд 4

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

Пример работы сортировки Шелла, продолжение В результате 4-сортировки получим последовательность: _________________________________ | | | | 40 14 2 38 90 51 8 63 |__________|__________|__________| На следующем шаге элементы, отстоящие друг от друга на две позиции, объединяются в подпоследовательности и сортируются простыми вставками независимо друг от друга. Этот процесс называется 2-сортировкой. После 2-сортировки получим последовательность: 2 14 8 38 40 51 90 63 Ее сортируют методом простых вставок. К последнему шагу элементы довольно хорошо упорядочены, поэтому требуется мало перемещений. Данный процесс называется 1-сортировкой.

Слайд 5

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

Выбор шага в сортировке Шелла В сортировке методом Шелла можно использовать любую убывающую последовательность шагов ht, ht-1, ..., h1 Чтобы выбрать некоторую хорошую последовательность шагов сортировки, нужно проанализировать время работы как функцию от этих шагов. До сих пор не удалось найти наилучшую возможную последовательность шагов ht, ht-1, ..., h1 для больших N. Выявлен примечательный факт, что элементы последовательностей приращений не должны быть кратны друг другу. Это позволяет на каждом проходе сортировки перемешивать цепочки, которые ранее никак не взаимодействовали. Желательно, чтобы взаимодействие между разными цепочками происходило как можно чаще. Кнут: ..., 121, 40, 13, 4, 1, где hk+1= 3  hk + 1, h1 = 1 ..., 31, 15, 7, 3, 1, где hk+1 = 2 hk + 1, h1 = 1

Слайд 6

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

Анализ эффективности метода Утверждение Если k-отсортированная последовательность i-сортируется (k > i), то она остается k-отсортированной. → C каждым следующим шагом сортировки с убывающим приращением количество отсортированных элементов в последовательности возрастает. Для последовательности шагов 2k + 1, ..., 9, 5, 3, 1 количество пересылок пропорционально N1.27, для последовательности 2k – 1, ..., 15, 7, 3, 1 — N1.26, для последовательности (3k – 1)/2, ..., 40, 13, 4, 1 — N1.25 Общая оценка: величина порядка N3/2

Слайд 7

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

Алгоритм процедура Вставка(b, h) // b — номер первого элемента последовательности // h – величина шага начало процедуры // Пусть i – номер первого элемента в несортированной части массива i := b + h; пока i  N выполнять x:= A[i]; j := i – h; пока j  b и A[j]>x выполнять // Все элементы из отсортированной части, большие // x, сдвинуть на величину шага h вправо, A[j+h] := A[j]; j := j – h; конец пока // Элемент x поставить на свое место по порядку: A[j+h] := x; i := i + h; конец пока конец процедуры

Слайд 8

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

Алгоритм, продолжение Основная программа: // Выбор начального шага: h := 1; пока h < N/3 выполнять h := 3*h + 1; конец пока // Сортировка: пока h  1 выполнять цикл по i от 1 до h с шагом 1 выполнять Вставка (i, h); конец цикла h := (h – 1) / 3; конец пока

Слайд 9

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

Пирамидальная сортировка При сортировке методом простого выбора на каждом шаге выполняется линейный поиск минимального элемента. Линейная сложность этого поиска делает сложность всей сортировки квадратичной. Возможно ли найти минимальный элемент за время лучшее линейного? Оказывается, что это возможно, если использовать на каждом следующем шаге информацию о взаимных отношениях элементов, накопленную на предыдущих шагах. Идея бинарного выбора может быть эффективно применена, если организовать входные данные в виде так называемой пирамиды (или сбалансированного бинарного дерева поиска) и поддерживать их в этом виде в процессе сортировки. Метод сортировки с использованием такой пирамиды был предложен Р. У. Флойдом в 1964 г. под названием «Heap sort» — пирамидальной сортировки или сортировки кучей.

Слайд 10

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

Свойство пирамиды Пусть дана последовательность h1, ..., hn. Элемент hi образует пирамиду в этой последовательности, если выполнены следующие условия: если 2  i ≤ n, то hi ≥ h2i и h2i образует пирамиду; если 2  i + 1 ≤ n, то hi ≥ h2i+1 и h2i+1 образует пирамиду. Элементы hn/2+1, ..., hn всегда образуют тривиальные пирамиды, поскольку для них приведенные условия имеют ложные посылки. Если элемент h1 образует пирамиду, то и каждый элемент последовательности образует пирамиду. В этом случае будем говорить, что вся последовательность является полной пирамидой.

Слайд 11

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

Полная пирамида при n=15 Полная пирамида может быть изображена в виде корневого бинарного дерева, в котором элементы h2i и h2i+1 являются сыновьями элемента hi. Элемент в любом узле численно не меньше всех своих потомков, а вершина полной пирамиды h1 содержит максимальный элемент всей последовательности.

Слайд 12

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

Пример полной пирамиды при n=12 Если число элементов в полной пирамиде не равно 2k – 1, самый нижний уровень дерева будет неполным: недостающих сыновей можно достроить, добавив в пирамиду несколько заключительных «минимальных» элементов «0», не нарушающих условия пирамиды. Последовательность, упорядоченная по убыванию, является полной пирамидой. Например, последовательность из 12 элементов 12, 11, 7, 8, 10, 6, 3, 2, 1, 5, 9, 4 является полной пирамидой с вершиной 12.

Слайд 13

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

Идея метода пирамидальной сортировки Подготовка к сортировке: входная неупорядоченная последовательность перестраивается в пирамиду. Сортировка: входная и готовая последовательности хранятся в одном массиве, причем готовая последовательность формируется в хвосте массива, а входная остается в начале массива. Основой реализации метода является следующая процедура просеивания. Пусть в последовательности h1, ..., hn элементы hi+1, ..., hn уже образуют пирамиды. Требуется перестроить последовательность так, чтобы пирамиду образовывал элемент hi. На каждой итерации цикла наибольший из трех элементов hi, h2i и h2i+1 путем обмена оказывается в корне текущего поддерева, что обеспечивает истинность условий пирамиды в этом корне. Если при этом изменяется корень левого или правого поддерева, то просеивание продолжается для него.

Слайд 14

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

Построение пирамиды a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Шаг 1, i=5: 52 81 42 23 11 76 91 63 37 20 Шаг 2, i=4 : 52 81 42 23 20 76 91 63 37 11 Шаг 3, i=3 : 52 81 42 63 20 76 91 23 37 11 Шаг 4, i=2 : 52 81 91 63 20 76 42 23 37 11 Шаг 5, i=1 : 52 81 91 63 20 76 42 23 37 11 Выход: 91 81 76 63 20 52 42 23 37 11

Слайд 15

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

Сортировка На каждом шаге сортировки первый элемент массива, т. е. максимальный элемент пирамиды, переносится в начало готовой последовательности путем обмена с последним элементом пирамиды, занимающим его место. Затем остаток входной последовательности вновь перестраивается в пирамиду, обеспечивая корректность следующего шага. В начале i-го шага элементы a1, .., ai, по предположению, хранят входную последовательность как пирамиду, а ai+1, .., aN – упорядоченную по возрастанию готовую последовательность (изначально пустую). На i-м шаге текущий максимальный элемент пирамиды а1 обменивается с аi, становясь началом новой готовой последовательности, где он будет новым минимальным элементом. Входная последовательность (пирамида) при этом претерпевает два изменения: — она теряет последний элемент, что не нарушает условий пирамиды ни в одном узле; — ее первый элемент становится произвольным, что может нарушать условие пирамиды только в первом узле.

Слайд 16

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

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

Слайд 17

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

Слайд 18

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

Алгоритм процедура Просеивание (i, n) // i – номер элемента, который нужно просеять // n – номер последнего элемента массива начало процедуры пока 2*i

Слайд 19

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

Алгоритм, продолжение Основная программа: Шаг 1. Построение пирамиды: i := N / 2; пока i  1 выполнять Просеивание (i, N); i := i – 1; конец пока Шаг 2. Сортировка на пирамиде: i := N; пока i > 1 выполнять Обмен (1, i); i := i – 1; Просеивание (1, i); конец пока конец основной программы

Слайд 20

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

Анализ Число итераций цикла в процедуре просеивания не превосходит высоты пирамиды. Высота полного бинарного дерева из N узлов, каковым является пирамида, равна [log2 N]. Просеивание имеет логарифмическую сложность. Итоговая сложность пирамидальной сортировки ~N  log2 N. Наилучший случай – обратное упорядочение входной последовательности.

Слайд 21

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

Сортировка с разделением. Быстрая сортировка Ч. Э. Р. Хоар Это метод сортировки, при котором обмениваются местами пары несоседних элементов, а задача сортировки последовательности рекурсивно сводится к задачам сортировки ее меньших частей. Допустим сначала, что мы уже переупорядочили некоторым образом элементы входной последовательности, после чего оказалось возможным разделить ее на две непустые части по границе некоторого индекса т: левую (индексы 1...т) и правую (индексы т+1...N); причем значения всех элементов левой части не превосходят значений всех элементов правой части:  i, j: 1  i  m и m < j  N выполнено: аi  aj. (*) Индекс т назовем медианой.

Слайд 22

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

Сортировка разделением, идея алгоритма Отсортируем любым методом обмена отдельно левую часть, не затрагивая элементов правой части, а затем отдельно правую, не трогая левой. При этом обмениваться могут только пары элементов, находящиеся в одной части, поэтому никакой обмен не нарушает свойство (*). Значит, оно будет верно и для результирующей последовательности, которая в силу этого оказывается упорядоченной в целом. СортировкаРазделением (l, r) /* l, r – границы сортируемой подпоследовательности */ /* Разделение */ привести подпоследовательность аl,…, аr к условию (*) и определить медиану m; /* Рекурсивный спуск */ если l < m то // части длины 0 и 1 не сортируем СортировкаРазделением (l, m); если m + 1 < r то // части длины 0 и 1 не сортируем СортировкаРазделением (m + 1, r); конец

Слайд 23

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

Получается, что в процессе дробления исходной задачи на подзадачи мы приходим к тривиальным подзадачам: сортировке последовательностей длины 0 и 1. Получается, что в процессе дробления исходной задачи на подзадачи мы приходим к тривиальным подзадачам: сортировке последовательностей длины 0 и 1. Не приходится ничего делать и для слияния решений подзадач в решение исходной задачи во время возврата из рекурсии: упорядоченные последовательности образуются сами собой по мере упорядочения их частей. Где же тогда фактически выполняется сортировка? - На фазе разделения, иллюстрируя, как хорошая подготовка условий для решения зачастую уже и дает решение! В качестве критерия разделения нам понадобится так называемый пилотируемый элемент х. В классической версии алгоритма в качестве x выбирается произвольный элемент сортируемой последовательности: первый, последний, расположенный в середине или иначе. Влияние его выбора на эффективность алгоритма мы обсудим ниже.

Слайд 24

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

В процессе разделения мы соберем в левой части последовательности все элементы аi  х, а в правой — все элементы aj  x. В процессе разделения мы соберем в левой части последовательности все элементы аi  х, а в правой — все элементы aj  x. Условие (*) при этом будет выполнено даже при возможном наличии одинаковых элементов x в обеих частях. Введем два бегущих индекса-указателя i и j, которые делят разделяемую подпоследовательность на три участка: левый (al ... ai-1), правый (aj+1 ... ar), средний (ai ... aj). В левом и правом участках будут накапливаться элементы левой и правой частей, подлежащих затем рекурсивной сортировке, а в среднем находятся остальные, еще не распределенные элементы.

Слайд 25

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

Процесс разделения i = l; j = r; цикл пока ai < х цикл /* проверка i < r не нужна: х где-то есть */ i := i + 1; /* в конце ai  х */ конец цикла; пока х < aj цикл /* проверка j > i не нужна: х есть */ j := j – 1; /* в конце aj  х */ конец цикла; если i ≤ j то /* если i = j, a[i = j] = x, нужен сдвиг индексов для выхода из цикла */ обменять ai и aj ; /* теперь ai  х  aj */ i := i + 1; /*на случай ai = х : добавить в левую часть */ j := j – 1;/* на случай aj = х : добавить в правую часть */ пока i < j;

Слайд 26

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

Комментарии Циклы по встречным индексам переносят из средней части в левую или правую элементы, строго меньшие или большие х, которые могут быть добавлены в эти части без перестановки. После их выполнения процесс разделения либо заканчивается (если i  j), либо пара ai и aj образует инверсию. В последнем случае их следует обменять и включить в левую и правую части. Вот здесь и происходят упорядочивающие обмены с уменьшением числа инверсий в последовательности!

Слайд 27

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

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

Слайд 28

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

Цикл оканчивается при i  j. Однако нам еще надо определить медиану. Определенные границы левой части – l...i – 1, правой – j + 1...r, однако интервал j + 1...i – 1 может быть не вырожден и заполнен элементами х (почему?). Эти элементы останутся на своих местах в процессе сортировки (почему?), поэтому их можно исключить из левой и правой частей. Окончательно границами левой части можно считать l...j, а правой – i...r.

Слайд 29

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

Процесс разделения, пример Разделение: 40 51 8 38 89 1 15 63 Начало: i x j Первый проход:i j Сближение Обмен 15 51 8 38 89 1 40 63 Второй проход: i j Сближение Обмен i j 15 1 8 38 89 51 40 63 Третий проход: i j Сближение ij Обмен 15 1 8 38 89 51 40 63 Четвертый проход: j i Сближение

Слайд 30

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

Слайд 31

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

Анализ Процессу разбиения подвергается весь массив, следовательно выполняется N сравнений. Число обменов? Пусть после разделения х будет занимать в массиве позицию k. Число требующихся обменов равно числу элементов в левой части массива (k - 1), умноженному на вероятность того, что элемент нужно обменять. Элемент обменивается, если он не меньше, чем х. Вероятность этого равна (N - (k - 1))/N.

Слайд 32

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

Анализ, продолжение Просуммируем всевозможные варианты выбора медианы и разделим эту сумму на N, в результате получим ожидаемое число обменов: Ожидаемое число обменов равно приблизительно N/6. В лучшем случае каждое разделение разбивает массив на две равные части, а число проходов, необходимых для сортировки, равно log2 N. Тогда общее число сравнений равно N log2 N.

Слайд 33

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

Анализ, продолжение Однако в худшем случае сортировка становится «медленной». Например, когда в качестве пилотируемого элемента всегда выбирается наибольшее значение. Тогда в результате разбиения в левой части оказывается N - 1 элемент, т. е. массив разбивается на подмассивы из одного элемента и из N - 1 элемента. В этом случае вместо log2 N разбиений необходимо сделать ~ N разбиений. В результате в худшем случае оценка оказывается ~ N2, что гораздо хуже пирамидальной сортировки.