Sort stability: Difference between revisions
Content deleted Content added
added sort by rowid to enforce a stable sort |
Walterpachl (talk | contribs) →{{header|REXX}}: replace the wrong program |
||
(75 intermediate revisions by 44 users not shown) | |||
Line 1:
{{task|Sorting Algorithms}}
{{Sorting Algorithm}}
[[Category:Sorting]]
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.
;Example:
In this table of countries and cities, a stable sort on the ''second'' column, the cities, would keep the '''US Birmingham''' above the '''UK Birmingham'''.
(Although an unstable sort ''might'', in this case, place the '''US Birmingham''' above the '''UK Birmingham''', a stable sort routine would ''guarantee'' it).
<pre>
UK London
US New York
US Birmingham
UK Birmingham
</pre>
Similarly, stable sorting on just the first column would generate '''UK London''' as the first item and '''US Birmingham''' as the last item (since the order of the elements having the same first word – '''UK''' or '''US''' – would be maintained).
;Task:
:# Examine the documentation on any in-built sort routines supplied by a language.
:# Indicate if an in-built routine is supplied
:# If supplied, indicate whether or not the in-built routine is stable.
<br>
(This [[wp:Stable_sort#Comparison_of_algorithms|Wikipedia table]] shows the stability of some common sort routines).
<br><br>
=={{header|11l}}==
11l's in-built <code>sorted</code> function as well as the <code>sort</code> method of arrays are not guaranteed stable.
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program stableSort641.s */
/* use merge sort and pointer table */
/* but use a extra table of pointer for the merge */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*******************************************/
/* Structures */
/********************************************/
/* city structure */
.struct 0
city_name: //
.struct city_name + 8 // string pointer
city_country: //
.struct city_country + 8 // string pointer
city_end:
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .asciz "Name : @ country : @ \n"
szMessSortName: .asciz "Sort table for name of city :\n"
szMessSortCountry: .asciz "Sort table for country : \n"
szCarriageReturn: .asciz "\n"
// cities name
szLondon: .asciz "London"
szNewyork: .asciz "New York"
szBirmin: .asciz "Birmingham"
szParis: .asciz "Paris"
// country name
szUK: .asciz "UK"
szUS: .asciz "US"
szFR: .asciz "FR"
.align 4
TableCities:
e1: .quad szLondon // address name string
.quad szUK // address country string
e2: .quad szParis
.quad szFR
e3: .quad szNewyork
.quad szUS
e4: .quad szBirmin
.quad szUK
e5: .quad szParis
.quad szUS
e6: .quad szBirmin
.quad szUS
/* pointers table */
ptrTableCities: .quad e1
.quad e2
.quad e3
.quad e4
.quad e5
.quad e6
.equ NBELEMENTS, (. - ptrTableCities) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
ptrTableExtraSort: .skip 8 * NBELEMENTS
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrptrTableCities // address pointers table
bl displayTable
ldr x0,qAdrszMessSortName
bl affichageMess
ldr x0,qAdrptrTableCities // address pointers table
mov x1,0 // not use in routine
mov x2,NBELEMENTS - 1 // number of élements
mov x3,#city_name // sort by city name
mov x4,#'A' // alphanumeric
ldr x5,qAdrptrTableExtraSort
bl mergeSort
ldr x0,qAdrptrTableCities // address table
bl displayTable
ldr x0,qAdrszMessSortCountry
bl affichageMess
ldr x0,qAdrptrTableCities // address table
mov x1,0 // not use in routine
mov x2,NBELEMENTS - 1 // number of élements
mov x3,#city_country // sort by city country
mov x4,#'A' // alphanumeric
ldr x5,qAdrptrTableExtraSort
bl mergeSort
ldr x0,qAdrptrTableCities // address table
bl displayTable
100: // standard end of the program
mov x0,0 // return code
mov x8,EXIT // request to exit program
svc 0 // perform the system call
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrTableCities: .quad TableCities
qAdrszMessSortName: .quad szMessSortName
qAdrptrTableExtraSort: .quad ptrTableExtraSort
qAdrszMessSortCountry: .quad szMessSortCountry
qAdrptrTableCities: .quad ptrTableCities
/******************************************************************/
/* merge sort */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the index of first element */
/* x2 contains the number of element */
/* x3 contains the offset of area sort */
/* x4 contains the type of area sort N numeric A alpha */
/* x5 contains address extra area */
mergeSort:
stp x3,lr,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
stp x10,x11,[sp,-16]! // save registers
mov x6,x1 // save index first element
mov x7,x2 // save number of element
mov x11,x0 // save address table
cmp x2,x1 // end ?
ble 100f
add x9,x2,x1
lsr x9,x9,1 // number of element of each subset
mov x2,x9
bl mergeSort
mov x1,x9 // restaur number of element of each subset
add x1,x1,1
mov x2,x7 // restaur number of element
bl mergeSort // sort first subset
add x10,x9,1
1:
sub x1,x10,1
sub x8,x10,1
ldr x2,[x0,x1,lsl 3]
str x2,[x5,x8,lsl 3]
sub x10,x10,1
cmp x10,x6
bgt 1b
mov x10,x9
2:
add x1,x10,1
add x8,x7,x9
sub x8,x8,x10
ldr x2,[x0,x1,lsl 3]
str x2,[x5,x8,lsl 3]
add x10,x10,1
cmp x10,x7
blt 2b
mov x10,x6 //k
mov x1,x6 // i
mov x2,x7 // j
3:
mov x0,x5 // table address x1 = i x2 = j x3 = area sort offeset
bl comparArea
cmp x0,0
bgt 5f
blt 4f
// if equal and i < pivot
cmp x1,x9
ble 4f // inverse to stable
b 5f
4: // store element subset 1
mov x0,x5
ldr x6,[x5,x1, lsl 3]
str x6,[x11,x10, lsl 3]
add x1,x1,1
b 6f
5: // store element subset 2
mov x0,x5
ldr x6,[x5,x2, lsl 3]
str x6,[x11,x10, lsl 3]
sub x2,x2,1
6:
add x10,x10,1
cmp x10,x7
ble 3b
mov x0,x11
100:
ldp x10,x11,[sp],16 // restaur 2 registers
ldp x8,x9,[sp],16 // restaur 2 registers
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x3,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* comparison sort area */
/******************************************************************/
/* x0 contains the address of table */
/* x1 indice area sort 1 */
/* x2 indice area sort 2 */
/* x3 contains the offset of area sort */
/* x4 contains the type of area sort N numeric A alpha */
comparArea:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
ldr x1,[x0,x1,lsl 3] // load pointer element 1
ldr x6,[x1,x3] // load area sort element 1
ldr x2,[x0,x2,lsl 3] // load pointer element 2
ldr x7,[x2,x3] // load area sort element 2
cmp x4,'A' // numeric or alpha ?
beq 1f
cmp x6,x7 // compare numeric value
blt 10f
bgt 11f
b 12f
1: // else compar alpha string
mov x8,#0
2:
ldrb w9,[x6,x8] // byte string 1
ldrb w5,[x7,x8] // byte string 2
cmp w9,w5
bgt 11f
blt 10f
cmp w9,#0 // end string 1
beq 12f // end comparaison
add x8,x8,#1 // else add 1 in counter
b 2b // and loop
10: // lower
mov x0,-1
b 100f
11: // highter
mov x0,1
b 100f
12: // equal
mov x0,0
100:
ldp x8,x9,[sp],16 // restaur 2 registers
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of table */
displayTable:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
mov x2,x0 // table address
mov x3,0
1: // loop display table
lsl x4,x3,#3 // offset element
ldr x6,[x2,x4] // load pointer
ldr x1,[x6,city_name]
ldr x0,qAdrsMessResult
bl strInsertAtCharInc // put name in message
ldr x1,[x6,city_country] // and put country in the message
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
add x3,x3,1
cmp x3,#NBELEMENTS
blt 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
100:
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Name : London country : UK
Name : Paris country : FR
Name : New York country : US
Name : Birmingham country : UK
Name : Paris country : US
Name : Birmingham country : US
Sort table for name of city :
Name : Birmingham country : UK
Name : Birmingham country : US
Name : London country : UK
Name : New York country : US
Name : Paris country : FR
Name : Paris country : US
Sort table for country :
Name : Paris country : FR
Name : Birmingham country : UK
Name : London country : UK
Name : Birmingham country : US
Name : New York country : US
Name : Paris country : US
</pre>
=={{header|Ada}}==
[[Ada 83]] and [[Ada 95]] do not provide a standard sort utility.
[[Ada 2005]] provides two generic procedures for sorting arrays. One (<code>Ada.Containers.Generic_Array_Sort</code>) is for unconstrained array types and one (<code>Ada.Containers.Generic_Constrained_Array_Sort</code>) is for constrained array types.
Both are not guaranteed stable and in all implementation they are not.
Also, <code>Vectors</code> and <code>Doubly_Linked_Lists</code> containers have their own internal generic sort. <code>Doubly_Linked_Lists</code> sort is stable.
=={{header|AppleScript}}==
The AppleScript language doesn't have a built-in sort facility, but there are various possibilities depending on exactly what it is that needs to be sorted:
1. A scripted application may possibly have a sort command in its AppleScript dictionary whose invocation causes it to sort its own data internally (by its own criteria) and/or return them to the script in sorted form.
2. A sort routine written natively in AppleScript can be used as a library. This will be for sorting AppleScript lists, so if the data to be sorted aren't already in the form of a list, they have to be converted first and possibly converted back afterwards. An example of a stable, customisable AS sort is [https://macscripter.net/viewtopic.php?pid=194430#p194430 here].
3. The Foundation framework's NSArray and NSMutableArray classes have sorting methods which appear to be stable. However, as with AppleScript sorts, the data have to be converted first if they're not in the form of one of these classes. Furthermore, the methods usable through AppleScriptObjC only sort on named keys, not on positions, so to sort on the "second column" requires the preparation of an array containing objects which each contain an identifiable key matched with a second-column value.
4. If the data are in the form of a single piece of text, AppleScript can pass this to the 'sort' executable which comes with the Bash shell.
The task description doesn't specify what form the "table" takes, but here it's assumed to be a tab-delimited text.
<syntaxhighlight lang="applescript">set aTable to "UK London
US New York
US Birmingham
UK Birmingham"
-- -s = stable sort; -t sets the field separator, -k sets the sort "column" range in field numbers.
set stableSortedOnColumn2 to (do shell script ("sort -st'" & tab & "' -k2,2 <<<" & quoted form of aTable))
set stableSortedOnColumn1 to (do shell script ("sort -st'" & tab & "' -k1,1 <<<" & quoted form of aTable))
return "Stable sorted on column 2:" & (linefeed & stableSortedOnColumn2) & (linefeed & linefeed & ¬
"Stable sorted on column 1:") & (linefeed & stableSortedOnColumn1)</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"Stable sorted on column 2:
US Birmingham
UK Birmingham
UK London
US New York
Stable sorted on column 1:
UK London
UK Birmingham
US New York
US Birmingham"
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">records: @[
#[country: "UK", city: "London"]
#[country: "US", city: "New York"]
#[country: "US", city: "Birmingham"]
#[country: "UK", city: "Birmingham"]
]
print "Original order:"
loop records => print
print "\nSorted by country name:"
loop sort.by:'country records => print
print "\nSorted by city name:"
loop sort.by:'city records => print</syntaxhighlight>
{{out}}
<pre>Original order:
[country:UK city:London]
[country:US city:New York]
[country:US city:Birmingham]
[country:UK city:Birmingham]
Sorted by country name:
[country:UK city:London]
[country:UK city:Birmingham]
[country:US city:New York]
[country:US city:Birmingham]
Sorted by city name:
[country:US city:Birmingham]
[country:UK city:Birmingham]
[country:UK city:London]
[country:US city:New York]</pre>
=={{header|AutoHotkey}}==
Autohotkey has got a build-in sorting method for tables, which is stable.
<
(
UK, London
Line 56 ⟶ 480:
ButtonSortCities:
LV_ModifyCol(3, "Sort")
Return</
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SORT_STABILITY.AWK [-v width=x] -v field=x SORT_STABILITY.TXT
#
# sort by country: GAWK -f SORT_STABILITY.AWK -v field=1 SORT_STABILITY.TXT
# sort by city: GAWK -f SORT_STABILITY.AWK -v field=2 SORT_STABILITY.TXT
#
# awk sort is not stable. Stability may be achieved by appending the
# record number, I.E. NR, to each key.
#
BEGIN {
FIELDWIDTHS = "4 20" # 2 fields: country city
PROCINFO["sorted_in"] = "@ind_str_asc"
if (width == "") {
width = 6
}
}
{ arr[$field sprintf("%0*d",width,NR)] = $0 }
END {
if (length(NR) > width) {
printf("error: sort may still be unstable; change width to %d\n",length(NR))
exit(1)
}
printf("after sorting on field %d:\n",field)
for (i in arr) {
printf("%s\n",arr[i])
}
exit(0)
}
</syntaxhighlight>
<p>input:</p>
<pre>
UK London
US New York
US Birmingham
UK Birmingham
</pre>
<p>output from: GAWK -f SORT_STABILITY.AWK -v field=1 SORT_STABILITY.TXT</p>
<pre>
after sorting on field 1:
UK London
UK Birmingham
US New York
US Birmingham
</pre>
<p>output from: GAWK -f SORT_STABILITY.AWK -v field=2 SORT_STABILITY.TXT</p>
<pre>
after sorting on field 2:
US Birmingham
UK Birmingham
UK London
US New York
</pre>
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
The supplied SORTLIB library currently uses a Shell Sort, so it is not stable.
=={{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|C++}}==
C++ standard library's [http://www.sgi.com/tech/stl/sort.html std::sort()] function is not guaranteed stable. The stable analog of it is the [http://www.sgi.com/tech/stl/stable_sort.html std::stable_sort()] function. In addition, [http://www.sgi.com/tech/stl/List.html std::list]'s <tt>sort()</tt> method is guaranteed stable.
=={{header|Clojure}}==
Clojure's ''sort'' and ''sort-by'' functions are implemented using Java's ''java.utils.Array.sort'' methods, which are guaranteed stable.
=={{header|COBOL}}==
The SORT statement causes a set of records or table elements to be arranged in a user-specified sequence.
If the DUPLICATES phrase is specified and the contents of all the key data items associated with one record or
table element are equal to the contents of the corresponding key data items associated with one or more other
records or table elements, the order of return of these records or the relative order of the contents of these
table elements is:
a) The order of the associated input files as specified in the SORT statement. Within a given input file the
order is that in which the records are accessed from that file.
b) The order in which these records are released by an input procedure, when an input procedure is specified.
c) The relative order of the contents of these table elements before sorting takes place.
When the DUPLICATES phrase is used, the sort is stable.
=={{header|Common Lisp}}==
Common Lisp provides the two functions [http://www.lispworks.com/documentation/HyperSpec/Body/f_sort_.htm <code>sort</code> and <code>stable-sort</code>].
Each of these functions can sort arbitrary objects using a given predicate function, the input to which can be altered by the optional <code>key</code> parameter.
(eg; sorting file names based upon file sizes, the predicate might be <code><</code> and the <code>key</code> could be a function that transforms the file's name into its size)
=={{header|D}}==
Line 78 ⟶ 581:
<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|
The included sorting algorithm, <code>sort</code>, is stable.
=={{header|Elixir}}==
Enum.sort and Enum.sort_by of Elixir are 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:
<syntaxhighlight lang="elixir">cities = [ {"UK", "London"},
{"US", "New York"},
{"US", "Birmingham"},
{"UK", "Birmingham"} ]
IO.inspect Enum.sort(cities)
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)
IO.inspect Enum.sort_by(cities, fn {_country, city} -> city end)</syntaxhighlight>
{{out}}
<pre>
[{"UK", "Birmingham"}, {"UK", "London"}, {"US", "Birmingham"}, {"US", "New York"}]
[{"US", "New York"}, {"US", "Birmingham"}, {"UK", "London"}, {"UK", "Birmingham"}]
[{"UK", "London"}, {"UK", "Birmingham"}, {"US", "New York"}, {"US", "Birmingham"}]
[{"US", "Birmingham"}, {"UK", "Birmingham"}, {"UK", "London"}, {"US", "New York"}]
</pre>
'''Note:''' If the function does not return true, the sorting is not stable and the order of equal terms may be shuffled:
<syntaxhighlight lang="elixir">IO.inspect Enum.sort(cities, fn a,b -> elem(a,0) > elem(b,0) end)</syntaxhighlight>
{{out}}
<pre>
[{"US", "Birmingham"}, {"US", "New York"}, {"UK", "Birmingham"}, {"UK", "London"}]
</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|Factor}}==
The <code>sorting</code> vocabulary implements a stable sort. [http://docs.factorcode.org/content/article-sequences-sorting.html <code>sorting</code> docs]
=={{header|Fortran}}==
The language does not offer an in-built sort facility. Numerous libraries exist, which may or may not have documentation on their sort routine's stability.
=={{header|FreeBASIC}}==
The language does not offer an in-built sort facility. Numerous libraries exist, which may or may not have documentation on their sort routine's stability.
=={{header|GAP}}==
<
# However, SortingPerm is stable. We will see it on an example, showing indexes of elements after the sort.
Line 102 ⟶ 645:
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' ],
# [ 1, 2, 4, 8, 11, 13, 14, 16, 19, 3, 5, 6, 7, 9, 10, 12, 15, 17, 18, 20 ] ]</
=={{header|Go}}==
New to Go 1.2 is the function Stable() in the sort package and is documented to be a stable sort. Other sort functions are documented to have no guarantee of stability.
=={{header|Groovy}}==
Groovy's [http://groovy.codehaus.org/groovy-jdk/java/util/Collection.html#sort() Collection.sort()], Object[].[http://groovy.codehaus.org/groovy-jdk/java/lang/Object%5b%5d.html#sort() sort()], [http://groovy.codehaus.org/groovy-jdk/java/util/Map.html#sort() Map.sort()], and their various and sundry overloads all use the same stable sort algorithm.
Example:
{{trans|Java}}
{{works with|Groovy|1.8.1}}
<syntaxhighlight lang="groovy">def cityList = ['UK London', 'US New York', 'US Birmingham', 'UK Birmingham',].asImmutable()
[
'Sort by city': { city -> city[4..-1] },
'Sort by country': { city -> city[0..3] },
].each{ String label, Closure orderBy ->
println "\n\nBefore ${label}"
cityList.each { println it }
println "\nAfter ${label}"
cityList.sort(false, orderBy).each{ println it }
}</syntaxhighlight>
Output:
<pre>Before Sort by city
UK London
US New York
US Birmingham
UK Birmingham
After Sort by city
US Birmingham
UK Birmingham
UK London
US New York
Before Sort by country
UK London
US New York
US Birmingham
UK Birmingham
After Sort by country
UK London
UK Birmingham
US New York
US Birmingham</pre>
=={{header|Haskell}}==
Line 124 ⟶ 710:
The following sample demonstrates Java's sort stability:
<
import java.util.Comparator;
Line 170 ⟶ 756:
System.out.println();
}
}</
;Output
<pre>
Line 199 ⟶ 785:
=={{header|JavaScript}}==
The ECMAScript 2019 standard defines Array.sort() as stable.
At the time of writing this is already implemented in in Node.js and in the JS interpreters of all major browsers, including Microsoft Edge, but not according to the Mozilla implementations table, the older Internet Explorer. In earlier interpreters, sort stability depends on particular implementations.
<syntaxhighlight lang="javascript">ary = [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]]
print(ary);
Line 207 ⟶ 795:
print(ary);
/* a stable sort will output ["US", "Birmingham"] before ["UK", "Birmingham"] */</
Stable implementations:
Line 223 ⟶ 811:
<pre>UK,London,US,New York,US,Birmingham,UK,Birmingham
UK,Birmingham,US,Birmingham,UK,London,US,New York</pre>
=={{header|jq}}==
As of January 18, 2016 (Commit SHA 7835a72), the builtin sorting filters (notably sort/0 and sort_by/1) are stable; prior to that, stability was platform-dependent. This means that stability is NOT guaranteed in jq 1.5 or earlier. In the following, a version of jq with sorting stability has been used.
<syntaxhighlight lang="jq">[["UK", "London"],
["US", "New York"],
["US", "Birmingham"],
["UK", "Birmingham"]]
| sort_by(.[1])</syntaxhighlight>
Invocation:
<pre>$ jq -c -n -f rc-sort-stability.jq</pre>
{{out}}
<pre>[["US","Birmingham"],["UK","Birmingham"],["UK","London"],["US","New York"]]</pre>
=={{header|Julia}}==
Julia's built-in <code>sort</code> function is documented to be stable by default (although non-stable sort algorithms can optionally be selected).
<pre>
julia> A = [("UK", "London"), ("US", "New York"), ("US", "Birmingham"), ("UK", "Birmingham")];
julia> sort(A, by=x -> x[2])
4-element Array{(ASCIIString,ASCIIString),1}:
("US","Birmingham")
("UK","Birmingham")
("UK","London")
("US","New York")
</pre>
=={{header|Kotlin}}==
The collections in Kotlin's standard library are thin wrappers around the corresponding JDK collections and, since the latter's sort methods are stable, so too are Kotlin's standard sort functions.
<syntaxhighlight lang="scala">// version 1.1.51
fun main(args: Array<String>) {
val cities = listOf("UK London", "US New York", "US Birmingham", "UK Birmingham")
println("Original : $cities")
// sort by country
println("By country : ${cities.sortedBy { it.take(2) } }")
// sort by city
println("By city : ${cities.sortedBy { it.drop(3) } }")
}</syntaxhighlight>
{{out}}
<pre>
Original : [UK London, US New York, US Birmingham, UK Birmingham]
By country : [UK London, UK Birmingham, US New York, US Birmingham]
By city : [US Birmingham, UK Birmingham, UK London, US New York]
</pre>
=={{header|Lasso}}==
Arrays can be sorted in two “built in" ways in Lasso:
<syntaxhighlight lang="lasso">//Single param array:
array->sort
//An array of pairs, order by the right hand element of the pair:
with i in array order by #i->second do => { … }
//The array can also be ordered by multiple values:
with i in array order by #i->second, #i->first do => { … } </syntaxhighlight>
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.
* Note this explanation of sorting does not cover ordering by properties of complex objects, which is also possible using query expressions.
Sort by second value only:
<syntaxhighlight lang="lasso">local(a = array('UK'='London','US'='New York','US'='Birmingham','UK'='Birmingham'))
with i in #a order by #i->second do => {^ #i->first+' - '+#i->second+'\r' ^}</syntaxhighlight>
{{out}}
<pre>US - Birmingham
UK - Birmingham
UK - London
US - New York</pre>
Sort by second then by first:
<syntaxhighlight lang="lasso">local(a = array('UK'='London','US'='New York','US'='Birmingham','UK'='Birmingham'))
with i in #a order by #i->second, #i->first do => {^ #i->first+' - '+#i->second+'\r' ^}</syntaxhighlight>
{{out}}
<pre>UK - Birmingham
US - Birmingham
UK - London
US - New York</pre>
=={{header|Liberty BASIC}}==
LB has build-in SORT routine.
Documentation does not says if it's stable or not.
Example from RC keeps order.
Here's an example showing that SORT indeed unstable.
<syntaxhighlight lang="lb">
randomize 0.5
N=15
dim a(N,2)
for i = 0 to N-1
a(i,1)= int(i/5)
a(i,2)= int(rnd(1)*5)
next
print "Unsorted by column #2"
print "by construction sorted by column #1"
for i = 0 to N-1
print a(i,1), a(i,2)
next
sort a(), 0, N-1, 2
print
print "After sorting by column #2"
print "Notice wrong order by column #1"
for i = 0 to N-1
print a(i,1), a(i,2),
if i=0 then
print
else
if a(i,2) = a(i-1,2) AND a(i,1) < a(i-1,1) then print "bad order" else print
end if
next
</syntaxhighlight>
{{Out}}
<pre>
Unsorted by column #2
by construction sorted by column #1
0 4
0 1
0 1
0 0
0 4
1 1
1 1
1 2
1 1
1 0
2 4
2 3
2 2
2 0
2 4
After sorting by column #2
Notice wrong order by column #1
0 0
1 0
2 0
1 1
1 1
1 1
0 1 bad order
0 1
1 2
2 2
2 3
2 4
0 4 bad order
0 4
2 4
</pre>
=={{header|Lua}}==
The built-in function table.sort is not guaranteed stable.
=={{header|
M2000 has two types of Inventories, objects using a hash algorithm, the normal with unique keys, so a sort statement on this object use quicksort, and a second type, the "queue" type, which can get same keys, and has stable sort.
Here is the stable sort
<syntaxhighlight lang="m2000 interpreter">
Module Stable {
Inventory queue alfa
Stack New {
Data "UK", "London","US", "New York","US", "Birmingham", "UK","Birmingham"
While not empty {
Append alfa, Letter$:=letter$
}
}
sort alfa
k=Each(alfa)
Document A$
NL$={
}
While k {
A$= Eval$(k, k^)+" "+eval$(k)+NL$
}
Clipboard A$ ' write to clipboard
Report A$
}
Call Stable
Output:
UK London
UK Birmingham
US New York
US Birmingham
</syntaxhighlight>
We can sort in on key only. Lets make keys with two fields (based on fields lengths, except for last one)
<syntaxhighlight lang="m2000 interpreter">
Module Stable1 {
Inventory queue alfa
Stack New {
Data "UK London","US New York","US Birmingham", "UK Birmingham"
While not empty {
Append alfa, Letter$
}
}
sort alfa
k=Each(alfa)
Document A$
NL$={
}
While k {
A$= Eval$(k, k^)+NL$
}
Clipboard A$ ' write to clipboard
Report A$
}
Call Stable1
Output:
UK Birmingham
UK London
US Birmingham
US New York
</syntaxhighlight>
Now second column is sorting (but it is one column all, no two columns). So lets see the unstable sort. Because all keys now are unique we just remove queue from Inventory definition.
<syntaxhighlight lang="m2000 interpreter">
Module Stable2 {
Inventory alfa
Stack New {
Data "UK London","US New York","US Birmingham", "UK Birmingham"
While not empty {
Append alfa, Letter$
}
}
sort alfa
k=Each(alfa)
Document A$
NL$={
}
While k {
A$= Eval$(k, k^)+NL$
}
Clipboard A$ ' write to clipboard
Report A$
}
Call Stable2
Output:
UK Birmingham
UK London
US Birmingham
US New York
</syntaxhighlight>
So now we see that using unique keys in either type of inventories we get same output.
By default in inventory queue numbers in keys (in any position) are sorted as numbers.
We can use '''sort alfa as number''' for normal inventory, or ''sort alfa as text''
For ascending/descending sort we can use sort descending alfa as number
If we delete a key in normal inventory we miss the sort order. We can't delete keys in queue inventories, but we can drop from the last append a number of keys. Also Exist() function in queue inventories always find the last entry (for same keys), until that dropped, so with next use of Exist(pointer_to_inventory, key_case_sensitive$) we find the previous one. We can use keys as numbers, but they stored as strings.
=={{header|Mathematica}}/{{header|Wolfram Language}}==
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]]) &]
#[[Ordering[#[[All, 2]]]]] &[mylist]</
gives:
<
{{1, 2, 3}, {5, 4, 3}, {4, 5, 6}, {9, 5, 1}}</
Showing that Sort is unstable, and that by using input[[Ordering[input]]] Ordering provides a way to make a stable sort.
Line 243 ⟶ 1,094:
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
Line 298 ⟶ 1,149:
method compare(lft = Object, rgt = Object) public binary returns int
return (String lft).substring(0, 2).compareTo((String rgt).substring(0, 2))
</syntaxhighlight>
;Output
<pre>
Line 325 ⟶ 1,176:
US Birmingham
</pre>
=={{header|Nim}}==
Default Nim sort in the algorithm module is stable.
<syntaxhighlight lang="nim">import algorithm
const Records = [(country: "UK", city: "London"),
(country: "US", city: "New York"),
(country: "US", city: "Birmingham"),
(country: "UK", city: "Birmingham")]
echo "Original order:"
for record in Records:
echo record.country, " ", record.city
echo()
echo "Sorted by city name:"
for record in Records.sortedByIt(it.city):
echo record.country, " ", record.city
echo()
echo "Sorted by country name:"
for record in Records.sortedByIt(it.country):
echo record.country, " ", record.city</syntaxhighlight>
{{out}}
<pre>Original order:
UK London
US New York
US Birmingham
UK Birmingham
Sorted by city name:
US Birmingham
UK Birmingham
UK London
US New York
Sorted by country name:
UK London
UK Birmingham
US New York
US Birmingham</pre>
=={{header|OCaml}}==
OCaml's [http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALsort List.sort] and [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html#VALsort Array.sort] functions are not guaranteed to be stable. The stable versions are [http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALstable_sort List.stable_sort] and [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html#VALstable_sort Array.stable_sort], respectively.
=={{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.
<syntaxhighlight lang="oorexx">/* Rexx */
Do
cities = .array~of('UK London', 'US New York', 'US Birmingham', 'UK Birmingham',)
Say; Say 'Original table'
Call display cities
Say; Say 'Unstable sort on city'
sorted = cities~copy
sorted~sortWith(.ColumnComparator~new(4, 20))
Call display sorted
Say; Say 'Stable sort on city'
sorted = cities~copy
sorted~stableSortWith(.ColumnComparator~new(4, 20))
Call display sorted
Say; Say 'Unstable sort on country'
sorted = cities~copy
sorted~sortWith(.ColumnComparator~new(1, 2))
Call display sorted
Say; Say 'Stable sort on country'
sorted = cities~copy
sorted~stableSortWith(.ColumnComparator~new(1, 2))
Call display sorted
Return
End
Exit
display: Procedure
Do
Use arg CT
Say '-'~copies(80)
Loop c_ over CT
Say c_
End c_
Return
End
Exit
</syntaxhighlight>
;Output
<pre>
Original table
--------------------------------------------------------------------------------
UK London
US New York
US Birmingham
UK Birmingham
Unstable sort on city
--------------------------------------------------------------------------------
UK Birmingham
US Birmingham
UK London
US New York
Stable sort on city
--------------------------------------------------------------------------------
US Birmingham
UK Birmingham
UK London
US New York
Unstable sort on country
--------------------------------------------------------------------------------
UK London
UK Birmingham
US Birmingham
US New York
Stable sort on country
--------------------------------------------------------------------------------
UK London
UK Birmingham
US New York
US Birmingham
</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)'
Line 355 ⟶ 1,332:
MESSAGE
cc[1] SKIP(1) cc[2]
VIEW-AS ALERT-BOX.</
'''Output:'''
Line 385 ⟶ 1,362:
Example:
<
Cities = ['UK'#'London'
'US'#'New York'
Line 395 ⟶ 1,372:
%% sort by country; NOT stable because '<' is not reflexiv
{Show {Sort Cities fun {$ A B} A.1 < B.1 end}}</
=={{header|PARI/GP}}==
Pari's <code>vecsort</code> is stable, see 3.8.60 in the User's Guide. In particular, it uses a merge sort.
=={{header|Pascal}}==
Standard Pascal has no built-in routine for sorting. The RTL of FreePascal uses Quicksort for TList, TFPList and TStringList in the Classes unit. In many places in the standard libraries fgl and in generics.collections the sort is configurable provided the programmer implements a sort.
=={{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]:
<syntaxhighlight lang
=={{header|
The standard sort method is merge sort, which is apparently stable, though I would be reluctant to guarantee that, or rely on it, especially given that a simple tag sort is irrefutably stable since it explicitly orders by tag (aka original position) within any equal keys.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">test</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"UK"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"London"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"US"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"New York"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"US"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Birmingham"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"UK"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Birmingham"</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">---------------------
-- probably stable --
---------------------</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cmp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cmp</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)),{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-----------------------
-- guaranteed stable --
-----------------------</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">tag_cmp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">test</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (see note)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tags</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tag_cmp</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)))</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tags</span><span style="color: #0000FF;">),{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
{{`US`, `Birmingham`},
{`UK`, `Birmingham`},
{`UK`, `London`},
{`US`, `New York`}}
{{`US`, `Birmingham`},
{`UK`, `Birmingham`},
{`UK`, `London`},
{`US`, `New York`}}
</pre>
Commenting out the c=0 fixup in tag_cmp makes it unstable, or rather probably stable wrt the shuffle, and sometimes shows the first two lines flipped, whereas the active line guarantees original (pre-shuffle) ordering, even if an unstable underlying sort method were used.
Of course test=sort(test) guarantees alphabetical on second column within matching first column. Lastly, preserving a primary tag sort ordering within a secondary tag sort is a bit more mind-bending, but even that is not particularly difficult.
=={{header|PHP}}==
Line 429 ⟶ 1,437:
=={{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|Quackery}}==
The inbuilt sort is stable.
=={{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.
<syntaxhighlight lang="r">
# First, define a bernoulli sample, of length 26.
x <- sample(c(0, 1), 26, replace=T)
Line 456 ⟶ 1,469:
# 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
</syntaxhighlight>
=={{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.
<syntaxhighlight lang="racket">
#lang racket
(sort '(("UK" "London")
("US" "New York")
("US" "Birmingham")
("UK" "Birmingham"))
string<? #:key first)
;; -> (("UK" "London") ("UK" "Birmingham")
;; ("US" "New York") ("US" "Birmingham"))
(sort '(("UK" "London")
("US" "New York")
("US" "Birmingham")
("UK" "Birmingham"))
string<? #:key second)
;; -> '(("US" "Birmingham") ("UK" "Birmingham")
;; ("UK" "London") ("US" "New York"))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
The [https://docs.raku.org/language/101-basics#index-entry-stable_sort sort] built-in (available as sub and method) is stable.
Short demonstration for sorting only on the second item of each array:
<syntaxhighlight lang="raku" line>use v6;
my @cities =
['UK', 'London'],
['US', 'New York'],
['US', 'Birmingham'],
['UK', 'Birmingham'],
;
.say for @cities.sort: { .[1] };</syntaxhighlight>
=={{header|REBOL}}==
<
blk: [
Line 476 ⟶ 1,529:
UK Birmingham
]
sort/skip/compare blk 2 func [a b] [either a < b [-1] [either a > b [1] [0]]]</
=={{header|REXX}}==
<syntaxhighlight lang="rexx"></syntaxhighlight>
/*REXX program sorts a (stemmed) array */
/* replacing the wrong program published here earlier */
call gena /*generate the array elements (strings)*/
call show 'before sort' /*show the before array elements. */
call stableSort
exit
/*----------------------------------------------------------------------------*/
stableSort: procedure expose a.
parse Value '' With l1 l2
Do i=1 To a.0
parse Var a.i f1 f2
f2=translate(f2,'_',' ')
If pos(f1,l1)=0 Then l1=l1 f1
If pos(f2,l2)=0 Then l2=l2 f2
End
l1=wordsort(l1)
l2=wordsort(l2)
Say 'sorted
Do While l1<>''
Parse Var l1 f1s l1
Do i=1 To a.0
parse Var a.i f1 f2
If f1=f1s Then
Say a.i
End
End
Say ''
Say 'sorted by city'
Do While l2<>''
Parse Var l2 f2s l2
Do i=1 To a.0
parse Var a.i f1 f2
If translate(f2,'_',' ')=f2s Then
Say a.i
End
End
/*---------------------------------------------------------------------------------*/
gena: a.0=0
Call store 'UK London'
Call store 'US New York'
Call store 'US Birmingham'
Call store 'UK Birmingham'
Return
store:
z=a.0+1
a.z=arg(1)
a.0=z
Return
show:
Say arg(1)
do i=1 To a.0
say a.i
End
Return
/**********************************************************************
* Sort the list of words supplied as argument. Return the sorted list
**********************************************************************/
Parse Arg wl
wa.=''
wa.0=0
Do While
Parse Var wl w wl
Do i=1 To wa.0
If wa.i>w Then Leave
End
If i<=wa.0 Then Do
Do j=wa.0 To i By -1
ii=j+1
wa.ii=wa.j
End
End
wa.i=w
wa.0=wa.0+1
End
swl=''
Do i=1 To wa.0
swl=swl wa.i
End
Return strip(swl)</syntaxhighlight>
{{out|output|text= when using the default list:}}
<pre>
K:\>rexx sso
before sort
UK London
US New York
Line 533 ⟶ 1,624:
UK Birmingham
sorted by country
UK London
UK Birmingham
US New York
US Birmingham
US Birmingham
UK Birmingham
UK London
US New York
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
aList = [["UK", "London"],
["US", "New York"],
["US", "Birmingham"],
["UK", "Birmingham"]]
see sort(aList,2)
</syntaxhighlight>
=={{header|Ruby}}==
Line 566 ⟶ 1,650:
{{works with|MRI|1.8.7, 1.9.2}}
<
["US", "New York"],
["US", "Birmingham"],
Line 572 ⟶ 1,656:
p ary.sort {|a,b| a[1] <=> b[1]}
# MRI reverses the Birminghams:
# => [["UK", "Birmingham"], ["US", "Birmingham"], ["UK", "London"], ["US", "New York"]]</
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)]
Line 579 ⟶ 1,663:
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
Line 598 ⟶ 1,682:
sort_by {|x| n += 1; [(yield x), n]}
end
end</
<
["US", "New York"],
["US", "Birmingham"],
Line 607 ⟶ 1,691:
# => [["US", "Birmingham"], ["UK", "Birmingham"], ["UK", "London"], ["US", "New York"]]
p ary.stable_sort_by {|x| x[1]}
# => [["US", "Birmingham"], ["UK", "Birmingham"], ["UK", "London"], ["US", "New York"]]</
=={{header|Rust}}==
Rust's builtin sorts (.sort(), .sort_by(...), .sort_by_key(...)) are all stable
<syntaxhighlight lang="rust">fn main() {
let country_city = [
("UK", "London"),
("US", "New York"),
("US", "Birmingham"),
("UK", "Birmingham"),
];
let mut city_sorted = country_city.clone();
city_sorted.sort_by_key(|k| k.1);
let mut country_sorted = country_city.clone();
country_sorted.sort_by_key(|k| k.0);
println!("Original:");
for x in &country_city {
println!("{} {}", x.0, x.1);
}
println!("\nWhen sorted by city:");
for x in &city_sorted {
println!("{} {}", x.0, x.1);
}
println!("\nWhen sorted by county:");
for x in &country_sorted {
println!("{} {}", x.0, x.1);
}
}</syntaxhighlight>
Output: <pre>Original:
UK London
US New York
US Birmingham
UK Birmingham
When sorted by city:
US Birmingham
UK Birmingham
UK London
US New York
When sorted by county:
UK London
UK Birmingham
US New York
US Birmingham</pre>
=={{header|Scala}}==
Line 617 ⟶ 1,752:
Examples:
<
list: List[(Int, Char)] = List((1,c), (1,b), (2,a))
Line 635 ⟶ 1,770:
scala> cities.sortBy(_ substring 4)
res47: Seq[String] = ArrayBuffer(US Birmingham, UK Birmingham, UK London, US New York)</
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:
<
cityArray: Array[String] = Array(UK London, US New York, US Birmingham, UK Birmingham)
Line 643 ⟶ 1,778:
scala> cityArray
res56: Array[String] = Array(US Birmingham, UK Birmingham, UK London, US New York)</
=={{header|Sidef}}==
Sidef uses the stable merge-sort algorithm for sorting an array.
<syntaxhighlight lang="ruby">var table = [
<UK London>,
<US New\ York>,
<US Birmingham>,
<UK Birmingham>,
];
table.sort {|a,b| a[0] <=> b[0]}.each { |col|
say "#{col[0]} #{col[1]}"
}</syntaxhighlight>
{{out}}
<pre>UK London
UK Birmingham
US New York
US Birmingham</pre>
=={{header|Stata}}==
See '''[http://www.stata.com/help.cgi?sort sort]''' in Stata help. The command has a ''stable'' option to ensure sort stability.
=={{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|TXR}}==
TXR provides a number of sorting functions. <code>sort</code> and <code>nsort</code> (destructive variant) are not stable for vectors and strings, but are stable for lists.
The functions <code>ssort</code> and <code>snsort</code> counterparts are stable for all sequence kinds.
In addition, there are caching variants of all these functions: <code>csort</code>, <code>cnsort</code>, <code>cssort</code> and <code>csnsort</code>. They respectively have the same stability properties as their counterparts without the leading <code>c</code>.
TXR Lisp originally had one sorting function called <code>sort</code>, which was destructive, like the <code>sort</code> in Common Lisp. That function was renamed to <code>nsort</code>, and <code>sort</code> became the name of a non-destructive function. That happened in TXR 238, released in May, 2020.
=={{header|Wren}}==
{{libheader|Wren-sort}}
Of the six sorting algorithms supported by the above module, two (merge and insertion) are stable and the other four (quick, heap, selection and shell) are unstable.
Below we illustrate the points made in the task description using the stable insertion sort.
<syntaxhighlight lang="wren">import "./sort" for Cmp, Sort
var data = [ ["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"] ]
// for sorting by country
var cmp = Fn.new { |p1, p2| Cmp.string.call(p1[0], p2[0]) }
// for sorting by city
var cmp2 = Fn.new { |p1, p2| Cmp.string.call(p1[1], p2[1]) }
System.print("Initial data:")
System.print(" " + data.join("\n "))
System.print("\nSorted by country:")
var data2 = data.toList
Sort.insertion(data2, cmp)
System.print(" " + data2.join("\n "))
System.print("\nSorted by city:")
var data3 = data.toList
Sort.insertion(data3, cmp2)
System.print(" " + data3.join("\n "))</syntaxhighlight>
{{out}}
<pre>
Initial data:
[UK, London]
[US, New York]
[US, Birmingham]
[UK, Birmingham]
Sorted by country:
[UK, London]
[UK, Birmingham]
[US, New York]
[US, Birmingham]
Sorted by city:
[US, Birmingham]
[UK, Birmingham]
[UK, London]
[US, New York]
</pre>
=={{header|XPL0}}==
There is no built-in sort routine in XPL0. The 32-bit versions are
distributed with xpllib, which provides an integer sort routine. This
uses the Quicksort algorithm, which is unstable.
=={{header|zkl}}==
zkl's sort methods don't mention stability or columns, they are comparison based.
<syntaxhighlight lang="zkl">fcn sortByColumn(list,col)
{ list.sort('wrap(city1,city2){ city1[col]<city2[col] }) }</syntaxhighlight>
<syntaxhighlight lang="zkl">cities:=List(
T("UK", "London"), T("US", "New York"),
T("US", "Birmingham"),T("UK", "Birmingham"), );
sortByColumn(cities,0).concat("\n").println("\n------");
sortByColumn(cities,1).concat("\n").println();</syntaxhighlight>
{{out}}
<pre>
L("UK","London")
L("UK","Birmingham")
L("US","New York")
L("US","Birmingham")
------
L("UK","Birmingham")
L("US","Birmingham")
L("UK","London")
L("US","New York")
</pre>
|