Алгоритм сортировки слиянием

Хотя реализация слияния требует дополнительного пространства, идеи, лежащие в её основе, заслуживают внимания. Следует отметить, что всегда необходимы дополнительные:

1) временные затраты на копирование файла;

2) проверки на окончание хотя бы одного файла.

Рассмотрим один из подходов к выполнению двухпутевого слияния. Предположим, что в массиве RES размером n хранятся последовательно два отсортированных подмассива, содержащие соответственно m и p элементов (m+p=n)

Определение 1. Последовательность М, состоящая из n элементов, называется битонной последовательностью, если существует такое j, что

M1<=…<=Mj-1<=Mj>=Mj+1>=…>=Mn или M1>=…>=Mj-1>=Mj<=Mj+1<=…<=Mn

Сортировку слиянием удобно представить в виде слияния частей битонной последовательности. При двухпутевом слиянии оба отсортированных подмассива копируются в некий служебный массив WORK размера n. При этом первый подмассив копируется в прямом порядке (по возрастанию), а второй – в обратном (по убыванию). Таким образом, сразу за концом первого подмассива следует конец второго (т.е. в массиве WORK получена битонная последовательность). В листинге 1 представлена

реализация такого алгоритма двухпутевого слияния упорядоченных фрагментов массива RES размера n.

Функция MergeSort помещает результат слияния RES[left],…,RES[m] и RES[m+1],…,RES[right] в объединенный упорядоченный файл RES[left],…,RES[right]. В основу метода положена следующая идея: мы переставляем второй файл во время копирования в обратном порядке (без дополнительных затрат), так что связанный с ним указатель перемещается справа налево. Это приводит к тому, что наибольший элемент, в каком бы он файле не находился, служит служебной меткой для другого массива.

Дата добавления: 2015-08-17