2.) Revise the function quickSort so that it always chooses the last item in the array as the pivot. Add a counter to the function partition that counts the number of comparisons that are made. Compare the behavior of the revised function with the original one (pivot should be selected using sortFirstMiddleLast algorithm), using arrays of various sizes. At what size array does the difference in the number of comparisons become significant? For which pivot selection strategy does the difference in the number of comparisons become significant? Compare your analysis with the actual running times and counter as a function of the input size n = 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 8192, 16384 and clock() function. For comparison, you need to create two tables for execution times and a counter for both algorithms
2.) Revise the function quickSort so that it always chooses the last item in the array as the pivot.
Add a counter to the function partition that counts the number of comparisons that are made. Compare the behavior of the revised function with the original one (pivot should be selected using sortFirstMiddleLast
does the difference in the number of comparisons become significant? Compare your analysis with the actual running times and counter as a function of the input size n = 2, 4, 8, 16, 32, 64,
128, 256, 512, 1024, 2048, 8192, 16384 <time.h> and clock() function. For comparison, you need to create two tables for execution times and a counter for both algorithms
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 3 images
