Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Сортировка с помощью дерева.
Построение дерева начинается с листьев, которые содержат все элементы массива. Из каждой соседней пары выбирается наименьший элемент, и эти элементы образуют следующий (ближе к корню уровень дерева). Из каждой соседней пары выбирается наименьший элемент и т.д., пока не будет построен корень, содержащий наименьший элемент массива. Массив: 8, 23, 5, 65, 44, 33, 1, 6 Первый шаг: Второй шаг: Третий шаг:
Четвертый шаг: Пятый шаг: Шестой шаг: Седьмой шаг: Восьмой шаг: Пирамидальная сортировка. Массив: 44, 55, 12, 42, 94, 18, 6, 67
обменяли 55 и 12, забыли про 55 просеяли 12 сквозь 44, 42 обменяли местами 44 и 12, забыли про 44 просеяли 12 сквозь 42 обменяли местами 42 и 6, забыли про 42 получили 6, 12, 18. Сортировка со слиянием. Два массива: 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
|
|||||
Последнее изменение этой страницы: 2020-12-09; просмотров: 44; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.129.45.92 (0.007 с.) |