search
Log In
0 votes
46 views
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+n\ lg\ (n/k))$ expected time. How should we pick $k$, both in theory and in practice?
in Algorithms 46 views

1 Answer

0 votes

 

this might help

Related questions

0 votes
1 answer
1
74 views
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 74 views
0 votes
0 answers
2
41 views
Suppose that the splits at every level of quicksort are in the proportion $1-\alpha$ to $\alpha$, where $0<\alpha\leq1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $-lg\ n /lg\ \alpha$ and the maximum depth is approximately $-lg\ n / lg\ (1-\alpha)$.(Don’t worry about integer round-off.)
asked Jun 27, 2019 in Algorithms akash.dinkar12 41 views
0 votes
1 answer
3
0 votes
1 answer
4
37 views
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 37 views
...