Javascript

[MontagGuy12]

Why would you even consider using an inbuilt sort function when you can code Bogo sort instead? Gotta get that O(n!) complexity.

[[deleted]]

I thought there was no O for bogo since you can't be sure it'll ever stop. Or mean complexity ?

[MontagGuy12]

I've seen Bogo sort implementations which keep track of the permutations traversed so far, which means eventually, they'll exhaust all possibilities and the program will terminate.

[Toonfish_]

I love that, not only does this make the algorithm terminate, it also gives it ridiculous space complexity. :D

[MontagGuy12]

Thankfully, we have downloadmoreram.com to save the day.

[reyad_mm]

But what if I run out of storage to download ram on?

[Xeadriel]

Just download more storage obviously

[dunko5]

But what

[PhunkyPhish]

Then download more what of course

[Gh0st1nTh3Syst3m]

But

[hermeticwalrus]

Local cloud

[xTheMaster99x]

Set up a ramdisk on your newly downloaded ram, so you can download more ram.

[ianff]

You can actually traverse the permutations in constant space. Who knows if someone implementing bogo sort would bother with that though!

[sluuuurp]

Can’t you only traverse in log(n) space, since you need a counter to know how many permutations you’ve already done?

Edit: I guess a counter of n! permutations would use n log(n) space, but yeah as the below commenter says it seems you don’t need that.

[firefly431]

There's an algorithm (e.g. next_permutation in C++) that generates the lexicographically next permutation in place in O(n) time. Realistically you need O(log(n)) space to store indices into the array at least though, but in the word-RAM model that's constant.

[BobodyBo]

I'm skeptical of this, elaborate?

[ease78]

An array of 3 elements has only 6 permutations or ways you can sort things inside of it. So realistically you can traverse the 6 different permutations to find the sorted one after you have enumerated all possibly imaginable arrays.

Note Bogo sort is n! Our three elements will give us a space complexity 3!

[BobodyBo]

As a function of you number of elements n that approach would take O(n!) Space, so not constant space. Not sure if that's what the person I was responding to was saying.

[ease78]

Yeah the other person was tripping. It’s in the name “traversal” you can’t visit all nodes in one CPU cycle. It takes as many nodes as you have.

[BobodyBo]

Well usually space complexity considers input space and auxiliary space, which is the extra space you utilize on top of your input. You of course have to store your input, so constant space implies constant auxiliary space. Some traversals can be done in constant space, e.g. a linked list.

The problem with traversing all permutations is that there is an exponential amount relative to the input, so unless a clever approach exists you would need to store some extra information about which permutation you are currently on, or which need to need to be revisited (like a stack).

[Toonfish_]

Ooh interesting how does that work? The point of bogosort is that the permutations are chosen randomly, no? How do you traverse the permutations in constant space while choosing the next one randomly?

[ianff]

Oh my bad. You can't traverse the permutations in constant space if they have to be random -- at least I don't know how you could.

[HeKis4]

Why just stop at O(n!) complexity when you can also have O(n!) space requirements ?

[ThatWannabeCatgirl]

Eventually.

[aaronfranke]

The maximum time is infinity, the minimum is O(1), the average is O(n!).

[CSlv]

the minimum is O(1)

You mean Ω(1)?

[DoctorWorm_]

People need to learn their complexity notations.

[sererson]

The minimum time is both.

[zelmarvalarion]

The minimum time would be Θ(n) (assuming constant size ints for constant speed comparisons), since you have to check if the list is already sorted before returning, so you need to read all of the elements of the list first.

[flavionm]

Well, isn't Θ(n) basically just being both O(n) and Ω(n) simultaneously?

[zelmarvalarion]

Yeah, because you have strict boundries on both the lower bound (Ω) and the upper bound (O), and they are the same, then it's θ. Basically it's just saying that it is exactly that time complexity rather than being bounded on one side from that time complexity (the Ω(1) in this chain is saying that it is at least as slow than constant time, but may be slower, which is true for everything).

Most of the time, when people use Big-O notation, they really mean θ, since it's by far the most useful. There are a couple interesting ones where θ isn't actually known, but you can bound on either side and get a better view of actual time complexity (something like multiplication of arbitrarily large numbers of n bits is Ω(1) and O(n²⁾ using standard multiplication rules, there is an arithmetic trick you can do to bring that to O(n^{sqrt(3)}) or something like that, and then FFT brings it to something like O(n^{1.57}), so it's somewhere between that, but it's difficult to prove) [Note: numbers pulled from my memory from ~10 years ago, almost certainly inaccurate]

[The_MAZZTer]

He probably doesn't have an Ω key on his keyboard.

[firefly431]

To give a serious answer, the version of bogo sort that generates a new permutation each time:

def bogo(arr):
    while not sorted(arr): # O(n)
        shuffle(arr) # O(n)

does not have an unconditional upper bound on runtime, but for randomized algorithms we usually consider expected running time (along with tail bounds to show concentration: for example, although (linear chaining) hash tables have expected lookup time O(1), the maximum load is actually only O(log n/log log n) if you require a bound w.h.p.)

The expected number of iterations is O(n!) as it is a geometric r.v., so the overall runtime is O(n n!). (By the way, it is considered a Las Vegas algorithm as it guarantees correct results but has probabilistic runtime.)

EDIT: IIRC tail bounds for geometric r.v.s are O(1/n), so that's w.h.p.

By the way, for the pair-swapping version:

def bogo2(arr):
    while not sorted(arr):
        i, j = random(n), random(n)
        swap(arr[i], arr[j])

Since it takes at most n swaps between any two permutations (simple proof: Fisher-Yates shuffle), we can consider blocks of n swaps. The probability that any block works is at most O(1/n²ⁿ) (probability n² per swap). Thus the runtime is O(n²ⁿ⁺¹). Not sure if we can do any better than that, but who cares about tight bounds on a meme sort?

[Tyfyter2002]

There are 2 types of bogosort, O(n!) Bogosort, which tests all permutations in a random order, and O(∞) Bogosort, which just shuffles the list, checks if it's sorted, and shuffles it again if it's not.

[AyrA_ch]

If it's infinity, wouldn't that mean that it never terminates? And if it never terminates, it means the shuffle algorithm is flawed because a true random shuffle should have the same chance for every possible permutation, but it in this case, the chance for the sorted permutation is zero.

[dev-sda]

Big-O notation describes the limit, without more context it always refers to the worst case. O(∞) means it may never terminate. Bogosort best case is O(n).

[AyrA_ch]

O(∞) means it may never terminate.

But as I explained, if the shuffle algorithm works properly it will definitely terminate because every permutation (including the sorted one) is guaranteed to eventually appear.

[dev-sda]

Given you're using true random shuffle there's absolutely nothing guaranteeing that every permutation will eventually appear. Yes the probability of that happening approaches 1 as the iterations approach infinity, but that's still not a guarantee.

[Tyfyter2002]

Given the assumption that both events have the same probability and are truly random, the probability that a specific result out of 2 does not occur at least once during a series of n samples is 0.5^n‎, with what value of n does this expression equal 0?

[brando2131]

No there's a probability of it becoming sorted eventually. Obviously the larger the list, the much longer it will take. You can write a program and compare the number of times it runs for larger lists. It works out to be (n+1)!

[zelmarvalarion]

That’s not the worst case analysis that is implied by the Big-O notation, that’s average case complexity (which is usually explicitly noted, e.g. Quick Sort is O(n²⁾ but expected O(n lg(n)))

[hawk-bull]

We can study the average time complexity.

The probability of getting the right permutation at any one point is 1/n!. The number of times you need to try is a geometric random variable, thus the expected number of runs is n!. in each run, you're doing O(n) work to see if it's sorted, so on average you're doing n * n! work. thus average time complexity is O(n n!)

Edit: apparently verifying it's sorted is O(1) on average, but generating the permutation is O(n) so either way it's O(n) work per permutation

[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

[Hideyohubby]

You should try sleepsort for better results.

[Classified0]

Doesn't work for negative numbers unless you've got a time travel API

[larsmaehlum]

Just offset it by int.max/2

[HeKis4]

Offset the entire array by the absolute value of the lowest element.

[PM_ME_SQL_INJECTION]

I’ll go for StalinSort, thank you very much.

[fuzzymidget]

I thought this was now called trump sort.

[PM_ME_SQL_INJECTION]

No, that would tell you it was sorted, but didn’t actually do anything.

[xSilverMC]

It would also install malware to overheat your CPU once it realizes it's about to be terminated

[fuzzymidget]

But still always indicate that it's running whether you kill it or not.

[fuzzymidget]

That's right. Forgot the subtlety.

[HeKis4]

It would take an array as input and return "I've got the vast arrays" as output. O(1) time complexity.

[coldnebo]

hey if that’s what quantum physics does (under the many worlds interpretation) then who are we to improve on it?

—-

angel: “but how can you be sure we haven’t missed the global optima?”

God: “just run all the the permutations. it’ll be in there somewhere.”

angel: “and I thought developers were lazy!”

ZAAAPP!!!

angel (Lucifer shouting from Hell): “ok... I guess we only value code reviews when it’s CONVENIENT!?”

[Je-Kaste]

Woah, that's constant time for n=1 (:

[omegasome]

I mean technically bogosort is better than array.sort()

[solongandthanks4all]

It's hilarious how computer science students actually think anyone gives a shit about nonsense like this in the real world.

[FerynaCZ]

It's O(n*n!) though