首页 文章

是否有比Bogosort（a.k.a Monkey Sort）更差的排序算法？ [关闭]

提问于
浏览 次
156

我的同事们带我回到了我的大学时代，今天早上讨论了排序算法 . 我们回忆起我们的最爱，如StupidSort，我们其中一个人确信我们已经看到了一个 O(n!) 的排序算法 . 这让我开始寻找我能找到的"worst"排序算法 .

我们假设一个完全随机的排序会非常糟糕（即随机化元素 - 它是否按顺序排列？没有？再次随机化），我环顾四周，发现它显然被称为BogoSort, or Monkey Sort, or sometimes just Random Sort .

Monkey Sort似乎具有最差的 O(∞) 表现，最佳表现为 O(n) ，平均表现为 O(n·n!) .

是否有任何命名算法的平均性能比 O(n·n!) 差？或者只是比一般的猴子排序更愚蠢？

algorithm sorting big-o

26 回答

  • 7

    “你想要的是什么？”分类

    • 注意系统时间 .

    • 使用Quicksort（或任何其他合理合理的）排序，省略最后一次交换 .

    • 注意系统时间 .

    • 计算所需时间 . 扩展精度算术是必需的 .

    • 等待所需时间 .

    • 执行最后一次交换 .

    它不仅可以实现任何可以想象的无穷大的O（x）值，所以所花费的时间是可证明的（如果你可以等那么久） .

    回复于
  • 29

    没有什么比无限更糟糕了 .

    回复于
  • 16

    来自David Morgan-Mar的密集算法页面： Intelligent Design Sort

    简介智能设计排序是一种基于智能设计理论的排序算法 . 算法描述原始输入列表按其精确顺序排列的概率为1 /（n！） . 这样的可能性很小，说这是偶然发生的，这显然是荒谬的，所以必须由智能分拣机有意识地按顺序排列 . 因此，可以安全地假设它已经以某种方式进行了最佳排序，超越了我们对“升序”的幼稚理解 . 任何改变该顺序以符合我们自己的先入之见的尝试实际上会使它更少排序 . 分析该算法在时间上是恒定的，并且就地对列表进行排序，根本不需要额外的内存 . 事实上，它甚至不需要任何可疑的技术计算机的东西 . 赞美分拣机！反馈加里罗杰斯写道：使排序不变的时间否定了分拣机的力量 . 分拣机存在于时间之外，因此排序是永恒的 . 需要时间来验证排序会降低分拣机的作用 . 因此......这种特殊的类型是有缺陷的，不能归因于“分拣机” . 异端！

    回复于
  • 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

    最终，在存储芯片中翻转位的α粒子应该导致成功排序 .

    为了获得更高的可靠性，请将阵列复制到屏蔽位置，并根据原始阵列检查可能已排序的阵列 .

    那么如何根据原始数据检查可能排序的数组呢？您只需对每个数组进行排序并检查它们是否匹配 . MiracleSort是用于此步骤的明显算法 .

    EDIT: 严格地说，这不是算法，因为它不能保证终止 . "not an algorithm"是否符合"a worse algorithm"的条件？

    回复于
  • 54

    Quantum Bogosort

    一种排序算法，假设量子力学的多世界解释是正确的：

    • 检查列表是否已排序 . 如果没有，摧毁宇宙 .

    在算法结束时，列表将在唯一的宇宙中排序 . 该算法采用最坏情况O（N）和平均情况O（1）时间 . 实际上，执行的平均比较次数为2：宇宙将在第二个元素上被破坏的可能性为50％，在第三个元素上将被破坏的可能性为25％，依此类推 .

    回复于
  • 1

    我很惊讶没有人提到过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

    在性能方面它很糟糕（尤其是第二个例子） . 等待近3.5个月来排序2个数字有点糟糕 .

    回复于
  • 2

    Jingle Sort，如here所述 .

    在圣诞节期间，您将列表中的每个值分配给另一个孩子 . 孩子们，作为可怕的人类，将比较他们的礼物的 Value ，并相应地自我排序 .

    回复于
  • 14

    我有一位讲师曾经建议生成一个随机数组，检查它是否已经排序，然后检查数据是否与要排序的数组相同 .

    最佳情况O（N）（第一次宝贝！）最坏情况O（从不）

    回复于
  • 54

    如果您以任何方式保持算法有意义， O(n!) 是您可以实现的最差上限 .

    因为检查要排序的集合的排列的每种可能性将花费 n! 步骤，所以你不能比这更糟糕 .

    如果你正在做更多的步骤，那么算法没有真正有用的目的 . 更不用说以下带有 O(infinity) 的简单排序算法：

    list = someList
while (list not sorted):
    doNothing
    回复于
  • 17

    你应该对Pessimal Algorithms and Simplexity Analysis的激动人心的领域做一些研究 . 这些作者研究了使用pessimal最佳情况开发排序的问题（你的bogosort最好的情况是Omega（n），而slowsort（参见论文）具有非多项式最佳情况时间复杂度） .

    回复于
  • 1

    Bogobogosort . 是的，这是一件事 . 到Bogobogosort，你是Bogosort的第一个元素 . 检查是否对该元素进行了排序 . 作为一个元素，它将是 . 然后你添加第二个元素，并将这两个元素Bogosort直到它为止排序 . 然后再添加一个元素，然后再添加Bogosort . 继续添加元素和Bogosorting，直到你最终完成每个元素 . 在宇宙热死之前，这个设计永远不会成功 .

    回复于
  • 9

    这是我在大学里找到室友的2种情况

    1）检查订单2）可能发生奇迹，转到1

    和

    1）检查它是否有序，如果不是2）将每个元素放入数据包并将其从远程服务器反弹回自己 . 其中一些数据包将以不同的顺序返回，因此请转到1

    回复于
  • 3

    总是有Bogobogosort（Bogoception！） . 它在列表的越来越大的子集上执行Bogosort，然后如果列表未被排序则重新开始 .

    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; }
}
    回复于
  • 5

    有一种叫做bogobogosort的东西 . 首先，它检查前两个元素，并对它们进行bogosorts . 接下来它检查前3个，bogosorts他们，依此类推 . 如果列表在任何时候出现故障，它会通过再次对前2个进行重新启动来重新启动 . 常规bogosort的平均复杂度为O（N！），此算法的平均复杂度为O（N！1！2！3！... N！）编辑：为了让您了解此数字的大小，对于20个元素，该算法平均需要3.930093 * 10 ^ 158年，远高于提出的10 ^ 100年的宇宙热死亡（如果它发生），而合并排序需要大约.0000004秒，冒泡排序.0000016秒和博格索需要308年，139天，19小时，35分钟，22.306秒，假设一年是365.242天，计算机每秒执行250,000,000次32位整数运算 . 编辑2：这个算法并不像"algorithm"奇迹排序一样慢，这可能就像这样，在成功排序20个elemtnts之前会让计算机陷入黑洞，但如果确实如此，我估计平均复杂度为2 ^（32（32位整数中的位数）N）（元素个数）（数量<= 10 ^ 40年，因为重力加速了筹码运动，并且有2 ^ N个状态，其中是2 ^ 640 * 10 ^ 40，或者约5.783 * 10 ^ 216.762162762年，虽然如果列表开始排序，其复杂性只会是O（N），比合并排序更快，即使在列表中也只有N log N.最坏的情况 . 编辑3：这个算法实际上比奇迹排序慢，因为大小变得非常大，比如1000，因为我的算法的运行时间为2.83 * 10 ^ 1175546年，而奇迹排序算法的运行时间为1.156 * 10 ^ 9657年 .

    回复于
  • 12

    1将您的物品放在索引卡上
    2在距离你家一英里的刮风天将它们扔到空中 .
    2将它们扔进篝火并确认它们完全被摧毁 .
    3检查厨房地板是否正确订购 .
    4如果订单不正确，请重复此操作 .

    最佳案例场景是O（∞）

    Edit 基于KennyTM的敏锐观察 .

    回复于
  • 9

    Bozo sort是一种相关的算法，用于检查列表是否已排序，如果不是，则随机交换两个项目 . 它具有相同的最佳和最差情况表现，但我会直观地预期平均情况比Bogosort更长 . 很难找到（或产生）关于该算法性能的任何数据 .

    回复于
  • 4

    Segments of π

    假设π包含所有可能的有限数组合 . 见math.stackexchange question

    • 根据数组大小确定所需的位数 .

    • 使用π个位段作为索引来确定如何重新排序数组 . 如果某个段超出此数组的大小边界，请调整π十进制偏移量并重新开始 .

    • 检查重新排序的数组是否已排序 . 如果是woot，否则调整偏移并重新开始 .

    回复于
  • 5

    O（∞）的最坏情况性能甚至可能不会使其成为some的算法 .

    算法只是一系列步骤，您可以通过稍微调整一下来获得所需的输出，而不是以前采取的步骤 . 人们可以故意将所采取步骤数的知识放入算法中，并使其终止并仅在完成步骤数后才产生正确的输出 . X 很可能是O（n2）或O（nn！）的顺序或者算法所希望的 . 这将有效地增加其最佳案例和平均案例界限 .

    但是你最糟糕的情况不能超过:)

    回复于
  • 18

    我最喜欢的慢排序算法是stooge排序：

    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...) .

    另一个慢排序算法实际上命名为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慢 .

    回复于
  • 1
    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);
}
    回复于
  • 413

    这个页面是关于这个主题的有趣读物：http://home.tiac.net/~cri_d/cri/2001/badsort.html

    我个人最喜欢的是Tom Duff的傻话：

    /*
 * 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; }
        }
}
    回复于
  • 127

    双重bogosort

    Bogosort两次并比较结果（只是为了确保它已经分类）如果不再这样做

    回复于
  • 44

    您可以通过随机运行“is it sorted”步骤来减慢任何排序算法 . 就像是：

    • 创建一个与您要排序的数组大小相同的布尔数组 . 将它们全部设置为false .

    • 运行bogosort的迭代

    • 选择两个随机元素 .

    • 如果两个元素相对于彼此排序（i <j && array [i] <array [j]），则将布尔数组上的两个索引标记为true . 过度，重新开始 .

    • 检查数组中的所有布尔值是否均为真 . 如果没有，请返回3 .

    • 完成 .

    回复于
  • 1

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

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

    我正在研究的一个问题涉及选择两个随机点，如果它们的顺序错误，则将它们之间的整个子范围反转 . 我在http://richardhartersworld.com/cri_d/cri/2001/badsort.html上找到了算法，它说平均情况可能在O（n ^ 3）或O（n ^ 2 log n）附近（他不太确定） .

    我认为有可能更有效地做到这一点，因为我认为可能在O（1）时间内进行逆转操作 .

    实际上，我刚刚意识到这样做会使我所说的全部内容可能是因为我刚刚意识到我想到的数据结构会将随机元素访问到O（log n）并确定它是否需要在O（n）处反转） .

    回复于
  • 279

    Randomsubsetsort .

    给定n个元素的数组，选择概率为1 / n的每个元素，随机化这些元素，并检查数组是否已排序 . 重复直到排序 .

    预期的时间留给读者练习 .

    回复于

相关问题