Презентация на тему "Улучшенные сортировки"

Содержание

• 
  Слайд 1

  Лекция 11

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

• 
  Слайд 2

  Сортировка включениями с убывающим шагом. Метод Шелла

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

• 
  Слайд 3

  Пример работы сортировки Шелла

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

• 
  Слайд 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

• 
  Слайд 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содержит максимальный элемент всейпоследовательности. h1 h14 h13 h12 h11 h10 h9 h15 h8 h7 h6 h5 h4 h3 h2

• 
  Слайд 12

  Пример полной пирамиды при n=12

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

• 
  Слайд 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 :5281 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 узлов, каковым является пирамида, равна [log2N]. Просеивание имеет логарифмическую сложность. Итоговая сложность пирамидальной сортировки ~N log2N. Наилучший случай – обратное упорядочение входной последовательности.

• 
  Слайд 21

  Сортировка с разделением.Быстрая сортировка Ч. Э. Р. Хоар

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

• 
  Слайд 22

  Сортировка разделением, идея алгоритма

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

• 
  Слайд 23
  

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

• 
  Слайд 24
  

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

• 
  Слайд 25

  Процесс разделения

  i= l; j = r; цикл пока ai 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

• 
  Слайд 26

  Комментарии

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

• 
  Слайд 27
  

  Проверка того, что бегущие индексы не выходят за границы 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 4063 Третий проход: ij Сближение ij Обмен 15 1 8 38 89 51 4063 Четвертый проход: ji Сближение

• 
  Слайд 30
  

  1 8 38 89 51 40 63 x 1-задачи: 15 1 8 x 1 15 8 8951 40 63 x 40 51 89 63 2-задачи: 15 8 x 8 15 408963 x 63 89 Результат: 1 8 15 38 40 51 63 89 Разделение

• 
  Слайд 31

  Анализ

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

• 
  Слайд 32

  Анализ, продолжение

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

• 
  Слайд 33
  

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