Sorting Algorithms in MOQA

被引：1

作者：

Townley, Jacinta ^{[1
]}

Manning, Joseph ^{[1
]}

Schellekens, Michel ^{[1
]}

机构：

[1] Univ Coll Cork, Dept Comp Sci, CEOL Res Grp, Cork, Ireland

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2009年 / 225卷

基金：

爱尔兰科学基金会;

关键词：

partial order; analysis of algorithms; average case; randomness preservation; sorting; quicksort;

D O I：

10.1016/j.entcs.2008.12.088

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A high-level overview of the MOQA language is presented. The representation of its data structure, a labeled series-parallel partial order, is shown along with some of the functions allowed upon this data structure. The combination of MOQA's data structure and its functions capture the required calculus to statically obtain the average-case time of algorithms written in this language. The implementation of these concepts is discussed and algorithms written in this implementation are presented. A detailed analysis of one of these implemented algorithms, quicksort, critically compares its average-case time in MOQA against the average-case time of standard quicksort. While the asymptotic average of quicksort in MOQA remains unchanged, extra constant costs are incurred by the MOQA method. It is shown that these costs result from molding the algorithm around the MOQA data structure and functions versus the general approach of choosing the data structure and functions that best match the algorithm. This limitation is balanced against an approach that aims to obtain the average-case time of algorithms statically.

引用

页码：391 / 404

页数：14

共 23 条

[1]

Abelson H., 1996, STRUCTURE INTERPRETA

[2]

Chase David R., 1990, PLDI

[3]

Cormen T. H., 2001, INTRO ALGORITHMS 2 E

[4]

Flajolet P., 1989, 1073 I NAT RECH INF

[5]

Flajolet Philippe, 1993, 1888 I NAT RECH INF

[6]

Flajolet Philippe, 1981, CAHIERS BUREAU U REC, V34-35

[7]

Flajolet Philippe, 1991, THEORETICAL COMPUTER

[8]

Flajolet Philippe, ANAL COMBINATORICS

[9]

Foata Dominique, 1974, SRIE GNRATRICE EXPON

[10]

Goulden I., 1983, COMBINATORIAL ENUMER

← 1 2 3 →