|
From: | Michael D Godfrey |
Subject: | stable sorts |
Date: | Sat, 25 Aug 2012 14:44:11 -0400 |
User-agent: | Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120717 Thunderbird/14.0 |
Ben, I checked a few things about sorts: 1. The term for a sort which correctly orders the indices of equal objects is "stable." 2. Our current Matlab (2009b) implements unstable sort, matching Octave. But there is the following Note in the Mathworks Newsletters (dated 2004): http://www.mathworks.com/company/newsletters/news_notes/dec04/adventure.html This says a number of interesting things, but they do not match the version of Matlab that we use. However, our matlab does have sortrows, which is claimed to be based on a stable sort. Octave sortrows says in the code: ## Since sort is 'stable' the order of identical elements will be ## preserved, so by traversing the sort indices in reverse order we ## will make sure that identical elements in index i are subsorted by ## index j. This documentation is ambiguous, at least to me, but it looks like the code does the right re-ordering. But, I have not run a test case. (I take the first line of the comment above to mean "Since sortrows is stable..." An important point would be to find out if newer Matlabs implement sort as stable. If they do, there is a strong compatibility argument for updating Octave sort. However, I think that it may be a good idea to make sort stable in any case. There is some feeling that, despite many unstable sorts, including C qsort, unstable is actually incorrect. I agree with this. I think that the latest interp1 (with your fix) will still work with a stable sort. Is this correct? Finally, the Mathworks newsletter talks about visort, vqsort, and vrsort, but our 2009b matlab does not provide these. If they are in newer matlabs, it would be good to implement them. Michael |
[Prev in Thread] | Current Thread | [Next in Thread] |