有没有比Bogosort（又名猴sorting）更糟糕的sortingalgorithm？

我的同事们把我赶回大学的时候，今天早上讨论了sortingalgorithm。 我们回想起我们最喜欢的StupidSort ，我们中的一个人确定我们看到了一个sortingalgorithm是O(n!) 。 这让我开始寻找我能find的“最糟糕的”sortingalgorithm。

我们假设一个完全随机的sorting将是非常糟糕的（即随机化元素 – 是否按顺序？再次随机化），我环顾四周，发现它显然被称为BogoSort或Monkey Sort，或者有时候只是随机sorting 。

猴sorting似乎具有O(∞)的最坏情况性能， O(∞) O(n)的最佳情况性能和O(n·n!)的平均性能。

有没有任何命名algorithm的平均性能比O(n·n!) ？ 或者只比猴子sorting一般？

Answer 1

来自David Morgan-Mar的神秘algorithm页面： 智能devisesorting

介绍

智能devisesorting是基于智能devise理论的sortingalgorithm。

algorithm描述

原始input列表的确切顺序的概率是1 /（n！）。 有这么一个小的可能性，说这是偶然发生这显然是荒谬的，所以它必须有意识地通过一个智能分拣机的顺序。 因此，可以假设它已经以某种方式被最优化地sorting，超越了我们对“升序”的天真的理解。 任何试图改变这个顺序以符合我们自己的偏见的尝试实际上会使它不那么sorting。

分析

这个algorithm在时间上是不变的，并且就地sorting列表，根本不需要额外的内存。 事实上，它甚至不需要任何可疑的技术电脑的东西。 赞美分拣机！

反馈

加里·罗杰斯写道：

使sorting时间不变，否认分拣机的威力。 分拣机存在时间之外，因此sorting是永恒的。 要花费时间来validation分类器的作用，会减lessSorter的作用。 因此…这种特殊的types是有缺陷的，不能归因于“分拣机”。

异端！

Answer 2

多年前，我发明了（但从未实际执行过）MiracleSort。

 Start with an array in memory. loop: Check to see whether it's sorted. Yes? We're done. No? Wait a while and check again. end loop 

最终，在存储芯片中翻转位的阿尔法粒子应该导致成功的分类。

为了获得更高的可靠性，请将arrays复制到屏蔽位置，并根据原始值检查可能sorting的arrays。

那么你如何检查对原始的可能sorting的数组？ 您只需对每个数组进行sorting并检查它们是否匹配。 MiracleSort是用于此步骤的明显algorithm。

编辑：严格来说，这不是一个algorithm，因为它不保证终止。 “不是algorithm”是否被认为是“更坏的algorithm”？

Answer 3

量子Bogosort

一种sortingalgorithm，假设量子力学的许多世界的解释是正确的：

1. 检查列表是否已sorting。 如果不是，则摧毁宇宙。

algorithm结束时，列表将被sorting在唯一的宇宙左侧。 该algorithm采用最坏情况下的O（N）和平均情况O（1）时间。 实际上，进行比较的平均次数是2：在第二个元素上有50％的机会被毁灭，25％的机会在第三个元素上被破坏，依此类推。

Answer 4

叮当sorting，如此处所述。

你在圣诞节时将你的名单中的每个值都给予另一个孩子。 孩子，作为可怕的人类，会比较他们的礼物的价值，并相应地sorting自己。

Answer 5

我很惊讶没有人提到sleepsort然而…还是我没有注意到它？ 无论如何：

 #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait 

示例用法：

 ./sleepsort.sh 5 3 6 3 6 3 1 4 7 ./sleepsort.sh 8864569 7 

在performance方面是可怕的（特别是第二个例子）。 等了将近3.5个月的时间sorting2个数字还是不错的。

Answer 6

我有一位曾经build议生成一个随机数组的讲师，检查它是否被sorting，然后检查数据是否与要sorting的数组相同。

最好的情况O（N）（第一次的宝贝！）最坏的情况O（永远）

Answer 7

如果你保持algorithm有意义的话， O(n!)是你能达到的最坏的上界。

由于检查每个可能的排列集将被sortingn! 步骤，你不能比这更糟糕。

如果你正在做更多的步骤那么algorithm没有真正有用的目的。 更不用说下面的O(infinity)简单sortingalgorithm：

 list = someList while (list not sorted): doNothing 

Answer 8

你应该对Pessimal Algorithms和Simplexity Analysis这个激动人心的领域做一些研究。 这些作者研究的问题是用最好的情况来开发一个类（最好的情况是Omega（n），而慢速（看文章）有一个非多项式的最佳情况时间复杂度）。

Answer 9

这里有两种我在大学里和我的室友想出来的

1）检查命令2）也许奇迹发生了，去1

和

1）检查是否按顺序，如果不是的话2）把每个元素放到一个包里，然后把它从远处的服务器反弹回去。 其中一些数据包将以不同的顺序返回，因此请转到1

Answer 10

Bogobogosort。 是的，这是一件事。 Bogobogosort，你Bogosort的第一个元素。 检查一个元素是否被sorting。 作为一个元素，它将是。 然后你添加第二个元素，并Bogosort这两个，直到它被sorting。 然后再添加一个元素，然后添加Bogosort。 继续添加元素和Bogosorting，直到最终完成每个元素。 在宇宙的热死之前，这个devise从来没有成功过。

Answer 11

总有Bogobogosort（Bogoception！）。 它对越来越大的列表子集执行Bogosort，然后如果列表未被sorting，则重新开始。

 for (int n=1; n<sizeof(list); ++n) { while (!isInOrder(list, 0, n)) { shuffle(list, 0, n); } if (!isInOrder(list, 0, n+1)) { n=0; } } 

Answer 12

1把你的物品分类在索引卡上
2在你家的一个大风天，把它们扔到空中。
2把它们扔进篝火，并确认它们完全被摧毁。
3检查厨房地板的正确顺序。
4如果不是正确的顺序，重复。

最好的情况是O（∞）

根据KennyTM的精确观察结果编辑。

Answer 13

“你想成为什么？” 分类

1. 记下系统时间。
2. 使用Quicksort（或其他任何合理合理的）sorting，省略最后的交换。
3. 记下系统时间。
4. 计算所需的时间。 扩展精度算术是一个要求。
5. 等待所需的时间。
6. 执行最后的交换。

它不仅可以实现任何可能的无限的O（x）值，所花费的时间是可certificate的正确的（如果你可以等待那么久）。

Answer 14

有一种叫做bogobogosort。 首先，它检查前两个元素，并对它们进行初始化。 接下来检查前3个，他们，等等。 如果该列表随时出现故障，则重新启动前两个。 普通的bogosort平均复杂度为O（N！），这个algorithm的平均复杂度为O（N！1！2！3！… N！）编辑：为了让你知道这个数字有多大，对于20个元素，这个algorithm的平均值为3.930093 * 10 ^ 158年，远高于10 ^ 100年的build议宇宙热量死亡（如果发生的话），而合并sorting需要大约.0000004秒，冒泡sorting为0.0000016秒，bogosort需要308年，139天，19小时，35分，22.306秒，假设一年365.242天，计算机每秒钟完成250,000,000次32位整数运算。 编辑2：这个algorithm并不像“algorithm”奇迹般的sorting，这可能像这样，将成功sorting20个元素之前，计算机吸入黑洞，但如果这样做，我估计一个平均的复杂性（32位整数中的位数） N）（元素数量） （数字<= 10 ^ 40年），因为重力加速了移动的芯片，并且有2 ^ N个状态，即2 ^ 640 * 10 ^ 40，即5.783 * 10 ^ 216.762162762年，但如果列表开始sorting，它的复杂度只会是O（N），比合并sorting快，只有N log N偶数编辑3：这个algorithm实际上比奇迹sorting慢，因为我的algorithm的运行时间为2.83 * 10 ^ 1175546年，而尺寸变得非常大，比如说1000，而奇迹sortingalgorithm将会运行时间为1.156 * 10 ^ 9657年。

Answer 15

没有什么比无穷更糟了。

Answer 16

Bozosorting是一个相关的algorithm，它检查列表是否被sorting，如果不是，则随机交换两个项目。 它具有相同的最好和最坏的情况下的performance，但我会直观地预期平均情况比Bogosort更长。 这个algorithm的性能很难find（或产生）任何数据。

Answer 17

O（∞）的最坏情况performance可能甚至不会使它成为一些algorithm。

一个algorithm只是一系列的步骤，你总是可以做得更糟糕的调整一点，以获得所需的输出更多的步骤比以前采取。 可以有意识地把algorithm的步数知道，并且在X步完成之后才能终止并产生正确的输出。 X很可能是O（n ² ）或O（n ^n！ ）的顺序，或者是algorithm所要做的。 这将有效地增加最佳情况和平均情况。

但是，你最糟糕的情况是不能顶的:)

Answer 18

π的分段

假设π包含所有可能的有限数字组合。 请参阅math.stackexchange问​​题

1. 根据数组大小确定所需的位数。
2. 使用π位置的段作为索引来确定如何重新排列数组。 如果一个段超出了该数组的大小边界，则调整π小数偏移量并重新开始。
3. 检查重新sorting的数组是否已sorting。 如果它是woot，否则调整偏移并重新开始。

Answer 19

我最喜欢的慢sortingalgorithm是stoogesorting：

 void stooges(long *begin, long *end) { if( (end-begin) <= 1 ) return; if( begin[0] < end[-1] ) swap(begin, end-1); if( (end-begin) > 1 ) { int one_third = (end-begin)/3; stooges(begin, end-one_third); stooges(begin+one_third, end); stooges(begin, end-one_third); } } 

最坏情况的复杂度是O(n^(log(3) / log(1.5))) = O(n^2.7095...) 。

另一个慢sortingalgorithm实际上被命名为slowsort！

 void slow(long *start, long *end) { if( (end-start) <= 1 ) return; long *middle = start + (end-start)/2; slow(start, middle); slow(middle, end); if( middle[-1] > end[-1] ) swap(middle-1, end-1); slow(start, end-1); } 

这个在最好的情况下需要O(n ^ (log n)) …甚至比stoogesort慢。

Answer 20

 Recursive Bogosort (probably still O(n!){ if (list not sorted) list1 = first half of list. list 2 = second half of list. Recursive bogosort (list1); Recursive bogosort (list2); list = list1 + list2 while(list not sorted) shuffle(list); } 

Answer 21

这个网页是一个有趣的阅读主题： http : //home.tiac.net/~cri_d/cri/2001/badsort.html

我个人最喜欢的是汤姆达夫的傻瓜：

 /* * The time complexity of this thing is O(n^(a log n)) * for some constant a. This is a multiply and surrender * algorithm: one that continues multiplying subproblems * as long as possible until their solution can no longer * be postponed. */ void sillysort(int a[], int i, int j){ int t, m; for(;i!=j;--j){ m=(i+j)/2; sillysort(a, i, m); sillysort(a, m+1, j); if(a[m]>a[j]){ t=a[m]; a[m]=a[j]; a[j]=t; } } } 

Answer 22

双bogosort

Bogosort两次，并比较结果（只是为了确保它是sorting），如果不这样做再次

Answer 23

你可以通过随机运行“is it sorted”步骤来使任何sortingalgorithm变得更慢。 就像是：

1. 创build一个与你正在sorting的数组大小相同的布尔值数组。 将它们全部设置为false。
2. 运行一个bogosort的迭代
3. 挑选两个随机元素。
4. 如果两个元素相互sorting（i <j && array [i] <array [j]），则将布尔数组上的两个索引标记为true。 过来，重新开始。
5. 检查数组中的所有布尔值是否为真。 如果没有，请回到3。
6. 完成。

Answer 24

是的，SimpleSort在理论上运行在O(-1)但是这相当于O(...9999) ，这相当于O（∞ – 1），它恰好也相当于O（∞ ）。 这是我的示例实现：

 /* element sizes are uneeded, they are assumed */ void simplesort (const void* begin, const void* end) { for (;;); } 

Answer 25

我正在做的一件事情就是挑选两个随机点，如果它们的顺序错误，则颠倒它们之间的整个子范围。 我在http://richardhartersworld.com/cri_d/cri/2001/badsort.htmlfind了这个algorithm，它说平均情况可能在O（n ^ 3）或O（n ^ 2 log n）（他不太确定）。

我认为有可能更有效率地做，因为我认为在O（1）时间内做反转操作是可能的。

其实我只是意识到这样做可能会让我说的所有事情，也许是因为我刚刚意识到，我想到的数据结构将访问随机元素在O（log n），并确定是否需要在O（n ）。

Answer 26

Randomsubsetsort。

给定n个元素的数组，以概率1 / nselect每个元素，随机化这些元素，并检查数组是否已sorting。 重复，直到sorting。

预期的时间留给读者作为练习。