Impossible?
No.
WARNING!!! Some comments in Ukranian!
#define MAX_LOADSTRING 100
using namespace std;
typedef tuple <int,int,int> param_t; // offs,step,n
//array to sort
//const int N = 20000;
int *arr;
int *arr2;
int n;
// Global Variables:
HINSTANCE hInst; // current instance
TCHAR szTitle[MAX_LOADSTRING]; // The title bar text
TCHAR szWindowClass[MAX_LOADSTRING]; // the main window class name
HWND hWnd; //хендл головного вікна
HWND hDlgWindow; //хендл діалогового вікна
int threadsCnt; //кількість потоків
vector<HANDLE> threads; //хендли для потоків
clock_t curtime; //змінна для часу
// Forward declarations of functions included in this code module:
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK Sort(HWND, UINT, WPARAM, LPARAM );
void arayOutput() //вивід масиву до файлу
{
fstream outputfile; //
outputfile.open("array.txt", ios::out);
for (int i=0;i<n;i++)
outputfile<<arr[i]<<endl;
outputfile.close();
}
void heapify(int pos, int n) //просіювання елементів масиву
{
int iLeft = 2 * pos + 1; //координати лівого потомка
if (iLeft < n)
{
int iRight = iLeft+1; //координата правого потомка
int t = iRight < n && arr[iRight] >= arr[iLeft] ? iRight : iLeft; //вибір більшого з потомків, якщо такі є
if (arr[pos] < arr[t])
{
swap(arr[pos], arr[t]); //заміна більшого потомка з батьком, якщо потрібна
heapify(t, n); //просіювання відповідної гілки
}
}
}
void heap_make(int n) //прохід по дереву для просіювання
{
for (int i = n / 2; i >= 0; --i )
heapify(i, n);
}
void heap_sort(int n) //звичайне сортування
{
heap_make(n); //побудова сортуючого дерева
while (n>0) //сортування
{
swap(arr[0], arr[n - 1]);
n--;
heapify(0, n);
}
}
void heapify_thr(int pos, int n, int thr) //паралельне просіювання
{
int left = pos*2+1; //обчислення координат потомків
int right = left + 1;
if (left <n ) heapify_thr(left, n, thr); //рекурсивний обхід дерева
if (right <n ) heapify_thr(right, n, thr);
if (left < n)
{
int t = right < n && arr[right] >= arr[left] //обчислення більшого потомка
? right : left;
if (arr[pos] < arr[t]) //заміна з батьком, якщо потрібно
{
swap(arr[pos], arr[t]);
heapify_thr(t, n, thr); //подальше просіювання
}
}
}
void start_heapify(param_t * params) //процедура для роботи потоків
{
int offs = get<0>(*params); //зчитування параметрів - номер вершини, кількість елементів, номер потока
int step = get<1>(*params);
int n = get<2>(*params);
heapify_thr(offs,n,offs); //початок просіювання
}
void heap_make_mt(int n, int threadsCnt) //створення сортуючого дерева паралельно у 2-х потоках
{
for (int i = threadsCnt; i--;) { //створення потоків
threads.push_back(CreateThread(0, 0, (LPTHREAD_START_ROUTINE)start_heapify, new param_t(i+1,threadsCnt,n), 0, 0));
}
WaitForMultipleObjects(threadsCnt, &threads[0], true, INFINITE); //очікування завершення роботи потоків
heapify(0, n); //просіювання верхнього елемента
}
void heap_sort_mt(int n, int threads) //паралельне сортування
{
heap_make_mt(n, threads); //створення сортуючого дерева
while (n>0) //остаточне сортування
{
swap(arr[0], arr[n - 1]);
n--;
heapify(0, n);
}
}
int APIENTRY _tWinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPTSTR lpCmdLine,
int nCmdShow)
{
UNREFERENCED_PARAMETER(hPrevInstance);
UNREFERENCED_PARAMETER(lpCmdLine);
// TODO: Place code here.
MSG msg;
HACCEL hAccelTable;
srand( 1);
threadsCnt = 2; //кількість потоків для паралельного сортування
// Initialize global strings
LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadString(hInstance, IDC_LAB5_SORT, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);
// Perform application initialization:
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_LAB5_SORT));
// Main message loop:
while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
return (int) msg.wParam;
}
//
// FUNCTION: MyRegisterClass()
//
// PURPOSE: Registers the window class.
//
// COMMENTS:
//
// This function and its usage are only necessary if you want this code
// to be compatible with Win32 systems prior to the 'RegisterClassEx'
// function that was added to Windows 95. It is important to call this function
// so that the application will get 'well formed' small icons associated
// with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_LAB5_SORT));
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = MAKEINTRESOURCE(IDC_LAB5_SORT);
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));
return RegisterClassEx(&wcex);
}
//
// FUNCTION: InitInstance(HINSTANCE, int)
//
// PURPOSE: Saves instance handle and creates main window
//
// COMMENTS:
//
// In this function, we save the instance handle in a global variable and
// create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
hInst = hInstance; // Store instance handle in our global variable
hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
if (!hWnd)
{
return FALSE;
}
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
return TRUE;
}
//
// FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
// PURPOSE: Processes messages for the main window.
//
// WM_COMMAND - process the application menu
// WM_PAINT - Paint the main window
// WM_DESTROY - post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
PAINTSTRUCT ps;
HDC hdc;
switch (message) //обробка повідомлень головного вікна
{
case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
// Parse the menu selections:
switch (wmId)
{
case ID_FILE_32771:
hDlgWindow = CreateDialog(hInst, MAKEINTRESOURCE(IDD_DIALOG1), hWnd, Sort); //створення діалогового вікна при натисненні "Старт"
break;
case ID_FILE_32772: //створення діалогового вікна при натисненні "Про програму"
DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
break;
break;
case IDM_EXIT:
DestroyWindow(hWnd);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
break;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
// TODO: Add any drawing code here...
EndPaint(hWnd, &ps);
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
//Обробка повідомлень діалогового вікна сортування
INT_PTR CALLBACK Sort(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
int inum, length;
wchar_t buf[20];
HWND hedit1; //текстове поле для кількості елементів
HWND hedit2; //текстове поле для часу
UNREFERENCED_PARAMETER(lParam);
switch (message)
{
case WM_INITDIALOG:
return (INT_PTR)TRUE;
case WM_COMMAND:
{
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
switch (wmId)
{
case IDC_BUTTON1: //натиснено "Почати"
length=10;
hedit1 = GetDlgItem(hDlgWindow,IDC_EDIT1);
hedit2 = GetDlgItem(hDlgWindow,IDC_EDIT2);
SendMessage(hedit1,WM_GETTEXT, length, (LPARAM)buf); //зчитування кількості елементів масиву
if (length == 0) MessageBox(hDlgWindow,TEXT("Enter array size"),TEXT("error"),MB_OK);
else
{
inum = _wtoi(buf);
if (inum == 0) MessageBox(hDlgWindow,TEXT("Enter array size"),TEXT("error"),MB_OK);
else
{
n = inum;
arr = new int[n]; //створення масив, що буде сортуватися
//sort
//checkbuttons
if(IsDlgButtonChecked(hDlgWindow, IDC_RADIO1)) //вибраний метод звичайного сортування
{
for (int i = 0; i < n; i++) //заповнення масиву випадковою послідовністю
{
arr[i] = rand() % 1000;
}
curtime = clock(); //початковий час
heap_sort(n); //сортування
float diff = ((float)clock()-(float)curtime) / CLK_TCK; //кінцевий час
const size_t len = 10;
wchar_t sBuffer[len];
_snwprintf(sBuffer, len-1, L"%f", diff);
BOOL b_Ret = SetWindowTextW(hedit2, sBuffer); //виведення часу, що затрачено на сортування
arayOutput(); //вивід масиву до файлу
}
else
{
if (IsDlgButtonChecked(hDlgWindow, IDC_RADIO2)) //обрано паралельне сортування
{
for (int i = 0; i < n; i++) //заповнення масиву випадковою послідовністю
{
arr[i] = rand() % 1000;
}
curtime = clock();
heap_sort_mt(n, threadsCnt); //сортування
float diff = ((float)clock()-(float)curtime) / CLK_TCK; //облік часу
const size_t len = 10;
wchar_t sBuffer[len];
_snwprintf(sBuffer, len-1, L"%f", diff);
BOOL b_Ret = SetWindowTextW(hedit2, sBuffer); //вивід часу
arayOutput(); //вивід масиву до файла
}
else MessageBox(NULL, TEXT("check sorting method"), TEXT("error"),MB_OK);
}
delete arr; //висвободження пам'яті масива
}
}
//MessageBox(hWnd,TEXT("Start button pushed"),TEXT("ok"),MB_OK);
break;
case IDC_BUTTON2:
MessageBox(hWnd,TEXT("Stop button pushed"),TEXT("ok"),MB_OK);
break;
}
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return (INT_PTR)TRUE;
}
}
}
return (INT_PTR)FALSE;
}
// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
UNREFERENCED_PARAMETER(lParam);
switch (message)
{
case WM_INITDIALOG:
return (INT_PTR)TRUE;
case WM_COMMAND:
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return (INT_PTR)TRUE;
}
break;
}
return (INT_PTR)FALSE;
}
