multi-threaded sorting program

closed account (zwA4jE8b)
Hey guys, whats up?

I made a program for school that uses 5 different sorting methods and outputs the results. I thought it would be fun to see if a multi-threaded sort program would be faster. Turn out it is. So far I am getting ~.5 second faster on MT.

The sorts sort a double[10000]; each array is identical.

The following code is most of my program, for lengths sake I left off the sorting functions, they work.

My question... Is this program well written?

I am new to multi-threading so I am guessing this is probably sloppy code. But this is practice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 
//Michael Ervin - Multi-Threaded sorting

#include <iostream>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <Windows.h>
#include <process.h>

using namespace std;

const int MAXARRAY = 10000;
double *staticarr;
ofstream fout("output.txt");
CRITICAL_SECTION sync;

unsigned __stdcall thread1( void *arg );
unsigned __stdcall thread2( void *arg );
unsigned __stdcall thread3( void *arg );
unsigned __stdcall thread4( void *arg );
unsigned __stdcall thread5( void *arg );

void bubblesort(double[], int);
void selectsort(double[], int);
void insertionsort(double[], int);
void quicksort(double [], int, int);
void shellsort(double temp[], int n);

void input(double[]);
void initarr(double[], double[]);
void print(double[], ofstream&, double);
void swaparr(double&, double&);

int main()
{
	clock_t tstart, tend;
	HANDLE hs[5];
	unsigned th1, th2, th3, th4, th5;
	fout << fixed << setprecision(3);
	InitializeCriticalSection(&sync);

	staticarr = new double[MAXARRAY];
	input(staticarr);

	cout << "Sorting data using five methods.\n" <<
			"1) Bubble Sort.\n" <<
			"2) Select Sort.\n" <<
			"3) Insertion Sort.\n" <<
			"4) Quick Sort.\n" <<
			"5) Shell Sort." <<endl;

	fout << "Starting multi-threaded sorting>>>>>" << endl << endl;
	tstart = clock();

		hs[0] = (HANDLE)_beginthreadex(NULL, 0, thread1, NULL, CREATE_SUSPENDED, &th1);
		hs[1] = (HANDLE)_beginthreadex(NULL, 0, thread2, NULL, CREATE_SUSPENDED, &th2);
		hs[2] = (HANDLE)_beginthreadex(NULL, 0, thread3, NULL, CREATE_SUSPENDED, &th3);
		hs[3] = (HANDLE)_beginthreadex(NULL, 0, thread4, NULL, CREATE_SUSPENDED, &th4);
		hs[4] = (HANDLE)_beginthreadex(NULL, 0, thread5, NULL, CREATE_SUSPENDED, &th5);

		ResumeThread(hs[0]);
		ResumeThread(hs[1]);
		ResumeThread(hs[2]);
		ResumeThread(hs[3]);
		ResumeThread(hs[4]);

		WaitForMultipleObjects(5, hs, true, INFINITE);

	
	tend = clock();
	fout << endl << "Total processing time: " << ((tend - tstart) / (double)CLOCKS_PER_SEC);
	fout.close();
	cin.get();
	
	return 0;
}

unsigned __stdcall thread1( void *arg )
{
	clock_t start, end;
	double timediff;
	double* x1 = new double[MAXARRAY];
	
	EnterCriticalSection(&sync);
	initarr(staticarr, x1);
	LeaveCriticalSection(&sync);
	
	start = clock();
	bubblesort(x1, MAXARRAY);
	end = clock();
	timediff = (end - start)/(double)CLOCKS_PER_SEC;
	
	EnterCriticalSection(&sync);
	fout << "Bubble Sort   N = " << MAXARRAY << endl;
	print(x1, fout, timediff);
	LeaveCriticalSection(&sync);

	return 3;
}
unsigned __stdcall thread2( void *arg )
{
	clock_t start, end;
	double timediff;
	double* x2 = new double[MAXARRAY];
	
	EnterCriticalSection(&sync);
	initarr(staticarr, x2);
	LeaveCriticalSection(&sync);
	
	start = clock();
	selectsort(x2, MAXARRAY);
	end = clock();
	timediff = (end - start)/(double)CLOCKS_PER_SEC;
	
	EnterCriticalSection(&sync);
	fout << "Select Sort   N = " << MAXARRAY << endl;
	print(x2, fout, timediff);
	LeaveCriticalSection(&sync);

	return 3;
}
unsigned __stdcall thread3( void *arg )
{
	clock_t start, end;
	double timediff;
	double* x3 = new double[MAXARRAY];
	
	EnterCriticalSection(&sync);
	initarr(staticarr, x3);
	LeaveCriticalSection(&sync);
	
	start = clock();
	insertionsort(x3, MAXARRAY);
	end = clock();
	timediff = (end - start)/(double)CLOCKS_PER_SEC;
	
	EnterCriticalSection(&sync);
	fout << "Insertion Sort   N = " << MAXARRAY << endl;
	print(x3, fout, timediff);
	LeaveCriticalSection(&sync);

	return 3;
}
unsigned __stdcall thread4( void *arg )
{
	clock_t start, end;
	double timediff;
	double* x4 = new double[MAXARRAY];
	
	EnterCriticalSection(&sync);
	initarr(staticarr, x4);
	LeaveCriticalSection(&sync);
	
	start = clock();
	quicksort(x4,0, MAXARRAY - 1);
	end = clock();
	timediff = (end - start)/(double)CLOCKS_PER_SEC;
	
	EnterCriticalSection(&sync);
	fout << "Quick Sort   N = " << MAXARRAY << endl;
	print(x4, fout, timediff);
	LeaveCriticalSection(&sync);

	return 3;
}
unsigned __stdcall thread5( void *arg )
{
	clock_t start, end;
	double timediff;
	double* x5 = new double[MAXARRAY];
	
	[code]EnterCriticalSection(&sync);
	initarr(staticarr, x5);
	LeaveCriticalSection(&sync);
	
	start = clock();
	shellsort(x5, MAXARRAY);
	end = clock();
	timediff = (end - start)/(double)CLOCKS_PER_SEC;
	
	EnterCriticalSection(&sync);
	fout << "Shell Sort   N = " << MAXARRAY << endl;
	print(x5, fout, timediff);
	LeaveCriticalSection(&sync);

	return 3;
}


The reason I EnterCriticalSection(&sync);initarr(staticarr, x5);LeaveCriticalSection(&sync); is because I do not know if the threads can all access staticarr simultaneously.

Thanks for your input,
Mike
Last edited on
closed account (zwA4jE8b)
The output shows every 1000th position.

Starting multi-threaded sorting>>>>>

Quick Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.016 seconds to complete.
-----------------------------------------------------------------------

Shell Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.031 seconds to complete.
-----------------------------------------------------------------------

Insertion Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.234 seconds to complete.
-----------------------------------------------------------------------

Select Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.327 seconds to complete.
-----------------------------------------------------------------------

Bubble Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 1.903 seconds to complete.
-----------------------------------------------------------------------


Total processing time: 1.903


Starting single-threaded sorting>>>>>

Bubble Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 1.903 seconds to complete.
-----------------------------------------------------------------------

Select Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.328 seconds to complete.
-----------------------------------------------------------------------

Insertion Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.265 seconds to complete.
-----------------------------------------------------------------------

Quick Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.000 seconds to complete.
-----------------------------------------------------------------------

Shell Sort   N = 10000
1391.390     4853.849     8394.386     11762.751    15177.162    
18772.754    22263.241    25720.695    29302.273    32797.765    
Sort took: 0.016 seconds to complete.
-----------------------------------------------------------------------


Total processing time: 2.512
Last edited on
closed account (zwA4jE8b)
Are there more efficient methods?
m4ster r0shi (2201)
closed account (zwA4jE8b)
Thanks, and sorry for being vague, I mean are there more efficient ways of writing the threading aspect of my program. The sorts that I am using were just part of the project. I will look into this 'flash sort' though.
m4ster r0shi (2201)
Oh... Well, usually, you want to have one sorting algorithm implemented using multiple threads,
not multiple threads running different sorting algorithms :P

Bitonic sort is good for parallelization -> http://en.wikipedia.org/wiki/Bitonic_sorter
Topic archived. No new replies allowed.