English  |  正體中文  |  简体中文  |  Items with full text/Total items : 58323/91876 (63%)
Visitors : 14060451      Online Users : 72
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/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 SizeFormat
    Presorting algorithms An average-case point of view.pdf114KbAdobe PDF0View/Open

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback