This project aims to implement and compare modern variants of the Quicksort algorithm in terms of their performance in sorting integers stored in main memory. The implemented variants include:
1. Quicksort_1p_l (QS1pL): The classic Quicksort algorithm where the leftmost element of the array is selected as the pivot.
2. Quicksort_1p_r (QS1pR): The Quicksort algorithm where a random pivot is selected uniformly at random from all elements of the array.
3. Quicksort_1p_m (QS1pM): The Quicksort algorithm where three candidate pivots are randomly selected, and the median (middle value) of the three is chosen as the final pivot.
4. Quicksort_2p_r (QS2pR): The Quicksort algorithm where two random pivots are selected uniformly at random from all elements of the array.
5. Quicksort_3p_r (QS3pR): This variant uses three pivots p < q < r, and at each iteration, the algorithm divides the array into four subarrays based on the three pivots and recursively sorts them. The pivots are randomly chosen.
6. Based on the previous two variants, two additional variants are generated with the following modifications:
- Quicksort_2p_r_pre (QS2pRPre): Instead of selecting a pivot from the subarray being sorted, a suitable pivot is chosen from the √n sample elements, and the subarray is partitioned accordingly.
- Quicksort_3p_r_pre (QS3pRPre): Similar to QS2pRPre, a suitable pivot from the √n sample elements is selected at each recursive call to partition the subarray.
To compare the competing algorithms on datasets of size n, the following methodology is employed:
1. Generate n integers within the range [0, 2n) pseudorandomly using the random number generator of your computer.
2. Perform the sorting experiment 50 times to calculate the average performance of each competitor for each performance metric. Compute the variance of the performance metric as well.
3. The experimentation is conducted for the following values of n:
- 10,000
- 100,000
- 1,000,000
- 10,000,000
The following performance metrics are used:
1. Execution Time: Measure the time taken by each algorithm to sort the data. Include hardware specifications used, such as CPU speed, memory size, memory speed, and any other relevant details affecting the performance of the competitors.
2. Number of Comparisons: Count the number of comparisons made between integers, such as comparisons with the pivot.
3. Number of Assignments: Count the number of assignments made, e.g., in a swap(a, b), which involves three assignments using a temporary variable. If any smart assignment techniques are employed to reduce the number of assignments, describe them in the pseudocode of the corresponding algorithm.