Sort stability: Difference between revisions

Line 105:

/* a stable sort will output ["US", "Birmingham"] before ["UK", "Birmingham"] */</lang>

Stable implementations:

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}}

⚫

<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.

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:

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:

Line 168:

Short demonstration for sorting only on the second item of each array:

⚫

<lang perl6>use v6;

⚫

use v6;

my @cities =

['UK', 'London'],

Line 171:

Line 176:

;

.say for @cities.sort: { .[1] };

.say for @cities.sort: { .[1] };</lang>

</lang>

=={{header|PHP}}==

Line 187:

Line 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:

Line 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:

Line 277:

There are two sort methods defined on <tt>Seq</tt>, which is the base collection trait for all sequences.

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 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:

Line 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

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:

<lang scala>scala> val cityArray = cities.toArray

cityArray: Array[String] = Array(UK London, US New York, US Birmingham, UK Birmingham)