• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Information Science >Formulation and analysis of in-place MSD radix sort algorithms
【24h】

Formulation and analysis of in-place MSD radix sort algorithms

机译：就地MSD基数排序算法的制定和分析

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We present a unified treatment of a number of related in-place MSD radix sort algorithms with varying radices, collectively referred to here as 'Matesort' algorithms. These algorithms use the idea of in-place partitioning which is a considerable improvement over the traditional linked list implementation of radix sort that uses 0(n) space. The binary Matesort algorithm is a recast of the classical radix-exchange sort, emphasizing the role of in-place partitioning and efficient implementation of bit processing operations. This algorithm is O(k) space and has O(kn) worst-case order of running time, where k is the number of bits needed to encode an element value and n is the number of elements to be sorted. The binary Matesort algorithm is evolved into a number of other algorithms including 'continuous Matesort' for handling floating point numbers, and a number of 'general radix Matesort' algorithms. We present formulation and analysis for three different approaches (sequential, divide-and-conquer and permutation-loop) for partitioning by the general radix Matesort algorithm. The divide-and-conquer approach leads to an elegantly coded algorithm with better performance than the permutation-loop-based American Flag Sort algorithm.
机译：我们提出了许多不同半径的相关MSD基数排序算法的统一处理方法，这里统称为“ Matesort”算法。这些算法使用就地分区的思想，它是对使用0（n）空间的基数排序的传统链表实现的显着改进。二进制Matesort算法是经典基数交换类型的重铸，强调了就地分区和有效执行位处理操作的作用。此算法为O（k）空间，运行时间为O（kn）最坏情况顺序，其中k是编码元素值所需的位数，n是要排序的元素数。二进制Matesort算法已演变为许多其他算法，包括用于处理浮点数的“连续Matesort”和许多“通用基数Matesort”算法。我们介绍了三种不同的方法（顺序，分治和置换循环）的公式化和分析方法，这些方法通过通用基数Matesort算法进行分区。与基于置换循环的美国国旗分类算法相比，分而治之的方法产生了一种性能更好的编码算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号