3 ms·
Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
by jcalvinowens 3y ago
Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
- lifthrasiir 3y agoUnless you have a thousand of sorting routines it wouldn't matter much. And compilers generally produce a much larger code than actually possible, you can implement bubblesort in 16 bytes of x86-32 assembly [1] for example. [1] https://gist.github.com/jibsen/8afc36995aadb896b649 https://gist.github.com/jibsen/8afc36995aadb896b649
- jcalvinowens 3y agoIt matters a great deal if you have 1KB of flash to fit the whole firmware in :)
- lifthrasiir 3y agoOh, if you are already writing an assembly my comment doesn't apply ;-)
- acdha 3y agoI was expecting that, too. The one person I’ve heard say they’d implemented bubble sort in the current century worked on automotive controllers where they had absurdly tight memory budgets and the data he had to sort was relatively small so they quite happily traded a few cycles for the smaller executable.
- padf 3y agoYes. Ignorant question: if you use bubble sort but go through the array in alternating senses, could it not improve locality and speed? Array v with N elements: First pass: go from v[0] to v[N-1] comparing v[i] with v[i+i] Second pass: go from v[N-1] to v[0] comparing v[i] with v[i+i] This is so obvious that it should have a name...
- padf 3y agoAnswering myself. Yes, it was an ignorant question as the name is Cocktail Shaker sort: https://en.wikipedia.org/wiki/Cocktail_shaker_sort https://en.wikipedia.org/wiki/Cocktail_shaker_sort