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

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

Шейкерная сортировка ShakerSort, слайд №1

Шейкерная сортировка ShakerSort, слайд №2

Шейкерная сортировка ShakerSort, слайд №3

Шейкерная сортировка ShakerSort, слайд №4

Шейкерная сортировка ShakerSort, слайд №5

Шейкерная сортировка ShakerSort, слайд №6

Шейкерная сортировка ShakerSort, слайд №7

Шейкерная сортировка ShakerSort, слайд №8

Шейкерная сортировка ShakerSort, слайд №9

Шейкерная сортировка ShakerSort, слайд №10

Шейкерная сортировка ShakerSort, слайд №11

Шейкерная сортировка ShakerSort, слайд №12

Шейкерная сортировка ShakerSort, слайд №13

Шейкерная сортировка ShakerSort, слайд №14

Шейкерная сортировка ShakerSort, слайд №15

Шейкерная сортировка ShakerSort, слайд №16

Шейкерная сортировка ShakerSort, слайд №17

Шейкерная сортировка ShakerSort, слайд №18

Шейкерная сортировка ShakerSort, слайд №19

Шейкерная сортировка ShakerSort, слайд №20

Шейкерная сортировка ShakerSort, слайд №21

Шейкерная сортировка ShakerSort, слайд №22

Содержание ▲

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

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

Слайд 1

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

Шейкерная сортировка ShakerSort Можно заметить, что в BubbleSort «легкие» элементы «всплывают» быстро, а «тяжелые» «тонут» медленно. Пример. СИДОРОВ ВО ВР ВО ВД ВИ ВСИДОРО

Слайд 2

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

Шейкерная сортировка ShakerSort ДВА (!) изменения в алгоритме, которые были предложены для уменьшения трудоемкости: 1) Изменение направления просмотра массива на каждой итерации. 2) Установление границ рабочей части массива на место последнего обмена на каждой итерации.

Слайд 3

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

Шейкерная сортировка ShakerSort Алгоритм на псевдокоде L, R – левая и правая границы рабочей части массива, n – количество элементов в массиве. L := 1, R := n, k := n, DO DO ( j := R, R-1, ... L+1) IF (aj < aj-1) aj↔aj-1, k := j FI OD L := k DO ( j := L, L+1, ... R-1) IF (aj > aj+1) aj↔aj+1, k := j FI OD R := k OD (L < R)

Слайд 4

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

К У Р А П О В А К У Р А П О В А А В А О А П А А А Р А У А К А К У Р А П О В К У Р У А У П У О У В У А К Р А П О В У В О В П А В А Р А К

Слайд 5

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

Два усовершенствования в алгоритме позволяют уменьшить только количество сравнений: Два усовершенствования в алгоритме позволяют уменьшить только количество сравнений: Мср = С < T = O(n2) , n→∞ Метод шейкерной сортировки сильно зависит от исходной упорядоченности массива по количеству сравнений. Метод обеспечивает устойчивую сортировку.

Слайд 6

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

Слайд 7

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

Видео: BubbleSort или ShakerSort ?

Слайд 8

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

Метод прямого включения InsertSort Начиная с i = 2 берём очередной i–й элемент массива и включаем его на нужное место среди первых (i-1) элементов, при этом все элементы, которые больше ai сдвигаются на одну позицию вправо.

Слайд 9

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

Метод прямого включения Алгоритм на псевдокоде DO ( i: = 2, 3, …, n ) t := ai, j := i -1 DO ( j > 0 и t < aj ) aj+1 := aj j := j -1 OD aj+1 := t OD

Слайд 10

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

К У Р А П О В А К У Р А П О В А К У Р А П О В А К Р У А П О В А А К Р У П О В А А К П Р У О В А А К О П Р У В А А В К О П Р У А А А В К О П Р У

Слайд 11

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

Для определения трудоемкости оценим количество операций для каждого значения i : Для определения трудоемкости оценим количество операций для каждого значения i : Cmin = 1 Cmax = i -1 Мmin = 2 Мmax = i +1 Тогда для всех i : Cmin = n -1 Cmax = Мmin = 2(n-1) Мmax = + 2n - 2 Средняя трудоемкость этого метода имеет квадратичный порядок T = O(n2) , n→∞. Метод прямого включения устойчивый. Метод сильно зависит от исходной упорядоченности массива.

Слайд 12

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

Слайд 13

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

Видео: InsertSort

Слайд 14

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

Метод Шелла ShellSort Из оценок метода прямого включения InsertSort видно, что, чем лучше упорядочен массив, тем меньше операций потребуется для его сортировки. Основная идея метода Шелла ShellSort состоит в предварительном улучшении порядка элементов массива, а затем окончательной сортировке его методом прямого включения. Шелл предложил работать в методе прямого включения с шагом k большим, чем 1, что предварительно улучшило бы упорядоченность массива. Чем больше величина шага, тем меньше операций сравнения и пересылки приходиться выполнять.

Слайд 15

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

Определение Предварительная сортировка массива методом прямого включения с шагом к > 1 называется к - сортировкой. Метод Шелла заключается в проведении сначала нескольких к-сортировок, а затем окончательной сортировке массива с шагом к=1. Обозначим H = ( h1 , h2 , … , hm ) – последовательность из m возрастающих шагов, где h1 = 1, h1 < h2 < h3 < …< hm . Производя последовательно к-сортировки с шагами hm , hm-1 ,.., h1 , получим упорядоченный массив. Это гарантируется тем, что последний шаг h1 = 1.

Слайд 16

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

Метод Шелла (ShellSort) Алгоритм на псевдокоде DO ( k := hm , hm-1 , … 1 ) DO ( i := k+1, k+2, … n ) t := ai , j := i - k DO ( j > 0 и t < aj ) aj+k := aj j := j - k OD aj+k := t OD OD

Слайд 17

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

К У Р А П О В А К У Р А П О В А К У Р А П О В А К А Р У П О В А К А П У Р О В А К А П О Р У В А В А К О П У Р А В А К А П О Р У

Слайд 18

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

В А К А П О Р У В А К А П О Р У А В К А П О Р У А В К А П О Р У А А В К П О Р У А А В К П О Р У А А В К О П Р У А А В К О П Р У

Слайд 19

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

Эффективность метода Шелла по времени работы зависит от выбора значений шагов. Эффективность метода Шелла по времени работы зависит от выбора значений шагов. Последовательность значений шагов, которая дает наилучшую трудоемкость, пока неизвестна, но существует и часто используется следующая последовательность шагов, предложенная Д.Кнутом: h1 = 1, hi = 2hi -1 +1, i = 2,…m, m = - 1 Пример n = 100, m = - 1 = 5, h1 = 1, h2 = 2h1 +1 = 3, h3 = 2h2 +1 = 7, h4 = 2h3 +1 = 15, h5 = 2h4 +1 = 31.

Слайд 20

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

При использовании последовательности шагов, предложенной Д.Кнутом, метод имеет порядок трудоёмкости O ( n1.2 ) , n→∞. При использовании последовательности шагов, предложенной Д.Кнутом, метод имеет порядок трудоёмкости O ( n1.2 ) , n→∞. Метод Шелла существенно быстрее методов с квадратичной трудоемкостью. В примере: Insert – 46 операций, Shell – 34 операции. Метод Шелла не устойчив. Метод зависит от исходной упорядоченности массива.