![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сортировка слиянием
Сортировка слиянием является процессом объединения двух или более упорядоченных наборов данных в один упорядоченный набор данных. В процессе сортировки поочередно сравниваются ключи в парах записей из исходных наборов данных так, что записи с меньшими ключами помещаются в результирующий набор данных. После того как один набор данных окажется исчерпанным, все оставшиеся элементы другого пересылаются в результирующий набор без изменения порядка следования. Структурограмма алгоритма сортировки слиянием в массив C(N+M) двух упорядоченных массивов A(N) и B(M) имеет вид.
Пример 1. На примере (заставка с пересылкой из А в С оставшихся). Характеристики метода. 1. Количество просмотров - не более Log2 N. 2. Число операций сравнения зависит от количества записей наиболее короткого исходного набора, а также от конкретных значений ключей элементов исходных массивов. 3. Требуется дополнительная память для хранения вспомогатель- ного набора данных, в котором могут храниться объединенные файлы.
Данный метод можно использовать для сортировки одного набора данных. Для этого набор данных разделяется на N частей размером в один элемент, и объединяются соседние (необъединенные) пары элементов. В результате образуются примерно N/2 частей размером в два эле- мента. Этот процесс продолжается, пока не останется только одна последовательность размером N. Ниже показано, как выполняется этот процесс на последова- тельности примера. Каждая отдельная часть на рисунке заключена в скобки.
Исходный файл: [25] [57] [48] [37] [12] [92] [86] [33]
Просмотр 1 [25 57] [37 48] [12 92] [33 86]
Просмотр 2 [25 37 48 57] [12 33 86 92]
Просмотр 3 [12 25 33 37 48 57 86 92]
|