Sort stability: Difference between revisions

When sorting records in a table by a particular column or field, a [[wp:Stable_sort#Stability|stable sort]] will always retain the relative order of records that have the same key.

 

US New York

US Birmingham

 

 

(This [[wp:Stable_sort#Comparison_of_algorithms|Wikipedia table]] shows the stability of some common sort routines).

 

=={{header|AutoHotkey}}==

Autohotkey has got a build-in sorting method for tables, which is stable.

(

UK, London

ButtonSortCities:

LV_ModifyCol(3, "Sort")

 

=={{header|AWK}}==

# syntax: GAWK -f SORT_STABILITY.AWK [-v width=x] -v field=x SORT_STABILITY.TXT

#

exit(0)

}

<p>input:</p>

<pre>

=={{header|C}}==

There is no built-in function in C ''language''. <code>stdlib</code> which comes with any C ''implementation'' is required to provide a [[wp:Qsort|<code>qsort()</code>]] routine that can sort arbitrary datatypes. Although the sorting algorithm is not specified, most (all?) implementions use a combined quicksort/insertion sort method for efficiency. Quicksort is by nature unstable.

 

=={{header|C sharp|C#}}==

The .NET library documentation for <tt>Array.Sort()</tt> says that it uses quicksort and is unstable.[http://msdn.microsoft.com/en-us/library/kwx6zbd4.aspx#remarksToggle]

 

=={{header|Clojure}}==

Clojure's ''sort'' and ''sort-by'' functions are implemented using Java's ''java.utils.Array.sort'' methods, which are guaranteed stable.

 

=={{header|Common Lisp}}==

 

<em>Unstable</em>, <em>stable</em> and <em>semistable</em> (in algorithms that partition ranges in two, <em>semistable</em> preserves stability on just the left of the partition point) are supported.

=={{header|Déjà Vu}}==

The included sorting algorithm, <code>sort</code>, is stable.

These functions use merge sort algorithm.

The sorting algorithm will be stable as long as the given function returns true for values considered equal:

{"US", "New York"},

{"US", "Birmingham"},

IO.inspect Enum.sort(cities, fn a,b -> elem(a,0) >= elem(b,0) end)

IO.inspect Enum.sort_by(cities, fn {country, _city} -> country end)

{{out}}

<pre>

 

'''Note:''' If the function does not return true, the sorting is not stable and the order of equal terms may be shuffled:

{{out}}

<pre>

=={{header|Erlang}}==

The function lists:sort/1 is not documented as stable. The function lists:keysort/2 is documented as stable.

 

=={{header|F_Sharp|F#}}==

[http://msdn.microsoft.com/en-us/library/ee370375.aspx <code>Array.sort</code>] is not stable.

[http://msdn.microsoft.com/en-us/library/ee370323.aspx <code>List.sort</code>] and [http://msdn.microsoft.com/en-us/library/ee353483.aspx <code>Seq.sort</code>] are stable.

 

=={{header|GAP}}==

# However, SortingPerm is stable. We will see it on an example, showing indexes of elements after the sort.

 

PrintArray(TransposedMat(List([1 .. n], i -> [a[i], b[i]])));

# [ [ 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B' ],

 

=={{header|Go}}==

{{trans|Java}}

{{works with|Groovy|1.8.1}}

[

'Sort by city': { city -> city[4..-1] },

println "\nAfter ${label}"

cityList.sort(false, orderBy).each{ println it }

 

Output:

 

The following sample demonstrates Java's sort stability:

import java.util.Comparator;

 

System.out.println();

}

;Output

<pre>

 

=={{header|JavaScript}}==

 

print(ary);

 

print(ary);

 

 

Stable implementations:

<pre>UK,London,US,New York,US,Birmingham,UK,Birmingham

UK,Birmingham,US,Birmingham,UK,London,US,New York</pre>

 

=={{header|Julia}}==

("UK","London")

("US","New York")

</pre>

 

Arrays can be sorted in two “built in" ways in Lasso:

 

array->sort

 

 

//The array can also be ordered by multiple values:

 

Sorting of arrays by either method uses “Qucksort” and is therefore unstable. A simulation of increasing sort stability would be introduced with additional params such as the example of ordering by the second then the first pair values in the example above - but would not be guaranteed stable.

 

Sort by second value only:

{{out}}

<pre>US - Birmingham

 

Sort by second then by first:

{{out}}

<pre>UK - Birmingham

 

Here's an example showing that SORT indeed unstable.

randomize 0.5

N=15

end if

next

{{Out}}

<pre>

The built-in function table.sort is not guaranteed 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:

Sort[mylist, (#1[[2]] < #2[[2]]) &]

gives:

Showing that Sort is unstable, and that by using input[[Ordering[input]]] Ordering provides a way to make a stable sort.

 

Java's [http://java.sun.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List) Collections.sort()] and [http://java.sun.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object%5B%5D) Arrays.sort()] methods are guaranteed stable. The following sample takes advantage of this to demonstrate sort stability.

 

options replace format comments java crossref savelog symbols nobinary

 

method compare(lft = Object, rgt = Object) public binary returns int

return (String lft).substring(0, 2).compareTo((String rgt).substring(0, 2))

;Output

<pre>

=={{header|Nim}}==

Default Nim sort in the algorithm module is stable.

 

=={{header|OCaml}}==

=={{header|ooRexx}}==

Open Object Rexx provides sort methods (<code>sort</code> and <code>sortWith(comparator)</code>) for its collection classes. By default these sort methods are implemented via an unstable <em>Quicksort</em> algorithm but the language does provide stable sorting methods (<code>stableSort</code> and <code>stableSortWith(comparator)</code>) implemented via a stable <em>Mergesort</em> algorithm.

Do

cities = .array~of('UK London', 'US New York', 'US Birmingham', 'UK Birmingham',)

End

Exit

;Output

<pre>

=={{header|OpenEdge/Progress}}==

The results can be forced to stable by ''additionally'' sorting on the ROWID of the record. If you leave the additional sort out, the indexes on the temp-table can influence the result.

FIELD country AS CHAR FORMAT 'x(2)'

FIELD city AS CHAR FORMAT 'x(16)'

MESSAGE

cc[1] SKIP(1) cc[2]

 

'''Output:'''

 

Example:

Cities = ['UK'#'London'

'US'#'New York'

 

%% sort by country; NOT stable because '<' is not reflexiv

 

=={{header|PARI/GP}}==

 

=={{header|Pascal}}==

 

=={{header|Perl}}==

The stability of Perl's in-built [http://perldoc.perl.org/functions/sort.html sort] function is version-dependent. If you want to guarantee a stable sort from it, you should use the following [http://perldoc.perl.org/sort.html sort pragma]:

 

 

=={{header|PHP}}==

=={{header|Python}}==

Python's in-built [http://docs.python.org/library/functions.html#sorted sorted] function as well as the [http://docs.python.org/library/stdtypes.html#mutable-sequence-types sort method of lists] are guaranteed stable (since version 2.3). (For even more information on the underlying routine, [[wp:timsort]], see [http://svn.python.org/projects/python/trunk/Objects/listsort.txt this]).

 

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

 

# First, define a bernoulli sample, of length 26.

x <- sample(c(0, 1), 26, replace=T)

# e h j n q s u x z a b c d f g i k l m o p r t v w y

# 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

 

=={{header|Racket}}==

Racket comes with a standard <tt>sort</tt> function, which is documented [[http://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Fprivate%2Flist..rkt%29._sort%29%29 here]]. It is documented as stable.

 

#lang racket

 

;; -> '(("US" "Birmingham") ("UK" "Birmingham")

;; ("UK" "London") ("US" "New York"))

 

=={{header|REBOL}}==

 

blk: [

UK Birmingham

]

 

=={{header|REXX}}==

<pre>

</pre>

 

=={{header|Ring}}==

aList = [["UK", "London"],

["US", "New York"],

["UK", "Birmingham"]]

see sort(aList,2)

 

=={{header|Ruby}}==

 

{{works with|MRI|1.8.7, 1.9.2}}

["US", "New York"],

["US", "Birmingham"],

p ary.sort {|a,b| a[1] <=> b[1]}

# MRI reverses the Birminghams:

 

Other implementations of Ruby might differ. Old versions of [[JRuby]] used java.util.Arrays.sort, which was a stable sort, but was slower than MRI. To increase performance, JRuby switched to quicksort, which is not stable. [http://jira.codehaus.org/browse/JRUBY-2198 (3)]

To code a stable sort, without implementing another sorting algorithm (such as [[Sorting algorithms/Merge sort|merge sort]]), use a Schwartzian transform.

 

def stable_sort

n = -1

sort_by {|x| n += 1; [(yield x), n]}

end

 

["US", "New York"],

["US", "Birmingham"],

# => [["US", "Birmingham"], ["UK", "Birmingham"], ["UK", "London"], ["US", "New York"]]

p ary.stable_sort_by {|x| x[1]}

 

=={{header|Scala}}==

 

Examples:

list: List[(Int, Char)] = List((1,c), (1,b), (2,a))

 

 

scala> cities.sortBy(_ substring 4)

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

 

 

scala> cityArray

 

=={{header|Sidef}}==

Sidef uses the stable merge-sort algorithm for sorting an array.

<UK London>,

<US New\ York>,

table.sort {|a,b| a[0] <=> b[0]}.each { |col|

say "#{col[0]} #{col[1]}"

{{out}}

<pre>UK London

US New York

US Birmingham</pre>

 

=={{header|Tcl}}==

Tcl's built-in [http://www.tcl.tk/man/tcl8.4/TclCmd/lsort.htm <code>lsort</code>] command implements a stable sort. It has been guaranteed to be stable since Tcl 8.0. Internally, it uses the mergesort algorithm.

 

=={{header|zkl}}==

zkl's sort methods don't mention stability or columns, they are comparison based.

T("UK", "London"), T("US", "New York"),

T("US", "Birmingham"),T("UK", "Birmingham"), );

sortByColumn(cities,0).concat("\n").println("\n------");

{{out}}

<pre>