Is this the simplest (and most surprising) sorting algorithm?

Re:Is this the simplest (and most surprising) sorting algori... by CaptainNegative on Tuesday October 05, 2021 @12:39PM (#28761826)

Shuffling is even less tricky if you're not trying to do it in place, if you're not trying to do it in linear(ithmic) time, or if you're not trying to induce a uniform distribution over all permutations (but rather just want some positive probability for all of them). Relaxing any combination of these conditions works just fine for Bogosort.

[ Parent | on HN ]

Re:Is this the simplest (and most surprising) sorting algori... by infinisil on Tuesday October 05, 2021 @01:04PM (#28762192)

It would even suffice to just swap two random elements every iteration!

[ Parent | on HN ]

Re:Is this the simplest (and most surprising) sorting algori... by 6510 on Tuesday October 05, 2021 @02:33PM (#28763593)

My gut says that combining that with other sort cycles in some magic ratio could do magical things. I'm quite wrong quite often ofc but the adventure is out there!

[ Parent | on HN ]

Re:Is this the simplest (and most surprising) sorting algori... by a1369209993 on Wednesday October 06, 2021 @09:44PM (#28780809)

Fun fact: Fisher-Yates samples a uniform distribution over permutations and is therefor capable of producing any permutation, so you can sort any array in linear time using Fisher-Yates with its RNG replaced by a appropriate oracle. (So the complexity of sorting a array mostly reduces to the complexity of determining which permutation it's in relative to a sorted version.)

[ Parent | on HN ]

Re:Is this the simplest (and most surprising) sorting algori... by innocenat on Tuesday October 05, 2021 @01:30PM (#28762625)

I think most C++ implementation of bogosort use std::next_permutation

[ Parent | on HN ]