Содержание
- 2. Слияние q–серии из списка a с r–серией из списка b, запись результата в очередь c DO
- 3. Трудоемкость алгоритма слияния серий Трудоемкость зависит от расположения элементов в сериях. q 1 2 3 q
- 4. Вновь сливаем списки a и b с образованием серий длины 4 , эатем длины 8 и
- 5. S К У Р А’ П О В А” Е’ Л Е” Н А”’ a К
- 6. a ←c0 А’ К Р У Е’ Е” Л Н b ←c1 А” В О П
- 7. Алгоритм расщепления списка S Расщепление (S, a, b, n) n - количество элементов в S k,
- 8. Метод прямого слияния (MergeSort) Обозначение переменных: n – количество элементов в списке S a, b –
- 9. Метод прямого слияния (MergeSort) p := 1 DO ( p i := 0, m := n
- 10. Трудоемкость метода MergeSort
- 12. Скачать презентацию
Слайд 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
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
Трудоемкость алгоритма слияния серий
Трудоемкость зависит от расположения элементов в сериях.
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.
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
Вновь сливаем списки a и b с образованием серий длины 4
, эатем длины 8 и т. д.
На каждом шаге размер серий увеличивается вдвое.
Когда получим одну серию длиной во весь список, процесс сортировки завершен.
a 2 c0 --> a 4 c0 … a
S c0 -> S
b c1 --> b c1 … b
Замечание: Если размер списка не кратен степени двойки, то нужно учесть, что какие-то серии могут быть короче, чем ожидается.
На каждом шаге размер серий увеличивается вдвое.
Когда получим одну серию длиной во весь список, процесс сортировки завершен.
a 2 c0 --> a 4 c0 … a
S c0 -> S
b c1 --> b c1 … b
Замечание: Если размер списка не кратен степени двойки, то нужно учесть, что какие-то серии могут быть короче, чем ожидается.
Слайд 5
S К У Р А’ П О В А” Е’ Л
S К У Р А’ П О В А” Е’ Л
Е” Н А”’
a К Р П В Е’ Е” А”’
b У А’ О А” Л Н
a ←c0 К У О П Е’ Л А”’
b ←c1 А’ Р А” В Е” Н
a К Р П В Е’ Е” А”’
b У А’ О А” Л Н
a ←c0 К У О П Е’ Л А”’
b ←c1 А’ Р А” В Е” Н
Слайд 6
a ←c0 А’ К Р У Е’ Е” Л Н
b ←c1
a ←c0 А’ К Р У Е’ Е” Л Н
b ←c1
А” В О П А”’
a ←c0 А’ А” В К О П Р У
b ←c1 А”’ Е’ Е” Л Н
S←c0 А’ А” А”’ В Е’ Е” К Л Н О П Р У
a ←c0 А’ А” В К О П Р У
b ←c1 А”’ Е’ Е” Л Н
S←c0 А’ А” А”’ В Е’ Е” К Л Н О П Р У
Слайд 7
Алгоритм расщепления списка S
Расщепление (S, a, b, n)
n - количество
Алгоритм расщепления списка 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
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
S
a
b
k
p
Слайд 8
Метод прямого слияния (MergeSort)
Обозначение переменных:
n – количество элементов в списке S
Метод прямого слияния (MergeSort)
Обозначение переменных:
n – количество элементов в списке S
a, b – рабочие списки
c = (c0, c1) – массив из двух очередей p – предполагаемый размер серии
q – фактический размер серии в списке a
r – фактический размер серии в списке b
m – текущее количество элементов в списках a и b
i – номер активной очереди
c = (c0, c1) – массив из двух очередей p – предполагаемый размер серии
q – фактический размер серии в списке a
r – фактический размер серии в списке b
m – текущее количество элементов в списках a и b
i – номер активной очереди
Слайд 9
Метод прямого слияния (MergeSort)
< Расщепление (S, a, b, n) >
p :=
Метод прямого слияния (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
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
Трудоемкость метода MergeSort