Presorting algorithms: An average-case point of view

✍ Scribed by Hsien-Kuei Hwang; Bo-Yin Yang; Yeong-Nan Yeh

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 114 KB
• Volume: 242
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00181-9

✦ Synopsis

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.