Re:Bubblesort, rocksort, and cocktail-shaker sort
by steerablesafe on Wednesday December 16, 2020 @06:38AM
(#25441439)
Also you you need "real" (in the quantum sense) random generator for the shuffling. If you use a PRNG then you risk destroying all the universes.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by taneq on Wednesday December 16, 2020 @07:04AM
(#25441609)
You could always just use a pseudorandom number generator and rely on bit errors to generate the different potential sort orders. ;)
Re:Bubblesort, rocksort, and cocktail-shaker sort
by steerablesafe on Wednesday December 16, 2020 @10:03AM
(#25443349)
If you add bit errors to the picture then the check after shuffle spuriously passing has a significant, potentially much higher probability than a bit error introducing new, previously impossible random shuffling and producing a sorted sequence. So in a significant portion (maybe most) of the non-destroyed universes quantum bogosort returns an unsorted sequence due to bit errors.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by taneq on Saturday December 19, 2020 @09:57AM
(#25477748)
Repeat the check an arbitrary number of times then? We have infinite universes, remember. :)
Re:Bubblesort, rocksort, and cocktail-shaker sort
by YokoZar on Wednesday December 16, 2020 @06:54AM
(#25441538)
If you're using a cloud host that doesn't charge you anything for instances with a very low runtime, you can implement quantum bogosort for free - just have every unsorted instance self-destruct promptly.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by FroshKiller on Wednesday December 16, 2020 @07:24AM
(#25441724)
For any given input, there is no advantage to running more than one instance in the same universe.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by bluGill on Wednesday December 16, 2020 @08:20AM
(#25442153)
This is creating many universes though.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by bluGill on Wednesday December 16, 2020 @08:32AM
(#25442268)
You can trivially parallelize this algorithm to be O(1): for each permutation you create universes to check all finite lengths of the list in parallel and destroy the universes that check either less elements than are in the list or that run off the end of the list.
I'm not sure if this can extend to infinite size lists. Sorting infinite lists in finite time makes my head hurt.
[0] https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort