Talk:Sort stability: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 26:
:Funnily, R uses also shell sort (or optionally a quick sort), and the manuals says that when shell sort is called on an array ''with names'', it uses a stable sort. Now, is there a stable variant of shell sort ? Or have I tried a very special case where shell sort is stable ? I'll have to look at this...
:[[User:Toucan|Toucan]] 08:30, 13 June 2011 (UTC)
::Ok, I've found the answer. In file lib/list.gi of GAP source distribution, we can see that SortingPerm doesn't sort exactly its argument (let's say it's L), but a list of pairs [ L[i], i ]. Since comparison of lists is done with lexicographic order, even with an unstable sort, the pairs will be sorted in a stable way (the integers indexes are here to distinguish two equal elements of L). The code I use to check merely retrieves these indexes. Conclusion : Sort is not stable, but we don't care since we can't check for it. And SortingPerm is stable.
::[[User:Toucan|Toucan]] 14:29, 13 June 2011 (UTC)
| |||