Шейкерная сортировка ShakerSort презентация

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

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

Шейкерная сортировка 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)

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

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

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

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

Метод прямого включения Алгоритм на псевдокоде 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

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

Для определения трудоемкости оценим количество операций для каждого значения 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→∞. Метод прямого включения устойчивый. Метод сильно зависит от исходной упорядоченности массива.

Видео: InsertSort

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

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

Метод Шелла (ShellSort) Алгоритм на псевдокоде <вычисление массива шагов h> 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

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

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

Эффективность метода Шелла по времени работы зависит от выбора значений шагов. Эффективность метода Шелла по времени работы зависит от выбора значений шагов. Последовательность значений шагов, которая дает наилучшую трудоемкость, пока неизвестна, но существует и часто используется следующая последовательность шагов, предложенная Д.Кнутом: 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.

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

Видео: ShellSort