![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сортировка со слиянием.
Два массива: 5, 8, 23, 65 1, 6, 34, 47 Записываем меньшее значение: 1 5, 8, 23, 65 1, 6, 34, 47 Записываем меньшее значение: 5 5, 8, 23, 65 1, 6, 34, 47 Записываем меньшее значение: 6 5, 8, 23, 65 1, 6, 34, 47 Записываем меньшее значение: 8 5, 8, 23, 65 1, 6, 34, 47 Записываем меньшее значение: 23 5, 8, 23, 65 1, 6, 34, 47 Записываем меньшее значение: 34 5, 8, 23, 65 1, 6, 34, 47 Записываем меньшее значение: 47 Осталось число 65. Внешняя сортировка прямым слиянием. Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения последовательно читается файл A, и записи a1, a3,..., a(n-1) пишутся в файл B, а записи a2, a4,..., an - в файл C (начальное распределение). Начальное слияние производится над парами (a1, a2), (a3, a4),..., (a(n-1), an), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее.
Массив: 23, 8, 5, 65, 47, 34, 1, 6 Шаг 1: файл В 23, 5, 47, 1 файл С 8, 65, 34, 6 Файл А: 8, 23, 5, 65, 34, 47, 1, 6 Шаг 2: файл В 8, 23, 34, 47 файл С 5, 65, 1, 6 Файл А: 5, 8, 23, 65, 1, 34, 6, 47 Шаг 3: файл В 5, 8, 23, 65 файл С 1, 34, 6, 47 Файл А: 1, 5, 8, 34, 6, 23, 47, 65 Шаг 4: файл В 1, 5, 8, 34 файл С 6, 23, 47, 65 Файл А: 1, 5, 6, 8, 23, 34, 47, 65
Естественное слияние. Алгоритм слияния можно использовать и для сортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого: 1. в исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии) 2. эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше 3. шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора 4. шаги 1 –3 применяются к новому полученному набору, т.е. выделяются пары серий, которые сливаются в еще более длинные наборы, и.т.д. до тех пор, пока не будет получена единая упорядоченная последовательность. Массив: 24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40 Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их: (24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40) (24) + (08, 13, 17) = (08, 13, 17, 24) (06, 19, 20) + (11) = (06, 11, 19, 20) (07, 55) + (33) = (07, 33, 55) (22) + (18) = (18, 22) Новый набор чисел: 08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40 Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось): (08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40) (08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24) (07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55) Новый набор: 06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40 Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их: (06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40) (06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55) Новый набор и его две серии: (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40) Этап 4. После слияния этих двух серий получим полностью упорядоченный набор: 02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55 Сбалансированное многолучевое слияние. Массивы: 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 3 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 5 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 5 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 6 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 7 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 9 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 23 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 30 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 33 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 44 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45 Записываем меньшее: 45 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45
ПРИЛОЖЕНИЕ 1
|