...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Fun-Sort - or the chaos of unordered binary search
【24h】

Fun-Sort - or the chaos of unordered binary search

机译：Fun-Sort-或无序二进制搜索的混乱

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

摘要

Usually, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated "binary searches" in an initially unsorted array also sorts n elements in time Theta(n(2) log n). If n is a power of two, then the expected termination point of a binary search in a random permutation of n elements is exactly the cell where the element should be if the array was sorted. We further show that we can sort in expected time Theta(n(2) log n) by always picking two random cells and swapping their contents if they are not ordered correctly. (C) 2004 Elsevier B.V. All rights reserved.
机译：通常，二进制搜索仅在排序数组中才有意义。我们显示，基于最初未排序的数组中重复的“二进制搜索”的插入排序还可以在时间Theta（n（2）log n）中对n个元素进行排序。如果n是2的幂，则在对n个元素进行随机排列的情况下，二进制搜索的预期终止点恰好是对数组进行排序时元素应位于的单元格。我们进一步表明，可以通过始终选择两个随机单元格并交换它们的内容（如果未正确排序）来按预期时间Theta（n（2）log n）进行排序。 （C）2004 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号