...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Natural Computing >Rainbow sort: Sorting at the speed of light
【24h】

Rainbow sort: Sorting at the speed of light

机译：彩虹排序：以光速排序

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

摘要

Rainbow Sort is an unconventional method for sorting, which is based on the physical concepts of refraction and dispersion. It is inspired by the observation that light that traverses a prism is sorted by wavelength. At first sight this "rainbow effect" that appears in nature has nothing to do with a computation in the classical sense, still it can be used to design a sorting method that has the potential of running in Θ(n) with a space complexity of Θ(n), where n denotes the number of elements that are sorted. In Section 1, some upper and lower bounds for sorting are presented in order to provide a basis for comparisons. In Section 2, the physical background is outlined, the setup and the algorithm are presented and a lower bound for Rainbow Sort of Ω(n) is derived. In Section 3, we describe essential difficulties that arise when Rainbow Sort is implemented. Particularly, restrictions that apply due to the Heisenberg uncertainty principle have to be considered. Furthermore, we sketch a possible implementation that leads to a running time of O(n + m), where m is the maximum key value, i.e., we assume that there are integer keys between 0 and m. Section 4 concludes with a summary of the complexity and some remarks on open questions, particularly on the treatment of duplicates and the preservation of references from the keys to records that contain the actual data. In Appendix A, a simulator is introduced that can be used to visualise Rainbow Sort.
机译：Rainbow Sort是一种非常规的排序方法，它基于折射和色散的物理概念。受到观察的启发，穿过棱镜的光线按波长分类。乍一看，自然界中出现的这种“彩虹效应”与经典意义上的计算无关，它仍然可以用来设计一种排序方法，这种方法有可能在Θ（n）中运行，且空间复杂度为Θ（n），其中n表示已排序元素的数量。在第1节中，给出了一些排序的上下限，以便为比较提供基础。在第2节中，概述了物理背景，介绍了设置和算法，并得出了Ω（n）的Rainbow Sort的下限。在第3节中，我们描述了实现Rainbow Sort时出现的基本困难。特别是，必须考虑由于海森堡不确定性原理而导致的限制。此外，我们勾画出一种可能的实现方式，该实现方式会导致运行时间为O（n + m），其中m是最大键值，即，我们假设在0到m之间有整数键。第四部分总结了复杂性，并对未解决的问题作了一些总结，特别是对重复项的处理以及对包含实际数据的记录的键的引用的保留。在附录A中，介绍了可用于可视化Rainbow Sort的模拟器。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号