4 ms·
Note that it is straightforward to modify an unstable sort algorithm into a stable one, when it’s okay to use O(n) extra memory: define an array that tracks eac
by chrchang523 4y ago
Note that it is straightforward to modify an unstable sort algorithm into a stable one, when it’s okay to use O(n) extra memory: define an array that tracks each element’s original position, and when two elements otherwise compare equal, use the original position as the final tiebreaker.
(With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the difference is.)
- hypertele-Xii 4y agoIsn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.
- chrchang523 4y agoThat's my usual approach, but there are clearly some programmers who don't want to always do this, and sometimes a stable-sort library function does in fact allow them to be more productive.
- bee_rider 4y agoThis seems basically equivalent to saying that whether or not a sort is stable is irrelevant, right? If the position of elements with equal keys doesn’t matter for your application, then of course there’s no reason to use a stable sort (or convert a non-stable one to stable by whatever trick).
- mxkopy 4y agoI'd assume cache locality makes it worthwhile, especially if the keys are big, point to big things that need to move, or live on separate drives. To that last point I'd wager stable algorithms can imply parallelization.
- ErikCorry 4y agoWell these are the sorts of arguments I made on the V8 bug, and people were not happy.
- lucumo 4y agoNo, there could be unsortable properties that are nonetheless different. Or the use case could really require that the original order is relevant. But yeah, I don't usually need stability either.
- hypertele-Xii 4y agoForgive me for sounding like an idiot but how can two properties be different, yet unsortable?
- lucumo 4y agoIf you can digitize it, you can probably sort it, that's true. But the sort keys can get very artificial and weird. Let's say you're sorting a bunch a unlabelled images. You can sort them by number of pixels, that's pretty clear but will likely have clashes. You could then sort by either width of height next, but the choice is pretty arbitrary. It's not obvious why a 100x10 pixel image should come before or after a 10x100 pixel image. But it's not very weird to pick one either. Next you could sort on properties of the first pixel. But those are multidimensional. Sorting by the most red first, for example, would be weird. You could still create an ordering if you need the consistency, but it wouldn't mean anything. If you don't sort by them, you can get images that are different in ways that aren't sorted. Stability (well, instability) becomes detectable. If you have to use an unstable sorting algorithm you'll be stuck choosing between images jumping around or being in a certain spot because the 34th pixel on the 56th line is slightly more greenish than in the image before it. It can depend on your use case which of those is least desirable. Having a stable sort would give you another option.
- hypertele-Xii 4y agoIs there such a thing as visual similarity -sort? Asking because you're actually describing a problem I have with a data set :D
- CipherThrowaway 4y agoDeeper comparison doesn't solve the problem because input order is arbitrary. The order may be based on a user dragging items around in a list widget, for example. The easiest way to transform an unstable sort into a stable sort is probably mapping input from T -> (Index, T) and including the index as a sort key.
- tgv 4y agoI'll spell it out then: you don't always need to sort based on the entire object's value. Comparing the whole object can be pretty expensive when you only need to sort by one field.
- hypertele-Xii 4y agoAnd allocating O(N) extra memory isn't expensive?
- noitpmeder 4y agoAnd if they're not completely equal?
- hypertele-Xii 4y ago...then they sort? What am I missing?