Tham khảo tài liệu 'thuật toán algorithms (phần 13)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | QUICKSORT 113 The median-of-three method helps Quicksort in three ways. First it makes the worst case much more unlikely to occur in any actual sort. In order for the sort to take N2 time two out of the three elements examined must be among the largest or among the smallest elements in the file and this must happen consistently through most of the partitions. Second it eliminates the need for a sentinel key for partitioning since this function is served by the three elements examined before partitioning. Third it actually reduces the total running time of the algorithm by about 5 . The combination of a nonrecursive implementation of the three method with a cutoff for small can improve the running time of Quicksort from the naive recursive implementation by 25 to 30 . Further algorithmic improvements are possible for example the median of five or more elements could be used but the amount of time saved will be marginal. More significant time savings can be realized with less effort by coding the inner loops or the whole program in assembly or machine language. Neither path is recommended except for experts with serious sorting applications. 114 Exercises 1. Implement a recursive Quicksort with a cutoff to insertion sort for subfiles with less than M elements and empirically determine the value of M for which it runs fastest on a random file of 1000 elements. 2. Solve the previous problem for a nonrecursive implementation. 3. Solve the previous problem also incorporating the median-of-three improvement. 4. About how long will Quicksort take to sort a file of N equal elements 5. What is the maximum number of times that the largest element could be moved during the execution of Quicksort 6. Show how the file AB AB AB A is partitioned using the two methods suggested in the text. 7. How many comparisons does Quicksort use to sort the keys EASY QUE STION 8. How many sentinel keys are needed if insertion sort is called directly from within Quicksort 9. Would it be .
