Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Восходящая сортировка слиянием

Читайте также:
  1. Агентское задание СОРТИРОВКА ПОСЫЛОК.
  2. Алгоритм сортировки слиянием
  3. Выкопка и сортировка посадочного материала
  4. ГЛАВА 30 СОРТИРОВКА КРУГЛЫХ ЛЕСОМАТЕРИАЛОВ
  5. ГЛАВА 50 СОРТИРОВКА ПИЛОМАТЕРИАЛОВ
  6. Преимущества и недостатки стратегического альянса как организационной формы интеграции в сравнении со слиянием и поглощением

Восходящая сортировка слиянием состоит из последовательности проходов по всему файлу с выполнением слияний вида m -c- m, при этом m на каждом проходе удваивается, так что в заключение производится слияния типа m -c- x для некоторого x, меньшего или равного m.

Нерекурсивный вариант сортировки слиянием в приведенном шаблоне функции получается следующим образом: все элементы файла рассматриваются как упорядоченные подсписки длиной 1. Затем мы рассматриваем этот список, выполняя слияния вида 1-с-1, что дает


упорядоченные подсписки размером 2, затем мы просматриваем полученный список, выполняя при этом слияния вида 2-с-2, что даст упорядоченный подсписок размером 8, и так до тех пор, пока весь список не станет упорядоченным. Завершающий подсписок не всегда может оказаться того же размера, что и все другие, если размер файла не является степенью 2, тем не менее, можно слить и его.

int min(int A,int B)

{return (A<B)?A:B;

}

//Листинг 3 Восходящая сортировка слиянием

template<typename T>

void MergeSortUp(T* a,int left,int right)

{

for(int m=1;m<=right-1;m=m+m)

for(int i=left;i<=right-m;i+=m+m)

{

MergeSort(a,i,i+m-1,min(i+m+m-1,right));

}

}

 


Дата добавления: 2015-08-17; просмотров: 130 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Усовершенствования базового алгоритма| Облегченная кладки. Кладка из искусственных и природных камней.

mybiblioteka.su - 2015-2024 год. (0.007 сек.)