[1185] Ineffective Sorts

Title Text:StackSort connects to StackOverflow, searches for ‘sort a list’, and downloads and runs code snippets until the list is sorted.<

Origin:https://xkcd.com/1185/

https://www.explainxkcd.com/wiki/index.php/1185:_Ineffective_Sorts

漫画给出了用伪Python编写的四种非功能排序算法的例子。

第一种是未完成的合并排序。合并排序通过将列表分成两半并对每一半执行合并排序来递归地工作。在对这两半进行排序之后,它们被合并,利用这两个半部现在处于正确顺序的事实,因此可以有效地完成合并。漫画中合并排序的作者似乎已经放弃了编写排序的排序合并部分,这就是为什么它是一个半心半意的合并排序,而是连接半部而没有排序。在当前状态下,排序会将列表划分为大小为1的元素,然后按原始的未排序顺序重新组合它们,但是在嵌套列表中 – 使原始数据更难以使用。作者承认这个失败的评论“嗯……在这里。抱歉。”

第二种是bogosort的“优化”变体。标准bogosort通过随机改组列表中的元素直到它们被排序为止。在评论中,作者指出这种bogosort变体在O(n log(n))中运行,而标准bogosorts实际上在预期的O(n!n!)时间内运行,但可能永远不会完成。 bogosort的这种变体完成得非常快,因为在大多数情况下它实际上并没有对列表进行排序,而是报告操作系统中的虚构错误(“内核页面错误”),如果在洗牌后没有对列表进行排序(n)倍。 bogosort是“优化的”,因为在最坏的情况下,没有比较排序算法可能比O(n log(n))做得更好。

第三种模式是一位程序员在求职面试中解释快速排序。快速排序的工作原理是选择索引作为枢轴值,并在枢轴之前排序小于枢轴的所有元素,并且在枢轴之后排序大于枢轴的所有元素。然后它会快速分配到小于枢轴的部分和大于枢轴的部分,直到整个列表被排序。受访者挣扎了一会儿,然后问他们是否可以使用标准库来召唤快速排序。笑话是,标准库包含一个快速排序,程序员宁愿依赖它(可能甚至将其作为自己的工作传递)而不是他自己的快速排序示例。

最后的那种只是一团糟。首先,它检查列表是否已排序,如果是,则退出。然后它将列表随机旋转10,000次(就像切割一副卡片一样),如果列表被排序则退出。接下来,在绝望中,它检查列表是否排序三次。最后,作者意识到他们没有成功的机会,他们执行计算机相当于Rage Quit并试图摧毁计算机而不是承认失败。首先,程序尝试在五秒钟内安排关闭计算机,然后尝试删除当前目录,然后尝试删除用户的主目录(可能是平地机的文件),最后是计算机上的所有文件。 rm是POSIX命令; -r和-f标志表示remove命令将删除指定目录的所有内容,并且不会事先提示用户。在“可移植性”的幌子下,程序运行等效的Windows rd命令,并在没有提示的情况下从“C:”驱动器中删除所有文件。最后,程序按顺序返回包含数字1到5的列表。

在标题文本中,StackOverflow(链接)是一个问答网站,程序员可以在这里询问和回答关于编程的问题。这段代码的作者充分利用了StackOverflow上的某个人知道他们正在做什么的希望,并发布了代码来排序列表……并且有人实现了stacksort;好吧,有点儿。

You May Also Like

More From Author

Leave a Reply

Your email address will not be published. Required fields are marked *