Name
Abstract | ||
|---|---|---|
We introduce the concept of presorting algorithms, quantifying and evaluating the performance of such algorithms with the average reduction in number of inversions. Stages of well-known algorithms such as Shellsort and quicksort are evaluated in such a framework and shown to cause a meaning drop in the inversion statistic. The expected value, variance and generating function for the decrease in number of inversions are computed. The possibility of “presorting” a sorting algorithm is also investigated under a similar framework. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0304-3975(98)00181-9 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Presorting algorithm,Presorting,presorting,average-case point,Measure of presortedness ( mop ),measure of presortedness mop | Journal | 242 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 2 |
PageRank | References | Authors |
0.47 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsien-Kuei Hwang | 1 | 365 | 38.02 |
| Bo-Yin Yang | 2 | 2 | 0.47 |
| Y.-N. Yeh | 3 | 253 | 44.47 |