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

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

Метод прямого слияния MergeSort, слайд №1

Метод прямого слияния MergeSort, слайд №2

Метод прямого слияния MergeSort, слайд №3

Метод прямого слияния MergeSort, слайд №4

Метод прямого слияния MergeSort, слайд №5

Метод прямого слияния MergeSort, слайд №6

Метод прямого слияния MergeSort, слайд №7

Метод прямого слияния MergeSort, слайд №8

Метод прямого слияния MergeSort, слайд №9

Метод прямого слияния MergeSort, слайд №10

Метод прямого слияния MergeSort, слайд №11

Содержание ▲

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

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

Слайд 1

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

Метод прямого слияния MergeSort Дан неупорядоченный список S. В основе алгоритма лежит операция слияния серий. Определение. p-серией называется неубывающая последовательность из p элементов. Задача: Имеется две упорядоченные последовательности a и b размером q и r соответственно. Необходимо получить последовательность с путем слияния a и b, длина последовательности с будет равна q + r. Пример: a: 1 4 5 6’ b: 2 3 6” 7 8 с: 1 2 3 4 5 6’ 6” 7 8

Слайд 2

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

Слияние q–серии из списка a с r–серией из списка b, Слияние q–серии из списка a с r–серией из списка b, запись результата в очередь c DO ( q ≠ 0 и r ≠ 0 ) IF ( a→Data ≤ b→Data) < Переместить элемент из списка a в очередь c > q := q-1 ELSE < Переместить элемент из списка b в очередь c > r := r-1 FI OD DO ( q > 0 ) < Переместить элемент из списка a в очередь c > q := q-1 OD DO ( r > 0 ) < Переместить элемент из списка b в очередь c > r := r-1 OD

Слайд 3

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

Трудоемкость алгоритма слияния серий Трудоемкость зависит от расположения элементов в сериях. q 1 2 3 q 1 3 5 7 r 4 5 6 7 8 r 2 4 6 8 Количество сравнений: min (q, r) ≤ C ≤ q+r -1 Количество перестановок: M = q+r Метод прямого слияния ( MergeSort ) Пусть размер списка S = 2k. Список S расщепляем на два списка a и b. Сливаем списки a и b с образованием двойных серий, то есть одиночные элементы сливаются в упорядоченные пары, которые записываются попеременно в очереди c0 и c1 . Переписываем очередь c0 в список a, очередь c1 – в список b.

Слайд 4

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

Вновь сливаем списки a и b с образованием серий длины 4 , эатем длины 8 и т. д. Вновь сливаем списки a и b с образованием серий длины 4 , эатем длины 8 и т. д. На каждом шаге размер серий увеличивается вдвое. Когда получим одну серию длиной во весь список, процесс сортировки завершен. a 2 c0 --> a 4 c0 … a S c0 -> S b c1 --> b c1 … b Замечание: Если размер списка не кратен степени двойки, то нужно учесть, что какие-то серии могут быть короче, чем ожидается.

Слайд 5

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

S К У Р А’ П О В А” Е’ Л Е” Н А”’ S К У Р А’ П О В А” Е’ Л Е” Н А”’ a К Р П В Е’ Е” А”’ b У А’ О А” Л Н a ←c0 К У О П Е’ Л А”’ b ←c1 А’ Р А” В Е” Н

Слайд 6

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

a ←c0 А’ К Р У Е’ Е” Л Н a ←c0 А’ К Р У Е’ Е” Л Н b ←c1 А” В О П А”’ a ←c0 А’ А” В К О П Р У b ←c1 А”’ Е’ Е” Л Н S←c0 А’ А” А”’ В Е’ Е” К Л Н О П Р У

Слайд 7

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

Алгоритм расщепления списка S Расщепление (S, a, b, n) n - количество элементов в S k, p - рабочие указатели a := S, b := S→Next, n := 1 k := a, p := b DO ( p ≠ NIL ) n := n+1 k→next := p→next k := p p := p→next OD

Слайд 8

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

Метод прямого слияния (MergeSort)

Слайд 9

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

Метод прямого слияния (MergeSort) < Расщепление (S, a, b, n) > p := 1 DO ( p < n ) < инициализация очередей c0, c1 > i := 0, m := n DO ( m > 0 ) IF ( m ≥ p ) q := p ELSE q := m FI m := m – q IF ( m ≥ p ) r := p ELSE r := m FI m := m – r < слияние(a, q, b, r, ci ) > i := 1– i OD a := c0 . Head, b := c1. Head p := 2p OD c0 . Tail→next := NULL S := c0 . Head

Слайд 10

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

Трудоемкость метода MergeSort Трудоемкость сортировки следует из трудоемкости операции слияния серий. На каждой итерации «большого» цикла производится ровно n перемещений элементов списков и менее n сравнений элементов. Количество итераций равно ⌈⌉ C < n ⌈⌉ M = n ⌈⌉ + n T = O(n) Метод обеспечивает устойчивую сортировку. При реализации алгоритма для массивов метод требует наличия второй рабочей копии массива. При реализации алгоритма для списков копия массива не требуется.