Anonymous user
Talk:Order two numerical lists: Difference between revisions
→Stable Sort??
(adding extra credit doesn't invalidate a solution.) |
|||
Line 60:
:: If so, it's bunk: sort stability depends more on the sort method than the comparator.--[[User:Ledrug|Ledrug]] 04:33, 30 November 2011 (UTC)
::: true, but if both elements are the same then it makes a difference if true or false is returned. how do you account for that difference? i think there are two aspects to stable, one is: when you rerun the sort it will always produce the same result. this stability depends on the algorithm. the other is, that if two elements are equal, their order will not be changed. that stability depends on the comparator. and according to [[wp:Sorting_algorithm#Stability|wikipedia]]: ''Stable sorting algorithms maintain the relative order of records with equal keys.'' the equality of keys is determined by the comparator.--[[User:EMBee|eMBee]] 05:50, 30 November 2011 (UTC)
:::: Still bunk. Regardless if elements are the same or not, sort stability also depends on how the comparator is called. <code>if (a[i] < a[j]) swap(a[i], a[j])</code> and <code>unless (a[i] > a[j]) swap(a[i], a[j])</code> are unlikely to be both stable in bubble sort. The comparison routine has '''no''' information regarding "the relative order of records", only the sort routine does, so terming a comparator "stable sort" is senseless. --[[User:Ledrug|Ledrug]] 07:20, 30 November 2011 (UTC)
:: Another thing, it might be better to omit some detailed requirement about the cmp result. To be practical, the cmp routine should be able to decide on the ording. For example, it's likely more useful for a comparison function to be tri-state instead of true/false;--[[User:Ledrug|Ledrug]] 04:33, 30 November 2011 (UTC)
::: tri-state does not work as input to a sort function unless the sort function is written for that. most sort function i i'd expect to want a boolean comparator.--[[User:EMBee|eMBee]] 05:50, 30 November 2011 (UTC)
| |||