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