Talk:Bogosort

Archived talk: until 16 May 2009

Let's move this article into a new article called Frivolous sorting algorithms

The additional algorithms here are written up cleverly and interestingly, and are of at least passing interest to computer scientists, but do these really belong on the Bogosort page? We already have a "computer humor" category from which Bogosort is linked; how about a new entry for "Frivolous sorting algorithms", and move all the content from here into that entry? Bogosort could redirect. Johnwbyrd (talk) 20:25, 14 September 2016 (UTC)

Worst-case complexity

Is it really O(Infinity)? That seems to imply that in the worst case it will never be sorted; but if it is run indefinitely it must eventually be so... 173.57.168.166 (talk) 06:01, 1 November 2010 (UTC)

Well... from what I know, yes it is really O(∞). In this case, "Worst case" means taking the least effective action each time. At least, that's how I interprate it. Although you are correct in that realistically, it will eventually get sorted. 173.24.183.93 (talk) 03:17, 17 November 2010 (UTC)

The only actions taken are shuffling the list, and checking if it is in the correct order. There is no guarantee that a single random shuffle will result in the correct order, and each shuffle is independent of the previous one, so in the worst case the correct order would never be achieved. --Joshua Issac (talk) 08:36, 18 May 2011 (UTC)

Yes, there is a guarantee. The probability that the algorithm will terminate is 1. The expected runtime is less then (n+1)!. The algorithm is thus positive almost sure terminating (sometimes also called bounded almost sure termination). Thats second strongest criterium for probabilistic algorithms there is for termination (only followed by certain termination). You may have a misconception of 'worst case' runtime. Worst case only references to the input of your algorithm. Phrased differently: What is the runtime of the algorithm for the worst input you can find? The random bits however are not part of the input. They are separate objects. I don't know any source that handles random bits as part of the input. If you have any source that implies otherwise, I would be grateful for this. PhoenixIra (talk) 08:26, 29 May 2020 (UTC)

Two-element list

I don't think "For dealing with a list of two elements, this places Bogosort amongst the best sorting methods: one comparison, and then either it finishes, or else there is one swap and one more comparison" is right. Even for a two-element list, the number of iterations (and thus running time) is unbounded; for any given n it is possible for the sort to last more than n iterations.

Maybe I don't know what it's trying to say. Superm401 - Talk 09:55, 22 May 2009 (UTC)

You are correct. This analysis depends on the shuffle explicitly excluding the identity permutation, which is typically not the case with the bogosort. The Gruber, et al. reference does analyze two forms of the bozo-sort, one of which (referred to in the paper as bozo-sort+) does explicitly exclude the null swap, but nowhere does that reference discuss the two element list case. I have removed this unsourced and arguably incorrect analysis. -- Thinking of England (talk) 03:58, 25 July 2009 (UTC)

Questionable etymology

The article currently states that the sort "is named after the humorous term quantum bogodynamics and, ultimately, the word bogus." I can't find any reference for this; it seem more likely that both "bogosort" and "quantum bogodynamics" derive directly from "bogus". The "quantum bogodynamics" connection was first added in this unsourced edit. -- Thinking of England (talk) 19:56, 24 July 2009 (UTC)

"the quantum randomization spawns an infinite array of universes"

Only 2^{number of random bits}. --Dc987 (talk) 08:55, 21 November 2009 (UTC)

Example explosion

By now, the longest part of the article presents implementations of the algorithm in different programming languages. Wikipedia is not a dumping ground for code, and in my opinion this does not go along with WP:NOTDIR, WP:UNDUE. Notice that we had a similar case at Talk:Depth-first_search#Example_explosion because numerous eager programmers flooded the article with implementations in various languages. There consensus was to remove these implementations.

I think the best would be to remove the section "Implementations in different programming languages". Maybe we can donate the implementations to some wikibook project. If someone feels the need for kepping a reference implementation, I'd suggest keep the implementation in Python OR in Smalltalk, and to put this into the section "description of the algorithm". These are reasonably short, and no particular skills in the respective programming language are needed to understand the code. Hermel (talk) 18:22, 14 September 2010 (UTC)

What is added by the various example source files? Other than the pleasure of seeing a version in one's favoured language, and comparing it favourably to the versions in the other languages, that is. Most of the text involved is gibberish required by the various syntax features of each language. The pseudocode surely is clear and shows all that need be shown. The only delicate point is that the test is performed before the shuffle (as opposed to Repeat shuffle(deck) until InOrder(Deck);) so that the sort will stop on an already-sorted deck. NickyMcLean (talk) 22:16, 14 September 2010 (UTC)

I have requested that the section on algorithm implementation be imported to wikibooks, they already have a redlink article on implementations of bogosort in various programming languages. See wikibooks:Requests_for_import#Bogosort. If no one objects, I think we can remove the section after the import over there has taken place. Hermel (talk) 19:00, 16 September 2010 (UTC)

In spirit of the above discussion, I also moved the C++ implementation provided by user .oisyn instead to wikibooks.

Best case complexity

The best case sorts in one step, shouldn't that be denoted as O(0)? AttishOculus (talk) 06:55, 7 December 2010 (UTC)

No, even if the list is already sorted, you need to walk it to know you're done. Testing if an n-elements list is sorted requires at least n-1 comparisons. Thus an O(n) best case complexity. This is actually a limit for any sorting algorithm. -- 86.71.9.237 (talk) 05:45, 5 January 2011 (UTC)

Other implementations

http://robsort.org/ - multithreaded, so massive parallelization would make it somewhat more efficient than Bogosort. — Preceding unsigned comment added by 207.171.191.61 (talk) 21:27, 14 February 2012 (UTC)

Quantum BogoSort explanation

Why was this removed? I think this more clearly explains how Quantum BogoSort is supposed to work: " The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer destroys the universe — implementation of this step being left as an exercise for the reader. The only observers will then be in the surviving universes and will see that the randomization worked the first time and that the list is in sorted order." — Preceding unsigned comment added by 199.46.198.232 (talk) 18:49, 24 April 2012 (UTC)

How does the Shuffle Algorithm Work

The shuffle method is important, because any code written is likely to employ pseudo random numbers. For any list, the bogosort algorithm will either eventually sort the list, or otherwise eventually find itself with the list in the same order as when it started AND independently happen to have the pseudo random generator seeded to the same value - after which the exact same set of operations would occur over and over again, with zero chance of success. I quote from the piece 'For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the infinite monkey theorem holds' - Actually that can only be true if you have true random numbers for swapping, or at least a sequence of pseudorandom numbers that is not repeating.

The infinite monkey theorem itself might not be true (as assumed here to tend to a prob of 1 as N tends to infinity) - for any monkey there may be some reason why the sequence of key presses for success is not possible, although it's hard to see why that might be, but it's also hard to disprove via experiment.

Back to the bogosort, Let's say I've got a sequence of 10^10 pseudo random numbers, but I'm sorting a list of 50 with 2x10^64 possible orders - the chance that I can get to the 1 sorted order before I encounter one of the unsorted orders more than once, and with the pseudo random seed in the same position, is looking slim - because when I reach the sorted state, probability says I've visited a vast number of other states 2 or more times. Gomez2002 (talk) 16:30, 14 April 2015 (UTC)

Quantum bogosort

ʘx (talk · contribs) removed the following content from the article without an adequate policy-based explanation (nowiki tags added by me):

{{anchor|Quantum bogosort}}Quantum Bogosort

An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n).<ref>[https://web.archive.org/web/20140704040258/http://www.mathnews.uwaterloo.ca/Issues/mn11103/QuantumBogoSort.php archived version of mathNEWS Issue 111.3: Friday, October 23, 2009 - Quantum Bogosort]</ref> First, use quantum randomness to permute the list. The quantum randomization creates n! branches of the wavefunction ("universes" in many-worlds interpretation), and one of these will be such that this single shuffle had produced the list in sorted order. The list is then inspected, and if it is not sorted, the universe is destroyed. Since destroyed universes cannot be observed, the list is always observed to have been successfully sorted after one iteration in O(n) which is just the time needed to verify that the list is sorted. Besides the impracticability of this algorithm, it is also not technically possible. Permuting n! items requires n*log(n) bits of randomness (see Stirling's approximation), so the algorithm would require O(n*log(n)) time. Beyond this, quantum computers do not actually offer a way to "destroy a universe": doing so would offer an algorithm for quantum computers to run NP-complete problems in polynomial time, a task which is widely suspected to be impossible. Instead, they can only "destroy possibilities" through quantum interference, yielding the complexity classes EQP and BQP. If destroying the universe is interpreted as killing all life, e.g. via nuclear winter, then the algorithm can work in O(n*log(n)) time through the anthropic principle.

Discussion about the validity of the removal is taking place at User talk:ʘx#Quantum bogosort; this text dump is provided for convenience and should be used mainly for revision of the actual content. --SoledadKabocha (talk) 05:16, 1 September 2015 (UTC)

To update the status: ʘx contends that quantum bogosort is unsuitable for any existing Wikipedia article, either this one or Quantum sort, because it fails to meet the definition of an algorithm and the provided citation does not adequately address this concern. (Presumably this has to do with its status as an unimplementable joke, because it depends on a dubious concept of destroying the universe, but I don't see why we couldn't just write a more rigorous definition.) ʘx has not provided my requested clarification and seems uninterested in continuing the discussion further. --SoledadKabocha (talk) 18:55, 5 September 2015 (UTC)

I have added {{missing information}} to the article as a courtesy to give readers a chance of finding this talkpage discussion. I intend to address ʘx's objections on his/her user talk page shortly. --SoledadKabocha (talk) 23:55, 1 November 2015 (UTC)

Concerning published references, I recall a short SF story (in Analog magazine, I think) that concerned the commissioning of a new high-power particle accelerator, whose full-power switch-on attempts were every time foiled by ever-more-unlikely mishaps: an explosion at the electricity substation, an airliner crashing into the building, etc. Eventually, a theorist came forward with a new analysis that suggested that activation would lead to a (bafflegab) that would destroy the universe, and so, evidently, only in those universes wherein some event prevented activation were there any longer observers to puzzle over events. Evidently, this notion is widespread. The sequence of mis-starts at the new CERN accelerator caused some amusement, especially when various theorists affirmed a firm belief in no possibility of universal implosion, just as they had in the story. An earlier such story concerned the impending test of a new "super" atomic bomb, that some feared might set the atmosphere alight (nitrogen and oxygen combining) NickyMcLean (talk) 09:54, 2 November 2015 (UTC)

Thank you for your attention, but I believe any added source would need to be a serious academic paper. See ʘx's user talk page for more technical details. --SoledadKabocha (talk) 03:40, 3 November 2015 (UTC)

I should probably elaborate on the technical issues. No one is objecting to the validity of quantum sorting or of quantum computing in general.

The contention is that quantum bogosort fails to qualify as a function and therefore an algorithm; since the scopes of this article and of Quantum sort are limited to sorting algorithms, the material is thus unsuitable for either article. This implies that we should split the quantum-bogosort material into its own article, being very careful not to describe quantum bogosort as a function nor an algorithm. (Quantum bogosort is currently a redirect to this article.)

I am not entirely clear why this is the case, as any method of sorting has one correct output for any given list as input. Our definition of a function depends on that of a binary relation, which does not appear to impose physical constraints on the computer implementation of the relation. (see below)

The problem seems to me more that we (Wikipedians, or possibly academia) haven't specified certain key steps of the process rigorously enough. For example, the issue of distributing n! unique permutations over the states of the quantum processor seems as much a question of physics as that of destroying the universe. (This may be trivial in the many-worlds interpretation, but in other interpretations of quantum mechanics, the specific answer would be different.)

I see no evidence that such a specification is impossible; I wonder whether we could define a classical simulation of quantum bogosort, using a computer sufficiently parallel to check n! lists for sortedness simultaneously, and rigorously relate that to an actual model of quantum computing somehow. That is why I say this is a sourcing issue. --SoledadKabocha (talk) 19:32, 3 November 2015 (UTC)

After thinking hard about it for a while, I see the following justification: From the perspective of a universe an infinitesimal time before its destruction, it would appear that a quantum bogosort has not returned any output. Hence in that universe, quantum bogosort fails to be left-total, hence fails to be a function. It then is no longer meaningful to decide whether it is effectively calculable, so it fails to be an algorithm, hence fails to be a sorting algorithm. --SoledadKabocha (talk) 20:27, 3 November 2015 (UTC)

I don't see that whether or not quantum bogosort is a function, or an algorithm is so relevant. It can be included in this article because of its name. However we do need to have a reliable source. It does not need to be an academic source, but should be something to show it was not just made up one day for inclusion in this article. It would be even better if the source could tell us if it was an algorithm, or a function rather than relying on original research. Then the facts can be included in this article. Graeme Bartlett (talk) 22:13, 3 November 2015 (UTC)

Ok, thanks. Admittedly I oversimplified a bit - my point was mainly that the specific source mentioned by NickyMcLean would not be sufficient.

Again, the technical discussion on how much the word "algorithm" should define the scope of the relevant article(s) is taking place at User talk:ʘx#Quantum bogosort, but I'm not sure of the most policy-compliant way to unify the split venues. --SoledadKabocha (talk) 22:41, 3 November 2015 (UTC)

In summary

To be clear, I am no longer involved with the discussion on ʘx's talk page.

The issue of which I am aware is that we do not have a source to support the choice of any specific formal system in which to define quantum bogosort and relate it to the underlying concept of a sorting algorithm. Until that is resolved, according to ʘx, it is meaningless to make any statement about quantum bogosort other than that it consists informally of a certain sequence of informal steps or that it is formally ill-defined.

As NickyMcLean seems to have a general interest in computing but no clear experience with this particular topic, I felt it was proper to apologize for dragging him/her into our overly verbose discussion. My post on his/her talk page contains a slightly longer summary of my actions within the discussion. --SoledadKabocha (talk) 03:27, 17 November 2015 (UTC)

Provoked by all the talk, I tracked down some specific references employing the "destroy universe" computational trick: Doomsday Device by John Gribben (Analog Science Fiction/Science Fact, February 1985), and Games, Puzzles and Computation by R.A. Heam and E.D. Demaine (2009), page 103-4, for example. Considering that W. has a rule "Ignore all rules" (including this one) with a view to inclusivity, I don't see any real need to be so picky over an approximate description in the absence of a formal one. Nor is there an agreed formal system to express it within. Readers of the (currently removed) text could well discern a meaning, and in the usual manner. NickyMcLean (talk) 11:40, 17 November 2015 (UTC)

I think a large problem here is that "quantum bogosort" will never be an interesting "algorithm" from a computer scientific perspective -- a lot of the physics doesn't even make sense from a quantum mechanical perspective, e.g. "destroying the universe" will entangle the computer with the outside world, etc. I don't think anyone will have luck here arguing for it on the basis of being computer scientifically interesting. But it is notable in that it's a common joke, often mentioned in intro quantum computation classes, or sometimes jokingly when lecturing on diverse sorting algorithms. We have an article on spaghetti sort that seems to be there for the same reason. (A lot of the physical demands of spaghetti sort are many times more implausible than quantum bogosort. For instance, spaghetti sort requires exponentially large distinguishable spaghetti rods to represent n bits, which will easily end up creating a blackhole; if it were to not, it would still require faster-than-light communication to fall to the table. I would much rather be tasked with destroying the human race.) Quantum bogosort is a subject of popular culture that seems worth discussing, if not a subject of classical algorithms. Timeroot (talk) 22:30, 27 November 2015 (UTC)

Accuracy disputed

This article confuses two algorithms: what logic programmers call bogosort, and what other apparently call bogosort. The logic programmer's definition is:

sort(I, P) :- permutation(I, P), sorted(P).

Read: "systematically generate all permutations, one by one, until you find one that is sorted". This algorithm has a worst-case running time of O((n+1)!) for an n-element input, not unbounded time like the randomized version. QVVERTYVS (hm?) 22:07, 5 November 2015 (UTC)

As a CS major somewhat familiar with logic programming, I have never ever seen bogosort defined this way. Can you cite a source for the above definition? Zowayix001 (talk) 02:19, 28 January 2016 (UTC)

Here is a university homework assignment that describes the Prolog algorithm as a deterministic bogosort. Interestingly, it also points out the connection. I'll update the article. QVVERTYVS (hm?) 09:42, 28 January 2016 (UTC)

Dead Link

Under example links, the github link to the Bogosort example in C is no longer valid. Profsquid (talk) 10:31, 4 January 2017 (UTC)

The ML implementation is not very efficient

So I noticed that the Standard ML implementation doesn't use a very good shuffle algorithm. Using List.revAppend is nice but it only reverses the first component of the partitioned list. If you're sorting lots of reverse-sorted lists with this implementation, it's going to take a long time for the rightmost elements to random walk over to the left where they can start being shuffled properly. This could really bite someone who's using our example in their production code! What do people think about adding an additional List.rev like this?

fun shuffle xs = List.revAppend (List.partition rand (List.rev xs));

.froth. (talk) 16:28, 20 July 2021 (UTC)

I was going to ask here if more than one language are actually necessary, seems like cruft (WP:LC). Also no one should realistically use bogosort "in production". Chininazu12 (talk) 09:48, 26 July 2021 (UTC)

I was joking... and I actually agree about not needing multiple implementations in the article. The Python example is clearer, even for someone who doesn't know Python, and dodges the ML example's issue with the sketchy shuffle algorithm. I'll remove the ML code. .froth. (talk) 23:02, 26 July 2021 (UTC)

Portmanteau ?

The article claims "Its name is a portmanteau of the words bogus and sort." But it isn't! So either this article is wrong or the definition of a portmanteau word is wrong. bogUsort would be a portmanteau word, for example. — Preceding unsigned comment added by 88.97.62.77 (talk) 20:07, 27 February 2023 (UTC)

Well may be it is from bogon or bogosity, but it's close enough. Graeme Bartlett (talk) 00:50, 1 March 2023 (UTC)

miracle sort best case

I think, the best case of miracle sort is O(n), which happens on a sorted list. 84.151.247.140 (talk) 12:07, 24 May 2023 (UTC)