Presorting algorithms : An average-case point of view

機構典藏 > College of Sciences > Graduate Institute & Department of Mathematics > Journal Article > Item 987654321/41565

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/41565

Title:	Presorting algorithms : An average-case point of view
Other Titles:	排序演算法之先期處理: 以平均情形的觀點
Authors:	黃顯貴;Hwang, Hsien-kwei;楊柏因;Yang, Bo-yin;葉永南;Yeh, Yeong-nan
Contributors:	淡江大學數學學系
Keywords:	Presorting;Measure of presortedness (mop)
Date:	2000-07-06
Issue Date:	2010-01-28 07:50:05 (UTC+8)
Publisher:	Elsevier
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.
Relation:	Theoretical Computer Science 242(1-2), pp.29-40
DOI:	10.1016/S0304-3975(98)00181-9
Appears in Collections:	[Graduate Institute & Department of Mathematics] Journal Article

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	128	View/Open
Presorting algorithms An average-case point of view.pdf		114Kb	Adobe PDF	1	View/Open