Anonymous user
Sort stability: Difference between revisions
m
whitespace
m (whitespace) |
|||
Line 105:
/* a stable sort will output ["US", "Birmingham"] before ["UK", "Birmingham"] */</lang>
Stable implementations:
{{works with|SpiderMonkey|1.8}}
{{works with|Firefox|3}}
{{works with|Internet Explorer|6}}
{{works with|JScript|5.7}}
{{works with|OSSP js}}
<pre>UK,London,US,New York,US,Birmingham,UK,Birmingham
US,Birmingham,UK,Birmingham,UK,London,US,New York</pre>
Not stable:
Not stable: {{works with|Rhino|1.7 rel 2}}, {{works with|Google Chrome|3.0}}▼
{{works with|Rhino|1.7 rel 2}}
<pre>UK,London,US,New York,US,Birmingham,UK,Birmingham
UK,Birmingham,US,Birmingham,UK,London,US,New York</pre>
=={{header|Lua}}==
The built-in function table.sort is not guaranteed stable.
=={{header|Mathematica}}==
Sort is not always stable. Ordering, which gives a list of indices such as to put the elements of the list in order, is stable. An example would be to sort the list (of lists) {{1, 2, 3}, {4, 5, 6}, {5, 4, 3}, {9, 5, 1}}, and doing so by looking at the 2nd value of each list:
<lang Mathematica>mylist = {{1, 2, 3}, {4, 5, 6}, {5, 4, 3}, {9, 5, 1}};
Sort[mylist, (#1[[2]] < #2[[2]]) &]
Line 161 ⟶ 168:
Short demonstration for sorting only on the second item of each array:
<lang perl6>use v6;▼
▲<lang perl6>
my @cities =
['UK', 'London'],
Line 171 ⟶ 176:
;
.say for @cities.sort: { .[1] };</lang>
=={{header|PHP}}==
Line 187 ⟶ 191:
=={{header|R}}==
R uses shell sort (stable) or quick sort (unstable). An easy way to show the difference is names to vector entries, then check if names are still ordered after sorting.
Line 242 ⟶ 245:
There seems to be some discussion debating whether stable sorting is worth the performance trade-off [[http://redmine.ruby-lang.org/issues/show/1089 2]].
<!--
To code a stable sort[[http://codesnippets.joyent.com/posts/show/1698 2]]:
Line 275 ⟶ 277:
{{works with|Scala|2.8}}
There are two sort methods defined on <tt>Seq</tt>, which is the base collection trait for all sequences. The methods are <tt>sortWith</tt> and <tt>sortBy</tt>, and differ only on the argument used. The first expects a function that will implement the "less than" method for the type of the sequence. The second expects a function from the type of the sequence into any type for which there is an <tt>Ordering</tt>, plus an implicit Ordering of the proper type.
The sort is stable.
Examples:
<lang scala>scala> val list = List((1, 'c'), (1, 'b'), (2, 'a'))
list: List[(Int, Char)] = List((1,c), (1,b), (2,a))
Line 304 ⟶ 301:
scala> cities.sortBy(_ substring 4)
res47: Seq[String] = ArrayBuffer(US Birmingham, UK Birmingham, UK London, US New York)</lang>
Besides that, there is the object <tt>scala.util.Sorting</tt>, which provides <tt>quickSort<tt> and <tt>stableSort</tt>. The former is only provided on <tt>Array</tt>, but the latter is provided over both <tt>Array</tt> and <tt>Seq</tt>. These sorts operate in-place, with the one over <tt>Seq</tt> returning a sorted <tt>Array</tt>. Here is one example:▼
▲Besides that, there is the object <tt>scala.util.Sorting</tt>, which provides <tt>quickSort<tt> and <tt>stableSort</tt>. The former is only provided on <tt>Array</tt>, but the latter is provided over
<lang scala>scala> val cityArray = cities.toArray
cityArray: Array[String] = Array(UK London, US New York, US Birmingham, UK Birmingham)
| |||