8 ms·
I suppose Excel data is often almost sorted with a few new additions, which makes bubble sort an arguably better choice?
by snaily 8y ago
I suppose Excel data is often almost sorted with a few new additions, which makes bubble sort an arguably better choice?
- xrisk 8y agoNope, bubble sort always performs the same number of ops regardless of whether the array is partially sorted or not. You might be thinking about insertion sort, which has that feature.
- JoeSmithson 8y agoBubble sort's number of operations can vary from n, if the list is sorted already, up to O(n*n) if the list is reversed.
- umanwizard 8y agoNot true. (3 2 1) -> (2 3 1) -> (2 1 3) -> (1 2 3) (3 passes, 3 swaps) Compare: (1 3 2) - > (1 2 3) (2 passes, 1 swap)
- xrisk 8y agoHmm I suppose you're right. My bad!
- ape4 8y agoIf you write it really poorly that might happen - but its easy to add a check to see if any swaps occurred. If none, you are done.
- kalleboo 8y agoI can't imagine they're using the OS sort for actual spreadsheet data. It's probably for something else like filenames or whatever, and it ends up not finding the file it's expecting in the place it's expecting.
- snaily 8y agoAgreed, especially since I (the GP) thought about this the wrong way - _Apple_ has chosen to use bubble sort as a compatibility measure for some Microsoft apps, not the other way around.
- krotton 8y agoWhich was possible because Microsoft decided to use Core Foundation APIs for sorting instead of their own implementation for spreadsheet data. Or maybe it's not for spreadsheet data, but just their custom file picker or something?
- arghwhat 8y agoIt's a framework-provided sort, not an OS sort. Its use is no weirder than using stdlib sorts, such as Go's "sort" package (which does either a quicksort, heapsort or shellsort, depending on the input length). However, relying on stability if it is not specified is a bad thing.
- deleted 8y ago[deleted]
- kalleboo 8y agoWhile I'm not a big fan of reinventing the wheel, when you're maintaining a 31-year-old cross-platform app that the majority of the planet's businesses rely on for their calculations, I'd be using a custom cross-platform math/sorting/etc engine rather than delegating to any OS, framework, stdlib, third-party anything. Considering this is Microsoft, where Office 4.2 for Mac was as close to WINE as you could get in the 90's, I'm assuming they're doing the same.
- arghwhat 8y agoThey are in platform specific code, manipulating CoreFoundation types (specifically a CFMutableArray), so your cross-platform homebrew sort suggestion is out of scope here. Any sorting function would need to be CoreFoundation (iOS/watchOS/macOS) specific. When possible, it would of course be best to use stdlib functionality, which would implicitly be cross-platform. Writing it yourself, or pulling in third-party libs to do it ranks way below stdlib, although I can't agree with myself whether doing so is better or worse than using OS-specific standard frameworks. Regardless, it is out of scope in this example.
- hornetblack 8y agoInsert sort should also be pretty fast for almost stored list, (and works better for not almost sorted).
- iainmerrick 8y agoFriends don't let friends use bubble sort. In fact friends don't even let enemies use bubble sort, if they have an ounce of humanity. Edit to actually answer the question: I wonder if it's something to do with some specific dataset having to be sorted in a particular way? i.e. where you'd normally use a stable sort, but the code accidentally depends on a specific unstable sort.
- iainmerrick 8y agoOh, wait, bubble sort is stable so it can't be that. Any other theories?
- anonymfus 8y ago>Any other theories? 1. Excel needs stable sort but OSX sort is unstable. 2. Performance deoptimisation to make Excel perform worse.
- iainmerrick 8y agoThere are any number of better ways to fix 1, though! 2 occurred to me too, but surely that’s too cynical. It would make Macs look bad more than Excel itself. Maybe it’s a bit of both. They needed a fix for 1, but they didn’t care about Excel performance at all so someone just spent 20 seconds doing a quick bodge job.
- saagarjha 8y agoMaybe because the software has a race condition around sorting which requires the use of a slower sort?
- r00fus 8y agoIs it wrong to ask if Microsoft intended it to be slow? Mac Outlook on a recent MBP is noticeably slower (usability impact) than a similar version of Outlook on my Windows VM on the same machine against the same account (30k items, 5GB-ish)
- xxs 8y agoBubble sort is never a good choice unless so extremely lazy or what to impersonate Obama...[0] There are dual-pivot quicksort, smooth sort (in-place, based on Leonardo numbers and takes O(n) time to process a presorted array and O(n log n) in the worst case, and achieves nearly-linear performance on many nearly-sorted inputs), TimSort (that's stable as plus). Morealso changing stable to unstable sort is usually a very bad move. [0]: https://www.youtube.com/watch?v=k4RRi_ntQc8 https://www.youtube.com/watch?v=k4RRi_ntQc8
- AlotOfReading 8y agoBubble sort is perfectly acceptable when you can only swap adjacent elements, which occasionally comes up in memory management.
- iainmerrick 8y agoThat’s the only time it would ever be acceptable, and I don’t think that comes up very often at all.
- xxs 8y agoHmm, do you have a good example? Even linked lists allow swapping elements at arbitrary positions.
- AlotOfReading 8y agoAt one point I was implementing managed memory on a highly memory constrained system. The system pretty quickly ran into issues with having enough memory to fulfill a request, but no contiguous block long enough. The solution to this is of course defragmentation. The issue is that allocations are irregularly sized and all swaps have to be done in-place. There was also a need to collect blocks of similar size together so the GC could work faster. Bubble sort was the only way to meet all these constraints cleanly, and better yet it only took 10 lines. It still felt dirty though.
- MichaelDickens 8y ago