5 ms·
My first CS teacher talked about what he called Bang Sort, which is also O(n): 1. For each entry in your list, cut a straw of length proportional to the value
by rflrob 5y ago
My first CS teacher talked about what he called Bang Sort, which is also O(n):
1. For each entry in your list, cut a straw of length proportional to the value to be sorted
2. Take all your straws in a bundle
3. Bang them gently on a flat table
4. Draw out the straws in order of length, each operation of which can be done in O(1) time
- solipsism 5y agoThe energy and space required are O(n) though.
- hibbelig 5y agoGiven that storing n items in an array or a similar structure requires O(n) space, the space requirement of bang sort seems normal. Perhaps by making use of the Oracle of Delphi, you could do away with the array. Also, the energy requirements... Wouldn't they be proportional to the number of operations required, i.e. the time complexity?
- deleted 5y ago[deleted]
- tsimionescu 5y agoThe more straws you have, the harder it becomes to discover the largest one, and to actually pick all of them up and bang them. At some point you will likely end up foul of fundamental limits related to mass and energy and the speed of light, and that limit will probably come well before 2^32 elements. Edit: This is usually the problem with analog algorithms: you can easily tell apart 100 items, but scale it up and you find you need so much energy to differentiate that you'd collapse into a black hole before successfully measuring the differences.