Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Первая версия программы сортировки с помощью простого слияния имеет следующий вид





 

  int i, j, k, 1;  
  int up , p;    
  up=l;      
  p=l;      
/* индексация индексов */
  do      
  {      
  if (up= = 1)  
  { i=l;    

j=n;

k=n+l;

l=2*n;

} else

{

k=l; l=n; i=n+l; j=2*n;

} /* слияние р-наборов из i- и j-входов в к- и 1-выходы */

up=-up;

р=2*р;

}

while(p==n);

Уточним действия, описанные на естественном языке. Ясно, что процесс слияния п элементов сам представляет собой последовательность слияний последовательностей, т. е. /^-наборов. После каждого такого частичного слияния выход переключается с нижнего на верхний конец выходного массива и наоборот, что гарантирует одинаковое распределение в обоих направлениях. Если сливаемые элементы направляются в левый конец выходного массива, то направление задается индексом к, и после пересылки очередного элемента он увеличивается на единицу. Если же элементы направляются в правый конец, то направление задается индексом / и он каждый раз уменьшается. Для упрощения фактического оператора слияния будем считать, что направление всегда задается индексом к, но после слияния /^-набора будем менять местами значения к и /, приращение же всегда обозначается через h, имеющее значение либо 1, либо -1. Высказанные соображения приводят к такому уточнению программы.

 

h=l;  
m=n;  
/*m — число сливаемых элементов*/
do  
{  
q=p;  
r=p;  
m=m-2*p;  

/^слияние q-элементов из i-входа с г элементами из j-входа; индекс выхода к, затем к увеличиваем на h*/

h=-h; /*обмен значениями к и 1*/

}

while(m==0);

Дальнейшее уточнение ведет уже к формулированию самого оператора слияния. При этом следует учитывать, что остаток подпоследовательности, оставшийся после слияния непустой подпоследовательности, добавляется простым копированием к выходной последовательности.




while {


( (q!=0) && (r!=0))


if (a[i]<a[j])

{ /* элемент из i-входа пересылается на k-выход; ink продвигаются*/

q=q-l;

}

else

{ /* элемент из j-входа посылается на k-выход; j и к продвигаются*/

г=г-1;

} }

/^копирование хвоста i-массива; копирование хвоста j-массива;*/

Если теперь уточнить операции копирования остатков, то программа станет совершенно точной. Однако, прежде чем сделать это, мы хотим избавиться от ограничения на п: пока оно должно быть степенью двойки. На какие части алгоритма влияло это условие? Легко убедить себя, что наилучший способ справиться с более общей ситуацией продолжать действовать, насколько это возможно, по-старому. В данной ситуации это означает, что мы будем продолжать слияние /^-наборов до тех пор, пока не останутся последовательности размером менее р. Этот процесс затрагивает только ту


часть, где определяются значения q и г — длины сливаемых последовательностей. Вместо трех операторов

q=p; г=р; т=т - 2*р; используется следующая конструкция:

iflm >=p)

q=p; else

q = m; т=т - q; if(m >=p)

r=p; else

r = m; m=m - r; . Здесь m — общее число элементов в двух входных последовательностях. Кроме того, для гарантии окончания программы условие р = 0, управляющее внешним циклом, заменяется на р>=п. Проделав все эти модификации, мы получаем следующую программу.

 

int i, j, k, 1, t;  
int h, m, p, q, r;  
int up;  
/*У массива а индексы 1, ..,2*n.*/
up=l;  
p=l;  
do  
{  
h=l;  
m=n;  
if (up==l)  
{  
i=l;  
j=n;  
k=n+l;  
l=2*n;  
}  
else  
{  
k=l;  

l=n; i=n+l; j=2*n; }

do {

/* слияние серий из i и j в к-

выход*/

/* q — длина серии из i, r — длина

серии из j */

if (m>=p)

q=p; else

q=m; m=m-q;

if (1>=P)

r=p; else

r=m; m=m-r;

while(q!=0 && r!=0)

{ /* слияние */

if (a[i]<a[j])

{

a[k]=a [i] ;

k=k+h;

i=i+l;

q=q-l; } else

{

a[k]=a[j]; k=k+h;

j=j-i;

r=r-l; } }

/* копирование остатка серии из j*/


while(r!=0) { а[к]=a[j]; k=k+h;  
j=j-i; r=r-l; }  
/* копирование остатка серии из i*/
while(q!=0) { a[k]=a [i] ; k=k+h; i=i+l;  
q=q-l; }  
h=-h; t=k; k=l; l=t;  
} while(m==0);  
up=-up; p=2*p;  
} while(p>=n);  
if (up==0) { for(i=l; i<n; i++) a[i]=a[i+n]; }  

Анализ алгоритма.Поскольку на каждом проходе р удваивается и сортировка заканчивается при р >= п, то всего требуется log n проходов. На каждом проходе по определению копируются по одному разу все п элементов. Поэтому общее число пересылок

М = n-\ogn.


Число сравнений ключей С даже меньше М, поскольку при копировании остатков никаких сравнений не производится. Однако, поскольку сортировки слиянием обычно употребляются в ситуациях, где приходится пользоваться внешними запоминающими устройствами, то затраты на операции пересылки на несколько порядков превышают затраты на сравнения. Поэтому детальный анализ числа сравнений особого практического интереса не представляет.

Алгоритм сортировки слиянием выдерживает сравнение даже с усовершенствованными методами сортировки. Однако, хотя здесь относительно высоки затраты на работу с индексами, решающее значение играет необходимость работать с памятью размером 2п. Поэтому сортировка слиянием для массивов, т. е. для данных, размещаемых в оперативной памяти, используется редко.



Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой




Дата добавления: 2014-11-29; Просмотров: 330; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.029 сек.