Talk:Sort stability: Difference between revisions
Content deleted Content added
→J and stability?: My thanks. |
No edit summary |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 20:
:Thanks Tikkanz for the excellent explanation. --[[User:Paddy3118|Paddy3118]] 08:57, 29 August 2009 (UTC)
==GAP and stability?==
Does GAP seem stable with the example given in the task description? I find it hard to follow what is being described in the GAP example. (Maybe some of the notes would be better off here in the talk page and maybe expanded apon)? --[[User:Paddy3118|Paddy3118]] 21:41, 12 June 2011 (UTC)
:I thought it was easy, you can see the R implementation (which I also wrote), mayber it's easier to read. The idea: sort an array of random values A/B, and get the sorting permutation. Then apply this permutation on an array of already sorted integers 1..n. In the result, there are two blocks, one for A and the other for B. If integers are sorted in both blocks, then the sort is stable in this case (I assume you understand why !). Of course I didn't prove it's stable in all cases, but I was not able to find a counterexample. Usually, an unstable sort fails even on such trivial examples (again, see R).
: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)
|