Sort stability: Difference between revisions

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

<br><br>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/*******************************************/

/* Constantes file */

.align 4

TableCities:

.quad szFR

.quad szUS

.quad szUK

.quad szUS

.quad szUS

/*********************************/

/* UnInitialized data */

.bss

sZoneConv: .skip 24

/*********************************/

/* code section */

.global main

main: // entry of program

bl displayTable

ldr x0,qAdrszMessSortName

bl affichageMess

 

mov x1,0 // not use in routine

mov x3,#city_name // sort by city name

mov x4,#'A' // alphanumeric

bl displayTable

bl affichageMess

 

mov x1,0 // not use in routine

mov x3,#city_country // sort by city country

mov x4,#'A' // alphanumeric

bl displayTable

qAdrTableCities: .quad TableCities

qAdrszMessSortName: .quad szMessSortName

qAdrszMessSortCountry: .quad szMessSortCountry

/******************************************************************/

/******************************************************************/

/* x0 contains the address of table */

/* x2 contains the number of element */

/* x3 contains the offset of area sort */

/* x4 contains the type of area sort N numeric A alpha */

bl comparArea

cmp x0,0

 

/******************************************************************/

/* comparison sort area */

stp x6,x7,[sp,-16]! // save registers

stp x8,x9,[sp,-16]! // save registers

beq 1f

blt 10f

bgt 11f

b 12f

2:

ldrb w9,[x6,x8] // byte string 1

bgt 11f

blt 10f

cmp w9,#0 // end string 1

beq 12f // end comparaison

b 2b // and loop

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

mov x2,x0 // table address

mov x3,0

1: // loop display table

ldr x0,qAdrsMessResult

bl strInsertAtCharInc // put name in message

bl strInsertAtCharInc // insert result at @ character

bl affichageMess // display message

add x3,x3,1

ldr x0,qAdrszCarriageReturn

bl affichageMess

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

<pre>

Name : London country : UK

Name : Paris country : US

</pre>

=={{header|Ada}}==

[[Ada 83]] and [[Ada 95]] do not provide a standard sort utility.

The task description doesn't specify what form the "table" takes, but here it's assumed to be a tab-delimited text.

 

US New York

US Birmingham

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 & ¬

 

{{output}}

US Birmingham

UK Birmingham

US New York

US Birmingham"

 

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

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

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.

 

print(ary);

 

print(ary);

 

 

Stable implementations:

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.

 

["US", "New York"],

["US", "Birmingham"],

["UK", "Birmingham"]]

 

Invocation:

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

 

fun main(args: Array<String>) {

// sort by city

println("By city : ${cities.sortedBy { it.drop(3) } }")

 

{{out}}

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>

 

Here is the stable sort

Module Stable {

Inventory queue alfa

US Birmingham

 

 

 

We can sort in on key only. Lets make keys with two fields (based on fields lengths, except for last one)

 

Module Stable1 {

Inventory queue alfa

US New York

 

 

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.

Module Stable2 {

Inventory alfa

US New York

 

 

So now we see that using unique keys in either type of inventories we get same output.

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.

 

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

{{Out}}

<pre>

</pre>

 

=={{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|Raku}}==

 

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

my @cities =

['UK', 'London'],

;

 

 

=={{header|REBOL}}==

 

blk: [

UK Birmingham

]

 

=={{header|REXX}}==

{{out|output|text=&nbsp; when using the default list:}}

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

Rust's builtin sorts (.sort(), .sort_by(...), .sort_by_key(...)) are all stable

 

let country_city = [

("UK", "London"),

println!("{} {}", x.0, x.1);

}

 

Output: <pre>Original:

 

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

=={{header|TXR}}==

 

 

 

=={{header|Wren}}==

 

Below we illustrate the points made in the task description using the stable insertion sort.

 

var data = [ ["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"] ]

var data3 = data.toList

Sort.insertion(data3, cmp2)

 

{{out}}

[US, New York]

</pre>

 

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