Последние записи

made in programmersforum 10

Интенсив по Python: Работа с API и фреймворками 24-26 ИЮНЯ 2022. Знаете Python, но хотите расширить свои навыки?
Slurm подготовили для вас особенный продукт! Оставить заявку по ссылке - https://slurm.club/3MeqNEk

Online-курс Java с оплатой после трудоустройства. Каждый выпускник получает предложение о работе
И зарплату на 30% выше ожидаемой, подробнее на сайте академии, ссылка - ttps://clck.ru/fCrQw

27th
Авг

Внешняя многофазовая сортировка слиянием

Posted by maloy under Delphi, Архив

maLoy*508

Нужно описание этого метода сортировки чисел…

alexBlack

Д.Кнут 3 том. стр. 294

По простому. Сбалансированное двухпутевое слияние. Отсортированные серии делим на два файла:

[0-1][2-3][4-5]
[1-2][3-4]

Слиянием этих файлов получаем 3-й

из [0-1],[1-2] — [a-b]
из [2-3],[3-4] — [b-c]
[4-5] просто копируем [4-5]
получили [a-b][b-c][4-5]

Этот файл снова делим на два файла

[a-b][4-5]
[b-c]

и мы опять на шаге 1, но серий стало меньше. Когда останется одна серия, сортировка закончена.

Многофазная сортировка — одно небольшое изменение. Третий файл делим на два по-другому. Половину оставляем в этом файле, вторую половину копируем. Снова получаем два файла (3, 1) 2-й используем для слияния. Поэтому многофазная — файлы меняются местами.

Остальное описание — многопутевая сортировка и тонкости выбора серий. С учетом этого описания перечитайте еще раз главы Кнута. Надеюсь станет понятно.

тема на форуме от 2008 года