|
Читайте также: |
Трехленточная сортировка последовательностей, представляет из себя простое прямое слияние последовательностей, для осуществления которого требуется три ленты. Суть метода состоит в следующем - исходная последовательность разбивается на две части, затем эти части сливаются, причем одиночные элементы образуют упорядочные пары. Полученная последовательность вновь разбивается на две части и сливаются, при этом упорядоченные пары образуют упорядоченные четверки. И так далее - четверки сливаются в восьмерки и т.п., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядоченна вся последовательность целиком.
Число пересылок: M = n * log n
Пример:
Исх. послед.: 44 55 12 42 94 13 05 67
1. 44 55 12 42
94 18 06 67
44 94 18 55 06 12 42 67
2. 44 94 18 55
06 12 42 67
06 12 44 94 18 42 55 67
3. 06 12 44 94
18 42 55 67
06 12 18 42 44 55 67 94
Сортировка естественным слиянием
Этот метод используется, когда последовательности частично упорядочены, эти упорядоченые последовательности называют сроками или сериями, поэтому при этой сортировке объединяются серии, а не последовательности фиксированной длинны. Каждый проход состоит из фазы распределения и фазы слияния. При разделении исходной последовательности на две подпоследовательности оптимальным вариантом будет тот, когда число серий в этих последовательностях одинаково; существенно неравномерное распределение серий в подпоследовательностях маловероятно, но может случиться, что в одной из подпоследовательностей серий на одну больше, тогда лишняя серия при проходе просто копируется.
Пример:
Имеем исходную последовательность (серии разделены ";") -
17 31; 05 59; 13 41 43 67; 11 23 29 47; 03 07 71; 02 19 57; 37 61
объединяем серии по две, одна последняя серия лишняя -
05 17 31 59; 11 13 23 29 41 46 47 67; 02 03 07 19 57 71; 37 61
05 11 13 17 23 29 31 41 43 47 59 67; 02 03 07 19 37 57 61 71
02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57 59 61 67 71
Многопутевая сортировка
Данный метод сортировки является модификацией метода естественного слияния. Временные затраты на любую сортировку последовательностей пропорциональны числу требуемых проходов, так как при каждом проходе копируются все данные. Чтобы уменьшить число этих проходов, серии распределяют на последовательности, число которых больше 2-х. Слияние Р серий, поровну распределены в М последовательностей, дает в результате Р/М серий. Второй проход уменьшить это число до Р/M¤, третий - до Р/M3 и т.д. Поэтому общие число проходов многопутевого слияния будет равно Log m K, где К - число элементов в последовательности. Итак, в этом методе, по сравнению с методом естественно слияния, добавляются М путей распределения и слияния последовательностей.
Дата добавления: 2014-12-15; просмотров: 107 | Поможем написать вашу работу | Нарушение авторских прав |