Menu
I am self learning CLRS 3rd edition and here is one of the tougher questions that I have encountered along with its answer as a service to all.
7.4-5
We can improve the running time of quicksort in practice by taking advantage of the
fast running time of insertion sort when its input is “nearly” sorted. Upon calling
quicksort on a subarray with fewer than k elements, let it simply return without
sorting the subarray. After the top-level call to quicksort returns, run insertion sort
on the entire array to finish the sorting process. Argue that this sorting algorithm
runs in O(nk+nlg(n/k)) expected time. How should we pick k, both in theory
and in practice?
219
Insertion sort has an average and worst-case running time of O ( n 2 ) O(n^2) O(n2), so in most cases, a faster algorithm is more desirable.
They are both O(n log n).
To sort an array of n distinct elements, quicksort takes O(n log n) time in expectation, averaged over all n! permutations of n elements with equal probability.
But, insertion sort is more efficient than quick sort in case of small arrays as the number of comparisons and swaps are less compared to quicksort. So we combine the two algorithms to sort efficiently using both approaches.
If you eval equation nlgn > nk + nlog(n/k) you get log k > k. Which is impossible. Hence in theory it's not possible. But in practice there are constant factors involved with insertion sort and quicksort. Take a look at the solution discussed in this pdf. You might want to update your answer. .
163
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
