Quicksort
Download the support code for this lab|^LabQuicksort.zip\. Look at the base quicksort implementation (QuickSortBasic class), at the tests offered and at the Main program.
Also download the lecture notes on this subject.
Exercises:
- Starting from QuickSortBasic, build the task-decomposed version of QuickSort to in slide 17 of the lecture.
- Starting from QuickSort with Tasks, build the parallel version of QuickSort to in slide 21 of the lecture.
- Starting from the parallel version of quicksort, build a more efficient parallel version, where the parallel tasks are created only at the topmost level, and all subsequent recursive calls are performed sequentially.
- Improve the above version by selecting the median element of the array as pivot.
Note: To analyze the performance of the parallel algorithm, use an input ArrayList that gets sorted in a few seconds on your machine.