Вот моя версия сортировки слиянием, но она работает неправильно((
Проблема явно в синхронизации, но как ее реализовать с минимальным ущербом скорости выполнения?...
#include "stdafx.h"
#include <fstream>
#include <iostream>
#include <conio.h>
#include <time.h>
#include <process.h>
#include <windows.h>
using namespace std;
int* a;
clock_t t1,t2;
unsigned thrid1,thrid2;
struct data
{
int s,f;
};
void sliv(int s, int spl, int f)
{
int* b = new int[f-s+1];
int i=s,j=spl+1,k=0;
while ((i<=spl)&&(j<=f))
{
if (a[i]>a[j]) { b[k]=a[j]; j++;}
else { b[k]=a[i]; i++;}
k++;
}
for(;i<spl+1;i++) { b[k]=a[i]; k++;}
for(;j<f+1; j++) { b[k]=a[j]; k++;}
k=0;
for(i=s;i<f+1;i++){ a[i]=b[k]; k++;}
delete [] b;
}
void sortST(int s, int f)
{
if (s>=f) return;
int spl = (s+f)/2;
sortST(s,spl);
sortST(spl+1,f);
sliv(s,spl,f);
}
unsigned _stdcall sortDT(void* args)
{
data buf = *((data*)(args));
if (buf.s>=buf.f) return 0;
int spl = (buf.s+buf.f)/2;
sortST(buf.s,spl);
sortST(spl+1,buf.f);
sliv(buf.s,spl,buf.f);
return 0;
}
void main()
{
a = (int*)malloc(sizeof( int )) ;
int i,n,showproc=1;
start:
HANDLE thread[2];
cout<<"—Ёб«® н«Ґ¬Ґв®ў ¬ ббЁў : ";
cin>>n;
if ((cin.fail())||(n<1)) {delete [] a; return;}
a = (int*)realloc(a, n * sizeof(int));
srand((unsigned)time( NULL ));
// з «® ¤ўгеЇ®в®з®Ј® б®авЁа®ў®з®Ј® Їа®жҐбб
cout<<"\n\n„ўгеЇ®в®з п б®авЁа®ўЄ ...\n";
data args;
args.s = 0;
args.f = n/2;
for(i=0;i<n;i++) a[i]=rand();
if (showproc)
{
cout<<"€бе®¤л© ¬ ббЁў: \n";
for(i=0;i<n;i++)
cout<<a[i]<<" ";
}
t1 = clock();
thread[0] = (HANDLE)_beginthreadex(NULL, 0, sortDT, (void*)&args, 0, &thrid1);
args.s = n/2+1;
args.f = n-1;
thread[1] = (HANDLE)_beginthreadex(NULL, 0, sortDT, (void*)&args, 0, &thrid2);
WaitForMultipleObjects(2,thread,TRUE,INFINITE);
//CloseHandle(thread[1]);
//CloseHandle(thread[2]);
sliv(0,n/2,n-1);
t2 = clock();
if (showproc)
{
cout<<"\nђҐ§г«мв в:\n";
for(i=0;i<n;i++)
cout<<a[i]<<" ";
}
cout<<endl<<"‚аҐ¬п ўлЇ®«ҐЁп: "<<t2-t1<<" ¬б.\n\n";
cout<<endl<<"_______________________________________________________________________________"<<endl;
goto start;
}
Примечание:
Вот в нормальной кодировке:
<pre>
#include "stdafx.h"
#include <fstream>
#include <iostream>
#include <conio.h>
#include <time.h>
#include <process.h>
#include <windows.h>
using namespace std;
int* a;
clock_t t1,t2;
unsigned thrid1,thrid2;
struct data
{
int s,f;
};
void sliv(int s, int spl, int f)
{
int* b = new int[f-s+1];
int i=s,j=spl+1,k=0;
while ((i<=spl)&&(j<=f))
{
if (a[i]>a[j]) { b[k]=a[j]; j++;}
else { b[k]=a[i]; i++;}
k++;
}
for(;i<spl+1;i++) { b[k]=a[i]; k++;}
for(;j<f+1; j++) { b[k]=a[j]; k++;}
k=0;
for(i=s;i<f+1;i++){ a[i]=b[k]; k++;}
delete [] b;
}
void sortST(int s, int f)
{
if (s>=f) return;
int spl = (s+f)/2;
sortST(s,spl);
sortST(spl+1,f);
sliv(s,spl,f);
}
unsigned _stdcall sortDT(void* args)
{
data buf = *((data*)(args));
if (buf.s>=buf.f) return 0;
int spl = (buf.s+buf.f)/2;
sortST(buf.s,spl);
sortST(spl+1,buf.f);
sliv(buf.s,spl,buf.f);
return 0;
}
void main()
{
a = (int*)malloc(sizeof( int )) ;
int i,n,showproc=1;
start:
HANDLE thread[2];
cout<<"Число элементов массива : ";
cin>>n;
if ((cin.fail())||(n<1)) {delete [] a; return;}
a = (int*)realloc(a, n * sizeof(int));
srand((unsigned)time( NULL ));
// начало двухпоточного сортировочного процесса
cout<<"\n\nДвухпоточная сортировка...\n";
data args;
args.s = 0;
args.f = n/2;
for(i=0;i<n;i++) a[i]=rand();
if (showproc)
{
cout<<"Исходный массив: \n";
for(i=0;i<n;i++)
cout<<a[i]<<" ";
}
t1 = clock();
thread[0] = (HANDLE)_beginthreadex(NULL, 0, sortDT, (void*)&args, 0, &thrid1);
args.s = n/2+1;
args.f = n-1;
thread[1] = (HANDLE)_beginthreadex(NULL, 0, sortDT, (void*)&args, 0, &thrid2);
WaitForMultipleObjects(2,thread,TRUE,INFINITE);
//CloseHandle(thread[1]);
//CloseHandle(thread[2]);
sliv(0,n/2,n-1);
t2 = clock();
if (showproc)
{
cout<<"\nРезультат:\n";
for(i=0;i<n;i++)
cout<<a[i]<<" ";
}
cout<<endl<<"Время выполнения: "<<t2-t1<<" мс.\n\n";
cout<<endl<<"_______________________________________________________________________________"<<endl;
goto start;
}
<\pre>