This repository was archived by the owner on Mar 25, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathParallelQuickSort.cs
More file actions
180 lines (138 loc) · 5.62 KB
/
ParallelQuickSort.cs
File metadata and controls
180 lines (138 loc) · 5.62 KB
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
using System;
using System.Threading;
namespace PDPC_QuickSort {
/**
* The Parallel Quick Sort.
* Tis an Experiment.
*/
public class ParallelQuickSort : Experiment<int[]> {
// The Amount of Threads.
private readonly int AmountOfThreads;
// Default Constructor.
public ParallelQuickSort(string Log, int XMin, int XMax, int NumExecutions) : base(Log, XMin, XMax, NumExecutions) {
// Calculate Amount of Threads.
AmountOfThreads = Environment.ProcessorCount;
// Dirty Way to Find the Lowest Power of 2 value...
while (!IsPowerOfX(AmountOfThreads, 2))
AmountOfThreads -= 1;
}
// Checks if a Number is Power of X.
private bool IsPowerOfX(int Number, int X) {
// 0 isn't power of anything.
if (Number == 0)
return false;
// Calculate Division.
double Division = Math.Log(Number) / Math.Log(X);
// If this is true, then, we are power of X.
return (int) Math.Ceiling(Division) == (int) Math.Floor(Division);
}
// The Parameters for the Parallel QuickSort.
protected class ParallelQuickSortParams {
// The Array.
public int[] Input;
// The Low Value.
public int Low;
// The High Value.
public int High;
// The Level.
public int Level;
// Constructor.
public ParallelQuickSortParams(ref int[] Input, int Low, int High, int Level) {
// Set Data.
this.Input = Input;
this.Low = Low;
this.High = High;
this.Level = Level;
}
}
// Actually Implements the Quicksort.
private void Quicksort_Implementation(object Params) {
// Cast Parameters.
ParallelQuickSortParams ThisParams = Params as ParallelQuickSortParams;
// Partition.
int P = Partition(ref ThisParams.Input, ThisParams.Low, ThisParams.High);
// Calculate Next Level.
int NextLevel = ThisParams.Level + 1;
// Check if Next Level is Parallel.
bool NextIsParallel = (int) Math.Pow(2, NextLevel) <= AmountOfThreads;
// Call Quicksort for the Left and Right Values.
Thread Q1 = Quicksort(ref ThisParams.Input, ThisParams.Low, P, NextLevel, NextIsParallel);
Thread Q2 = Quicksort(ref ThisParams.Input, P + 1, ThisParams.High, NextLevel, NextIsParallel);
// Attempt to Join Both Threads.
Q1?.Join();
Q2?.Join();
}
// Runs Quicksort.
private Thread Quicksort(ref int[] Input, int Low, int High, int Level, bool Parallel = true) {
// Make sure Values are in bounds.
if (Low < 0 || High < 0 || Low >= High)
return null;
// Create Parameters.
ParallelQuickSortParams Params = new ParallelQuickSortParams(ref Input, Low, High, Level);
// Check for Parallel.
if (Parallel) {
// Create new Thread with the Parameters.
Thread QuicksortThread = new Thread(Quicksort_Implementation);
// Start the Thread.
QuicksortThread.Start(Params);
// Return it.
return QuicksortThread;
}
// It isn't Parallel, call the Implementation.
Quicksort_Implementation(Params);
// Return null.
return null;
}
// Partitions the Array.
private int Partition(ref int[] Input, int Low, int High) {
// Get Pivot.
int Pivot = Input[(int)Math.Floor((High + Low) / 2f)];
// Get the Left and Right Indexes.
int Left = Low - 1;
int Right = High + 1;
// Loop Forever... (not really)
while (true) {
// Increment Left until it is >= Pivot.
do Left++; while (Input[Left] < Pivot);
// Decrease Right until it is <= Pivot.
do Right--; while (Input[Right] > Pivot);
// If the Indices are Crossed, return.
if (Left >= Right)
return Right;
// Swap Left and Right Indices.
SwapIndices(ref Input, Left, Right);
}
}
// Generates a Random Input.
public override int[] GenerateInput(int N) {
// Create Result.
int[] Result = new int[N];
// Create new Random.
Random Rand = new Random();
// Generate Random Numbers.
for (int i = 0; i < Result.Length; i++)
Result[i] = Rand.Next();
// Return it.
return Result;
}
// Clones the Input for Each Iteration.
public override int[] CloneInput(int[] Input) {
// Create Result.
int[] Result = new int[Input.Length];
// Copy Input to Result.
Input.CopyTo(Result, 0);
// Return Result.
return Result;
}
// Executes a Single Iteration.
public override void ExecuteIteration(int[] Input) {
// Call Quicksort, Parallel.
Quicksort(ref Input, 0, Input.Length - 1, 0)?.Join();
}
// Swaps two indexes in the Array, using the Semaphore.
private void SwapIndices(ref int[] Input, int X, int Y) {
// Swap Values.
(Input[X], Input[Y]) = (Input[Y], Input[X]);
}
}
}