|
Сортировка слиянием - пример
использования принципа «разделяй и властвуй». Сначала задача
разбивается на несколько подзадач меньшего размера. Затем эти задачи
решаются с помощью рекурсивного вызова или непосредственно, если их
размер достаточно мал. Наконец, их решения комбинируются, и
получается решение исходной задачи.
Выглядят так:
1) Сортируемый массив разбивается на две половины
меньшего размера;
2) Каждая из получившихся половин сортируется
отдельно;
3) Два упорядоченных массива половинного размера
соединяются в один.
Нетривиальным этапом является соединение двух
упорядоченных массивов в один.
Основная идея решения состоит в
попарном сравнении очередных элементов каждого фрагмента, выяснении, какой
из элементов меньше, переносе его во вспомогательный массив temp (для
простоты) и продвижении по тому фрагменту массива, из которого взят
элемент. При этом следует не забыть записать в temp оставшуюся часть
того фрагмента, который не успел себя
"исчерпать". |
|  |
Параллельная реализация:
Алгоритм делит исходный массив на n частей по количеству
доступных приложению процессоров. Далее следует параллельная область, в которой
каждый поток выполняет сортировку слиянием независимо друг от друга. В
конце области обеспечивается синхронизация потоков – выполняется ожидание
завершения вычислений всех потоков; далее все потоки завершаются – дальнейшие
вычисления продолжает выполнять только основной поток. Им и выполняется слияние
n частей массива в один упорядоченный.
void MergeSort(int* mas, int l, int r)
{
if(l >= r)
return;
int m = (l + r) /
2;
MergeSort(mas, l, m);
MergeSort(mas, m+1, r);
MergeGlob(mas, l, r, m);
}
void MergeGlob(int* mas, int l, int r, int m)
{
if(l >= r || m <
l || m > r) return;
if(r == l + 1
&& mas[l] > mas[r])
{
int t = mas[l];
mas[l] = mas[r];
mas[r] = t;
return;
}
MergeLoc(mas, l, r, m);
}
void MergeLoc(int* mas, int l, int r, int m)
{
int* tmp = new int[r-l+2];
for (int i=0; i<=r-l; i++)
tmp[i] = mas[l+i];
tmp[r-l+1] = 0;
for(int i = l, j = 0, k = m - l + 1; i
<= r; i++)
{
if(j > m - l) mas[i]
= tmp[k++];
else if(k > r - l) mas[i] = tmp[j++];
else mas[i] = (tmp[j]
< tmp[k]) ? tmp[j++] : tmp[k++];
}
}
bool SortTest(int* mas, int n)
{
bool fl = true; //sort is true
for (int i=0; i<n-1; i++)
if (mas[i] >
mas[i+1]) fl = false;
return fl;
}
int _tmain(int argc, _TCHAR* argv[])
{
int n,p, time;
char exit;
char nlen =
'\n';
do
{
do
{
cout<<"input the size of data <
9<size<10000000 > : ";
cin>>n;
cout<<nlen;
}
while ((n < 10) ||
(n > 10000000));
int* masr =
new int[n];
int* mas = new int[n];
srand(clock());
for (int i=0; i<n; i++)
{
masr[i] = rand() % 1000;
mas[i] = masr[i];
//cout<<mas[i]<<nlen;
}
cout<<nlen;
//--------------------------------------------------------------------
cout<<"1 thread:";
cout<<nlen;
time = clock();
MergeSort(masr, 0, n - 1);
time = clock() - time;
cout<<"time: ";
cout<<time;
cout<<nlen;
cout<<"sort is ";
(SortTest(masr, n)) ? cout<<"true" : cout<<"false";
cout<<nlen; cout<<nlen;
//--------------------------------------------------------------------
p = omp_get_num_procs();
cout<<p;
cout<<" threads:";
cout<<nlen;
time = clock();
#pragma omp parallel
shared(mas) firstprivate(n, p)
{
#pragma omp
for schedule(dynamic)
for (int i=0; i<p; i++)
if (i < p-1)
MergeSort(mas, i*n/p, (i+1)*n/p - 1);
else
MergeSort(mas, i*n/p, n - 1);
}
for (int i=1; i<p; i++)
if (i < p-1)
MergeLoc(mas, 0, (i+1)*n/p - 1, i*n/p - 1);
else
MergeLoc(mas, 0, n - 1, i*n/p - 1);
time = clock() - time;
cout<<"time: ";
cout<<time;
cout<<nlen;
cout<<"sort is ";
(SortTest(masr, n)) ? cout<<"true" : cout<<"false";
cout<<nlen; cout<<nlen;
cout<<"repeat (y/n)? ";
cin>>exit;
delete []masr;
delete []mas;
}
while (exit ==
'y');
return 0;
}
