检索结果-内蒙古大学图书馆

introspective sorting and selection algorithms

SOFTWARE-PRACTICE & EXPERIENCE 1997年第8期27卷 983-993页

作者： Musser, DR Computer Science Department Rensselaer Polytechnic Institute Troy NY 12180 U.S.A.

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Theta(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Theta(N-2). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much - one might as well use heapsort, which has a Theta(N log N) worst-case time bound, but is on the average 2-5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the 'stopper' yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Theta(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum-Floyd-Pratt-Rivest-Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C++ Standard Template Library. (C) 1997 by John Wiley & Sons, Ltd.

关键词： quicksort heapsort sorting algorithms introspective algorithms hybrid algorithms generic algorithms STL

来源：评论

学校读者我要写书评

暂无评论

introspective sorting and selection revisited

引用

SOFTWARE-PRACTICE & EXPERIENCE 2000年第6期30卷 617-638页

作者： Valois, JD Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA

We describe two improvements to introspective sorting and selection algorithms: a simple rule fine-grained introspection that detects potential worst-case performance after only a small constant number of partitioning steps, and the use of remedial randomization as an intervention strategy in order to reduce the performance penalty for false positives. We present experimental results showing that these techniques provide significant improvements in the running time for worst-case and other troublesome inputs, without sacrificing performance on well-behaved inputs. Copyright (C) 2000 John Wiley & Sons, Ltd.

关键词： Quicksort Find sorting and selection algorithms introspective algorithms hybrid algorithms generic algorithms

来源：评论

学校读者我要写书评

暂无评论

introspective Sorting and Selection algorithms

引用

Software: Practice and Experience 1999年第8期27卷

作者： DAVID R. MUSSER Computer Science Department Rensselaer Polytechnic Institute Troy NY 12180 U.S.A.

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ( N log N ), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ( N 2 ). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much – one might as well use heapsort, which has a Θ( N log N ) worst-case time bound, but is on the average 2–5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i -th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the ‘stopper’ yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Θ( N log N ) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum–Floyd–Pratt–Rivest–Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C+:+ Standard Template Library. ©1997 by John Wiley & Sons, Ltd.

关键词： quicksort heapsort sorting algorithms introspective algorithms hybrid algorithms generic algorithms STL

来源：评论

学校读者我要写书评

暂无评论

Worst-case Optimal Incremental Sorting 34

Worst-case Optimal Incremental Sorting

引用

2015 34th International Conference of the Chilean Computer Science Society (SCCC)

作者： Regla, Erik Paredes, Rodrigo Univ Talca Dept Ciencias Computac Curico Chile

ISBN: (纸本)9781467398176

We present an online algorithm to, given a fixed array A, retrieve its k smallest elements in optimum time for the worst case, that presents fast response in practice. For this, we devise an introspective version of the Incremental Quicksort (IQS) algorithm, which controls the size of the auxiliary stack of the IQS algorithm via an introspective criteria.

关键词： Worst case Incremental sorting introspective algorithms

来源：评论

学校读者我要写书评

暂无评论

Constructing DHCP Using Electronic Archetypes

引用

网络安全技术与应用 2014年第1期 7-7,9页

作者：喜彦贵余跃北京交通大学理学院数学系北京100044

Random symmetries and e-business have garnered profound interest from both mathematicians and analysts in the last several years. Given the current status of extensible theory,electrical engineers dubiously desire the study of fiber-optic cables. FluxEire,our new system for introspective algorithms,is the solution to all of these problems.

关键词： electronic archetypes introspective algorithms network

来源：评论

学校读者我要写书评

暂无评论

Worst-case Optimal Incremental Sorting

Worst-case Optimal Incremental Sorting

引用

International Conference of the Chilean Computer Science Society

作者： Erik Regla Rodrigo Paredes Departamento de Ciencias de la Computación Universidad de Talca Curicó Chile

ISBN: (纸本)9781467398183

关键词： Worst case Incremental sorting introspective algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：