Сортировка слиянием
Сортировка слиянием Сортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его несколько по-другому, нежели quickSort. А именно, вместо разделения по опорному элементу массив просто делится пополам.
template<class T>
void mergeSort(T a[], long lb, long ub) {
long split; // индекс, по которому делим массив
if (lb < ub) { // если есть более 1 элемента
split = (lb + ub)/2;
mergeSort(a, lb, split); // сортировать левую половину
mergeSort(a, split+1, last);// сортировать правую половину
merge(a, lb, split, ub); // слить результаты в общий массив
}
}
void merge(T a[], long lb, long split, long ub) {
// Слияние упорядоченных частей массива в буфер temp
// с дальнейшим переносом содержимого temp в a[lb]...a[ub]
// текущая позиция чтения из первой последовательности a[lb]...a[split]
long pos1=lb;
// текущая позиция чтения из второй последовательности a[split+1]...a[ub]
long pos2=split+1;
// текущая позиция записи в temp
long pos3=0;
T *temp = new T[ub-lb+1];
// идет слияние, пока есть хоть один элемент в каждой последовательности
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] < a[pos2])
temp[pos3++] = a[pos1++];
else
temp[pos3++] = a[pos2++];
}
// одна последовательность закончилась -
// копировать остаток другой в конец буфера
while (pos2 <= ub) // пока вторая последовательность непуста
temp[pos3++] = a[pos2++];
while (pos1 <= split) // пока первая последовательность непуста
temp[pos3++] = a[pos1++];
// скопировать буфер temp в a[lb]...a[ub]
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];
delete temp[ub-lb+1];
}
Оценим быстродействие алгоритма: время работы определяется рекурсивной формулой T(n) = 2T(n/2) + Theta(n).
Ее решение: T(n) = n log n - результат весьма неплох, учитывая отсутствие "худшего случая". Однако, несмотря на хорошее общее быстродействие, у сортировки слиянием есть и серьезный минус: она требует Theta(n) памяти.
Хорошо запрограммированная внутренняя сортировка слиянием работает немного быстрее пирамидальной, но медленнее быстрой, при этом требуя много памяти под буфер. Поэтому mergeSort используют для упорядочения массивов, лишь если требуется устойчивость метода(которой нет ни у быстрой, ни у пирамидальной сортировок).
Сортировка слиянием является одним из наиболее эффективных методов для односвязных списков и файлов, когда есть лишь последовательный доступ к элементам.
http://algolist.manual.ru
Отправить комментарий