The Sorting Algorithm That Never Ends! (Bogo Sort?)

The Sorting Algorithm That Never Ends! (Bogo Sort?)

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[CoolKnight]

Quantum bogo sort fixes this by destroying all universes with the incorrect order after randomizing. You need to make sure the randomizer is truly random though or you will destroy all universes.

[DominoPivot]

I think O(infinity) isn't a very useful notation. An efficient algorithm with one uncovered edge case would be O(infinity). I prefer the phrase unbounded O(n × n!) algorithm.

This is called Bogosort, and David "Dangermouse" Morgan-Mar humorously made into the even worse Bogobogosort which is supposedly an unbounded O(n! ^ n-k)...

[noddle]

Of course there’s a sorting algorithm of O(infinity). Swap the first two elements repeatedly infinitely (assuming this doesn’t sort the array).

[pchurch]

I also have made an O(infinity) sorting algorithm (forgot a base case in bubble sort)

[unlucky-]

Worst case that worst case this, IT HAS POTENTIALLY SORT ANYTHING IN O(1)

[nelmatrix]

No this isn't infinite. The reason is because the list or collection itself is finite, therefore no matter how much random arrangements you perform, you'll never exceed the maximum mumber of permutations possible. As s result, the worst case will be the last possible permutation which is the hitting point.

[not_vinkami]

I've just made another O(inf) sorting algorithm in python
def sort(array):
while True:
pass

[MatthewIrizarry-]

ACTUALLY… O(infinity) is incorrect… In your example, there are 5 elements. We then have to ask ourselves, how many ways can it be sorted. This is simply 5!, as there are 120 ways to arrange these numbers. Next, assume that we do a linear search for each arrangement. This is 5!*5. If we had 7 elements, it would be 7!*7. See the pattern? It is O(n*n!) because the constant basically does not matter in comparison to the growth of the factorial. You can check this using the limit asymptotic theorem. However, this involves some incredibly high level math, as attempting to use said limit definition requires you to take the derivative of n*n! which involves the gamma function. Anyways, the runtime of BOGO sort is O(n!)

[divine]

Not super familiar with big O notstion, but pretty sure the more correct time complexity would be O(omega). Dont remember the strict definition of omega perfectly, but i think it was just a more mathematically rigorous way of saying an arbitrarily large finite number. The best video on this ofd the top of my head was from someguy who made chess on an infinite board, called infite chess, talking about mate on omega

[justplay]

Not infinite given enough time it will sort it eventually

[hnk]

try quantum bogosort which can sort any list in O(1), using the "many worlds" interpretation of quantum mechanics.

It works as follows:

1. Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway.

2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)

3. All remaining universes contain lists which are sorted

[Ноунеймбезгалочки-мч]

if you want O(1) space use inserting sort

[luisgmzz_]

correct me if I'm wrong but inf is not a complexity order, or if it is, is equal to 1, cause it's not a function in terms of the elements of the array, if anything it would be a constant

[saranshthukral]

Permworm until everything become dust, mud and opaque big burger patty sorting
W algo

[zullendale]

This one is called Bogo Sort, but Miracle Sort and Intelligent Design Sort are slower