4 ms·

I absolutely loved learning about Bead Sort when I was in Uni. I was taking a class on algorithm design and Big-O notation and ended up reading through the sor

by munk-a 6y ago

I absolutely loved learning about Bead Sort when I was in Uni. I was taking a class on algorithm design and Big-O notation and ended up reading through the sorting algorithms page on wikipedia[1] and then wandering off the garden path investigating a few. There are several amusing ways that standard algorithmic analysis has been subverted with creative solutions (i.e. if you subscribe to the many-worlds theory then bogosort is always O(1) for at least one universe - you just need to discard the incorrect universes) but beadsort stood out as a really fun way to turn the problem on its head - the fact that it appears to be inspired from misusing an abacus just makes it even better. It's a great example of why having people who can think outside of the box can be a good asset - approaching problems from unexpected directions can yield valuable and novel solutions. 1. https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...

kkaranth 6y ago
I'm taking a graduate algorithms class right now, and stumbled upon the bead sort wiki page. These methods are quite interesting! The bound of O(n log n) only applies when using the traditional greater/less than comparison model
- MaxBarraclough 6y ago
  > only applies when using the traditional greater/less than comparison model What do you mean by this?
  - brmgb 6y ago
    The bound is a bound on comparaison sort not a general bound on sorting. If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.
    - MaxBarraclough 6y ago
      Right, comparative and non-comparative sorting algorithms. I'd say radix sort is the canonical example of a non-comparative sorting algorithm.
jbay808 6y ago
> (i.e. if you subscribe to the many-worlds theory then bogosort is always O(1) for at least one universe - you just need to discard the incorrect universes) Does this same line of thinking conclude that P=NP in at least one universe, too? You can use a radioactive decay counter to generate quantum random numbers, interpret them as a answer to an NP problem, and then verify the solution in polynomial time the normal way? In at least one universe, that will always work on the first try.
- munk-a 6y ago
  "It's amazing what you can do if you're willing to sacrifice a few universes to get out of doing some addition" - probably no one ever, but it should've been said before now.
  - cratermoon 6y ago
    That sounds like a quote from a Douglas Adam book.
  - kryptiskt 6y ago
    Narbonic got close http://narbonic.com/wordpress/wp-content/uploads/2006/12/061207.jpg http://narbonic.com/wordpress/wp-content/uploads/2006/12/061...
- comex 6y ago
  puts on pedant’s hat That wouldn’t actually make P = NP, because P is defined mathematically from first principles rather than being based on the rules of the universe. However, it would shift the class of practically computable problems from being ‘like P’ (but with limits on the runtime and memory usage achievable), to being ‘like P^NP’, P with an NP oracle, which is surprisingly a different complexity class from NP. At least, that’s what I gather based on Wikipedia and Stack Overflow [1]; I’m not an expert on the subject so I could be mistaken. [1] https://cs.stackexchange.com/questions/2712/does-npnp-np https://cs.stackexchange.com/questions/2712/does-npnp-np
  - jbay808 6y ago

by munk-a 6y ago

kkaranth 6y ago

I'm taking a graduate algorithms class right now, and stumbled upon the bead sort wiki page. These methods are quite interesting! The bound of O(n log n) only applies when using the traditional greater/less than comparison model

MaxBarraclough 6y ago
> only applies when using the traditional greater/less than comparison model What do you mean by this?
- brmgb 6y ago
  The bound is a bound on comparaison sort not a general bound on sorting. If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.
  - MaxBarraclough 6y ago
    Right, comparative and non-comparative sorting algorithms. I'd say radix sort is the canonical example of a non-comparative sorting algorithm.

jbay808 6y ago

> (i.e. if you subscribe to the many-worlds theory then bogosort is always O(1) for at least one universe - you just need to discard the incorrect universes) Does this same line of thinking conclude that P=NP in at least one universe, too? You can use a radioactive decay counter to generate quantum random numbers, interpret them as a answer to an NP problem, and then verify the solution in polynomial time the normal way? In at least one universe, that will always work on the first try.

munk-a 6y ago
"It's amazing what you can do if you're willing to sacrifice a few universes to get out of doing some addition" - probably no one ever, but it should've been said before now.
- cratermoon 6y ago
  That sounds like a quote from a Douglas Adam book.
- kryptiskt 6y ago
  Narbonic got close http://narbonic.com/wordpress/wp-content/uploads/2006/12/061207.jpg http://narbonic.com/wordpress/wp-content/uploads/2006/12/061...
comex 6y ago
puts on pedant’s hat That wouldn’t actually make P = NP, because P is defined mathematically from first principles rather than being based on the rules of the universe. However, it would shift the class of practically computable problems from being ‘like P’ (but with limits on the runtime and memory usage achievable), to being ‘like P^NP’, P with an NP oracle, which is surprisingly a different complexity class from NP. At least, that’s what I gather based on Wikipedia and Stack Overflow [1]; I’m not an expert on the subject so I could be mistaken. [1] https://cs.stackexchange.com/questions/2712/does-npnp-np https://cs.stackexchange.com/questions/2712/does-npnp-np
- jbay808 6y ago