HW5-part-2: Parallelization of Quick Sort
Due 9/30/2022 No Late Assignment
1- You need to understand the Quick sort algorithm and run the code provided on this
handout.
2- Explain what is the time complexity of the algorithm through examples. Change the
SEQUENTIAL_THRESHOLD = 1000; to 10000 and report the complexity and explain what
did you notice and if it is important from Parallelization point of view. Explain why?
3- Is there any other way to improve the Parallelization of quick sort?
Quick Sort Algorithm and Its Parallelization
The popular Quicksort algorithms recursively partitions the data in two halves based on the
pivot element. Quicksort, on average, makes O(n.log(n)) comparisons to sort n items. In the
worst-case, it makes O(n2) comparisons, though this behavior is very rare.
How Quicksort Works?
Quicksort is a Divide and Conquer algorithm. Like all divide-and-conquer algorithms, it first
divides a large array into two smaller subarrays and then recursively sort the subarrays. As
seen in the below figure, three steps are involved in the whole process:
Pivot selection: randomly pick an element from the array you want to sort, called a pivot, from
the array (usually the leftmost or the rightmost element of the partition).
Partitioning: Reorder the array such that all elements with values less than the pivot come
before the pivot. In contrast, all elements with values greater than the pivot come after it. The
equal values can go either way. After this partitioning, the pivot is in its final position.
Recur: Recursively apply the above steps to the subarray of elements with smaller values than
the pivot and separately to the subarray of elements with greater values than the pivot. The
base case of the recursion is arrays of size 1, which never need to be sorted.
The following is an example that shows how we choose the leftmost element as pivot at each
step of the Quicksort algorithm, partition the array across the pivot, and recur on two
subarrays we get after the partition process:
Let’s take a look at an example to get a better understanding of the Quicksort algorithm. In this
example, the array(shown in graphic below) contains unsorted values, which we will sort using
Quicksort.
Unsorted & Sorted Array
1). Selecting Pivot
The process starts by selecting one element (known as the pivot) from the list; this can be any
element. A pivot can be:
• Any element at random
• The first or last element
• Middle element
For this example, we’ll use the last element, 4, as our pivot.
2). Rearranging the Array
Now, the goal here is to rearrange the list such that all the elements less than the pivot are towards
the left of it, and all the elements greater than the pivot are towards the right of it.
• The pivot element is compared to all of the items starting with the first index. If the element is
greater than the pivot element, a second pointer is appended.
• When compared to other elements, if a smaller element than the pivot element is found, the
smaller element is swapped with the larger element identified before.
Let’s simplify the above example,
• Every element, starting with 7, will be compared to the pivot(4). A second pointer will be
placed at 7 because 7 is bigger than 4.
• The next element, element 2 will now be compared to the pivot. As 2 is less than 4, it will be
replaced by the bigger figure 7 which was found earlier.
• The numbers 7 and 2 are swapped. Now, pivot will be compared to the next element, 1 which
is smaller than 4.
• So once again, 7 will be swapped with 1.
• The procedure continues until the next-to-last element is reached, and at the end the pivot
element is then replaced with the second pointer. Here, number 4(pivot) will be replaced with
number 6.
As elements 2, 1, and 3 are less than 4, they are on the pivot’s left side. Elements can be in any
order: ‘1’,’2’,’3’, or ‘3’,’1’,’2’, or ‘2’,’3’,’1’. The only requirement is that all of the elements must be
less than the pivot. Similarly, on the right side, regardless of their sequence, all components should
be greater than the pivot.
In simple words, the algorithm searches for every value that is smaller than the pivot. Values
smaller than pivot will be placed on the left, while values larger than pivot will be placed on the
right. Once the values are rearranged, it will set the pivot in its sorted position.
3). Dividing Subarrays: Once we have partitioned the array, we can break this problem into two
sub-problems. First, sort the segment of the array to the left of the pivot, and then sort the
segment of the array to the right of the pivot.
Sorting the sub-arrays
• In the same way that we rearranged elements in step 2, we will pick a pivot element for each
of the left and right sub-parts individually.
• Now, we will rearrange the sub-list such that all the elements are less than the pivot point,
which is towards the left. For example, element 3 is the largest among the three elements,
which satisfies the condition, hence the element 3 is in its sorted position.
• In a similar manner, we will again work on the sub-list and sort the elements 2 and 1. We will
stop the process when we get a single element at the end.
• Repeat the same process for the right-side sub-list. The subarrays are subdivided until each
subarray consists of only one element.
• Now At this point, the array is sorted 🙂
Note: Please note that the pivot selection and partitioning steps can be made in several ways,
and the choice of specific implementation schemes significantly affects the algorithm’s
performance.
https://www.geeksforgeeks.org/quick-sort/
Example of Parallelization of quick Sort Algorithm:
quick Sort is a popular operation on large data, thus its parallelization is important to reduce
the execution time. There are different ways to parallelize the sorting algorithm. One easy way
to implement parallelization of Quicksort is to create two parallel tasks for each of the
partitioned lists. To do this let us wright this coed to create a Windows forms application
project called ParallelQuickSort and add a class to the project called QuicksortAlgorithms with
the following code in it.
class QuicksortAlgorithms
{
public static void Quicksort<T>(T[] data, int left, int right)
where T : IComparable<T> // The Quicksort method uses
the IComparable<T> implementation to sort the list entries.
{
if (right > left)
{
int pivot = Partition(data, left, right);
Quicksort(data, left, pivot – 1);
Quicksort(data, pivot + 1, right);
}
}
public static void QuickSortParallel<T>(T[] data, int left, int right)
where T : IComparable<T>
{
const int SEQUENTIAL_THRESHOLD = 1000;
if (right > left)
{
if ((right – left) < SEQUENTIAL_THRESHOLD) Quicksort(data, left,
right); // do sequential sort
else
{ }
}
}
int pivot = Partition(data, left, right);
Parallel.Invoke(() => QuickSortParallel(data, left, pivot – 1),
() => QuickSortParallel(data, pivot + 1, right));
private static int Partition<T>(T[] data, int low, int high) where T :
IComparable<T>
{
int left, right; T
pivotItem;
pivotItem = data[low]; int
pivot = left = low; right =
high;
while (left < right)
{
while (data[left].CompareTo(pivotItem) <= 0)
{
if (left < data.Length – 1)
left++;
else
}
break;
while (data[right].CompareTo(pivotItem) > 0)
{
if (right > 0)
right–;
else
}
break;
if (left < right)
Swap(data, left, right);
}
data[low] = data[right];
data[right] = pivotItem;
8
return right;
}
private static void Swap<T>(T[] data, int i, int j)
{
T temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
To test this code: add three buttons to the form as shown below. The code for the Form1 class
along with the three button handlers is shown below.
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void btnSortSequential_Click(object sender, EventArgs e)
{
double[] data = { 3, 9, 15, 7, 8, 4, 11 };
QuicksortAlgorithms.Quicksort<double>(data, 0, data.Length – 1);
string out1 = “”;
foreach (int n in data)
out1 += n.ToString() + ” ” + “n”;
MessageBox.Show(out1);
}
private void btnSortSequentialLarge_Click(object sender, EventArgs e)
{
int size = 10000000;
double[] data = new double[size];
9
InitData(data);
Stopwatch sw = new Stopwatch();
sw.Start();
QuicksortAlgorithms.Quicksort<double>(data, 0, data.Length – 1);
sw.Stop();
MessageBox.Show(“Sequential: Time taken = ” +sw.ElapsedMilliseconds.ToString());
}
void InitData(double[] data)
{
Random rand = new Random();
for (int i = 0; i < data.Length; i++)
data[i] =rand.NextDouble() * 1000 + 5;
}
private void btnSortParallelLarge_Click(object sender, EventArgs e)
{
int size = 10000000;
double[] data = new double[size];
InitData(data);
Stopwatch sw = new Stopwatch();
sw.Start();
QuicksortAlgorithms.QuickSortParallel<double>(data, 0, data.Length – 1); sw.Stop();
MessageBox.Show(“Parallel: Time taken = ” + sw.ElapsedMilliseconds.ToString());
}
}
Test the execution time of the sequential and parallel quicksort algorithms by clicking on the “Sort
Sequential large” and “Sort Sequential Parallel” buttons.
10