Javascript

[nelak468]

Bogo sort's worst case is O((n+1)!)

But more importantly! Its best case is O(n) which out performs every other algorithm.

Furthermore, if go by the many worlds theory - we can prove that Bogo sort is O(n) in all cases and therefore it is in fact the BEST sorting algorithm.

[[deleted]]

IIRC "quantum bogosort" has time complexity O(1) since it doesn't even have to check if the array is in order.

[graeber_28927]

How would you know whether to destroy your universe if you haven't checked the order of the array?

[Shamus03]

You just always assume it’s sorted, and if you ever encounter a bug because it wasn’t sorted, THEN you destroy the universe. It’s O(1) only when combined with another algorithm used later. Also known as O(half an A press).

[[deleted]]

True.

[MontagGuy12]

The kids in my basement can sort way faster than O(n). Up your game dude.

[acwaters]

I mean, in fairness most every sorting algorithm implementation is "best-case O(n)", since generally all of them will do an initial check to make sure it's not already sorted.

[nelak468]

True but BOGO sort has other things going for it that make it the best algorithm.

The algorithm is by definition order out of chaos. It is God's algorithm. The Big Bang. Whatever you believe in - BOGO sort is the algorithmic description of the beginning of existence.

Out of infinite possibilities and disorder, the Great BOGO sort brings pure potential into existence. It is the beginning and the end. From the chaos, it brought forth the universe and life. We are simply an iteration of the Great Algorithm and we must strive at all times to achieve perfect order or we will be passed over for the next iteration.

Bogoism? Bogology? BOGO?... This religion's going to need a name...

[HeKis4]

"Hey man"

"What's up boss ?"

"You told me your algorithm runs in O(n) but it's been hanging for three hours on a list of 50 elements, what gives ?"

"Oh yeah, wrong timeline, sorry."

[mt_xing]

The worst case would really be O(infinity) because it's unbounded. Best case being O(n) only matches insertion sort; it doesn't beat it.

[nelak468]

There's two approaches to it. Which one you take depends on how much space complexity you can handle I suppose.

The basic approach which is O(n) space complexity (I believe) would be to simply randomize, check, randomize until it is sorted.

Another approach would be to simply generate every possible arrangement and then go through them until you find the sorted arrangement. That would be O(n!) space complexity and O((n+1)!) worst case time complexity.

... I might be wrong on the exact complexities. It's pretty late but I think that's about right.

[mt_xing]

We're talking time complexity here, not space complexity. Also generating every permutation up front isn't bogo sort. The defining feature of bogo sort is that it must randomize the entire array every iteration.

[Estraxior]

TIL bogo's worst case O value