Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Помогите слепить в кучу!!!

14K
13 мая 2006 года
Morpheus
8 / / 08.04.2006
2.2.4. Слияние списков
Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А=<6,17,23,39,47> и В=<19,25,38,60> из 5 и 4 элементов дает в качестве результата список С=<6,17,19,23,25,38,39,47,60> из 9 элементов.
Для слияния списков А и В список С сначала полагается пустым, а затем к нему последовательно приписывается первый узел из А или В, оказавшийся меньшим и отсутствующий в С.
Составим функцию для слияния двух упорядоченных, расположенных рядом частей массива s. Параметром этой функции будет исходный массив s с выделенными в нем двумя расположенными рядом упорядоченными подмассивами: первый с индекса low до индекса low+l, второй с индекса low+l+1 до индекса up, где переменные low, l, up указывают месторасположения подмассивов. Функция merge осуществляет слияние этих подмассивов, образуя на их месте упорядоченный массив с индексами от low до up (см. рис.28).
/* слияние списков */
double *merge(double *s, int low, int up, int l)
{
double *b,*c,v;
int i,j,k;
b=calloc(l,sizeof(double));
c=calloc(up+1-l,sizeof(double));
for(i=low;i<low+l;i++)
b[i-low]=s;
for(i=0;i<up-l;i++)
c=s[i+l+low];
v=(b[l]=(c[up-l]=(s[low+l-1]>s[up-1]) ? (s[low+l-1]+1) : (s[up-1]+1)));
i=(j=0);
k=low;
while(b<v||c[j]<v)
{ if(b<c[j]) s[k]=b[i++];
else s[k]=c[j++];
k++;
}
return (s);
}

Рис.28. Схема движения индексов при слиянии списков.
2.2.5. Сортировка списков путем слияния
Для получения упорядоченного списка B' последовательность значений В=<K1,K2,...,Kn> разделяют на N списков В1=<K1>, B2=<K2>,...,Bn=<Kn>, длина каждого из которых 1. Затем осуществляется функция прохода, при которой М>=2 упорядоченных списков B1,B2,...,Bm заменяется на М/2 (или (М+1)/2) упорядоченных списков, B(2i-1)-oго и B(2i)-ого ( 2i<=M ) и добавлением Вm при нечетном М. Проход повторяется до тех пор пока не получится одна последовательность длины N.
Приведем пример сортировки списка путем использования слияния, отделяя последовательности косой чертой, а элементы запятой.
Пример:
9 / 7 / 18 / 3 / 52 / 4 / 6 / 8 / 5 / 13 / 42 / 30 / 35 / 26;
7,9 / 3,18 / 4 / 52 / 6 / 8 / 54 / 13 / 30 / 42 / 26 / 35;
3,7,9,18 / 4,6,8,52 / 5,13,30,42 / 26,35;
3,4,6,7,8,9,18,52 / 5,13,26,30,35,42;
3,4,5,6,7,8,9,13,18,26,30,35,42,52.
Количество действий, требуемое для сортировки слиянием, равно Q=N*log2(N), так как за один проход выполняется N сравнений, а всего необходимо осуществить log2(N) проходов. Сортировка слиянием является очень эффективной и часто применяется для больших N, даже при использовании внешней памяти.
Функция smerge упорядочивает массив s сортировкой слиянием, используя описанную ранее функцию merge.
/* сортировка слиянием */
double *smerge (double *s, int m, int n)
{ int l,low,up;
double *merge (double *, int, int, int);
l=1;
while(l<=(n-m))
{ low=m;
up=m-1;
while (l+up < n)
{ up=(low+2*l-1 < n) ? (low+2*l-1) : n ;
merge (s,low,up,l);
low=up-1;
}
l*=2;
}
return(a);
}
Для сортировки массива путем слияния удобно использовать рекурсию. Составим рекурсивную функцию srecmg для сортировки массива либо его части. При каждом вызове сортируемый массив делится на две равных части, каждая из которых сортируется отдельно, а затем происходит их слияние, как это показано на рис.29.

Рис.29. Схема сортировки слиянием.
/* рекурсивная сортировка слиянием 1/2 */
double *srecmg (double *a, int m, int n)
{ double * merge (double *, int, int, int);
double * smerge (double *, int, int);
int i;
if (n>m)
{ i=(n+m)/2;
srecmg(a,m,i);
srecmg(a,i+1,n);
merge(a,m,n,(n-m)/2+1);
}
return (a);
}
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог