class QuicksortAlgorithms { public static void Quicksort(T[] data, int left, int right) where T : IComparable // The Quicksort method uses the IComparable 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[] data, int left, int right) where T : IComparable { 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[] data, int low, int high) where T : IComparable { intleft,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[] data, int i, int j) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } }

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(data, 0, data.Length - 1); string out1 = ""; foreach (int n in data) out1 += n.ToString() + " " + " "; 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(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(data, 0, data.Length - 1); sw.Stop(); MessageBox.Show("Parallel: Time taken = " + sw.ElapsedMilliseconds.ToString()); } }

1- You need to understand the Quick sort algorithm and run the code provided . 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?