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

 

 

<br>

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

<br><br>

 

=={{header|Ada}}==

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

<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 mut city_sorted = country_city.clone();

let mut country_sorted = country_city.clone();

country_sorted.sort_by_key(|k| k.0);

 

println!("Original:");

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