Sort stability: Difference between revisions

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

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program stableSort641.s */

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

.include "../includeARM64.inc"

<pre>

Name : London country : UK

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

=={{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]]) &]

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.

 

const Records = [(country: "UK", city: "London"),

echo "Sorted by country name:"

for record in Records.sortedByIt(it.country):

 

{{out}}

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

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.

<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: #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: #000080;font-style:italic;">-----------------------

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

{{Out}}

<pre>

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

 

=={{header|PHP}}==

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>