Name
Abstract | ||
|---|---|---|
A ne analysis is given of the transitional behavior of the average cost of quicksort with median-of-three. Asymptotic formulae are derived for the stepwise improvement of the average cost of quicksort when iterating median-of-threek rounds for all possible values ofk. The methods used are general enough to apply to quicksort with median-of-(2t + 1) and to explain in a precise manner the transitional behaviors of the average cost from insertion sort to quicksort proper. Our results also imply nontrivial bounds on the expected height, \saturation level", and width in a random locally balanced binary search tree. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/BF02679613 | Algorithmica |
Keywords | Field | DocType |
uniform asymptotics,phase transition,binary search tree,insertion sort. recurrence relations.,ordinary differential equation,quicksort | Discrete mathematics,Combinatorics,Algorithmics,Recurrence relation,Self-balancing binary search tree,Insertion sort,Quicksort,Average cost,Introsort,Binary search tree,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 1 | 0178-4617 |
Citations | PageRank | References |
9 | 0.61 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hua-Huai Chern | 1 | 78 | 7.25 |
| Hsien-Kuei Hwang | 2 | 365 | 38.02 |