Sort stability
You are encouraged to solve this task according to the task description, using any language you may know.
When sorting records in a table by a particular column or field, a stable sort will always retain the relative order of records that have the same key.
For 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).
UK London US New York US Birmingham UK Birmingham
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).
- 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.
(This Wikipedia table shows the stability of some common sort routines).
AutoHotkey
Autohotkey has got a build-in sorting method for tables, which is stable. <lang AutoHotkey>Table = ( UK, London US, New York US, Birmingham UK, Birmingham )
Gui, Margin, 6 Gui, -MinimizeBox Gui, Add, ListView, r5 w260 Grid, Orig.Position|Country|City Loop, Parse, Table, `n, `r {
StringSplit, out, A_LoopField, `,, %A_Space%
LV_Add("", A_Index, out1, out2)
} LV_ModifyCol(1, "77 Center") LV_ModifyCol(2, "100 Center") LV_ModifyCol(3, 79) Gui, Add, Button, w80, Restore Order Gui, Add, Button, x+10 wp, Sort Countries Gui, Add, Button, x+10 wp, Sort Cities Gui, Show,, Sort stability Return
GuiClose: GuiEscape: ExitApp
ButtonRestoreOrder:
LV_ModifyCol(1, "Sort")
Return
ButtonSortCountries:
LV_ModifyCol(2, "Sort")
Return
ButtonSortCities:
LV_ModifyCol(3, "Sort")
Return</lang>
AWK
<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)
} </lang>
input:
UK London US New York US Birmingham UK Birmingham
output from: GAWK -f SORT_STABILITY.AWK -v field=1 SORT_STABILITY.TXT
after sorting on field 1: UK London UK Birmingham US New York US Birmingham
output from: GAWK -f SORT_STABILITY.AWK -v field=2 SORT_STABILITY.TXT
after sorting on field 2: US Birmingham UK Birmingham UK London US New York
BBC BASIC
The supplied SORTLIB library currently uses a Shell Sort, so it is not stable.
C
There is no built-in function in C language. stdlib which comes with any C implementation is required to provide a qsort() 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.
C++
C++ standard library's std::sort() function is not guaranteed stable. The stable analog of it is the std::stable_sort() function. In addition, std::list's sort() method is guaranteed stable.
C#
The .NET library documentation for Array.Sort() says that it uses quicksort and is unstable.[1]
Clojure
Clojure's sort and sort-by functions are implemented using Java's java.utils.Array.sort methods, which are guaranteed stable.
Common Lisp
Common Lisp provides the two functions sort and stable-sort.
Each of these functions can sort arbitrary objects using a given predicate function, the input to which can be altered by the optional key parameter.
(eg; sorting file names based upon file sizes, the predicate might be < and the key could be a function that transforms the file's name into its size)
D
In the std.algorithm Phobos v.2 module there is SwapStrategy that defines the swapping strategy for algorithms like sort and partition.
Unstable, stable and semistable (in algorithms that partition ranges in two, semistable preserves stability on just the left of the partition point) are supported.
Déjà Vu
The included sorting algorithm, sort, is stable.
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: <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)</lang>
- Output:
[{"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"}]
Note: If the function does not return true, the sorting is not stable and the order of equal terms may be shuffled: <lang elixir>IO.inspect Enum.sort(cities, fn a,b -> elem(a,0) > elem(b,0) end)</lang>
- Output:
[{"US", "Birmingham"}, {"US", "New York"}, {"UK", "Birmingham"}, {"UK", "London"}]
Erlang
The function lists:sort/1 is not documented as stable. The function lists:keysort/2 is documented as stable.
Factor
The sorting vocabulary implements a stable sort. sorting docs
F#
Array.sort is not stable.
List.sort and Seq.sort are stable.
GAP
<lang gap># According to section 21.18 of the reference manual, Sort is not stable (it's a Shell sort).
- However, SortingPerm is stable. We will see it on an example, showing indexes of elements after the sort.
n := 20; L := List([1 .. n], i -> Random("AB"));
- "AABABBBABBABAABABBAB"
p := SortingPerm(L);
- (3,10,15,17,18,19,9,14,7,13,6,12,16,8,4)(5,11)
a := Permuted(L, p);; b := Permuted([1 .. n], p);;
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 ] ]</lang>
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.
Groovy
Groovy's Collection.sort(), Object[].sort(), Map.sort(), and their various and sundry overloads all use the same stable sort algorithm.
Example:
<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 }
}</lang>
Output:
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
Haskell
Haskell's sort and sortBy functions are guaranteed stable.[2]
Icon and Unicon
Icon and Unicon use Quick Sort internally. As described in The Implementation of Icon and Unicon: a Compendium] sorting is done by the standard C library routine qsort which is not guaranteed to be stable.
Note(1): The built-in sort handles lists of mixed types by sorting first by type and then value. No coercion of types is performed. The sort order of types is: &null, integer, real, string, cset, procedure, list, set, table, record.
J
J's grade primitive /:, and therefore its sort (such as /:~), are guaranteed stable.
From the dictionary page for /: : "Elements of /:y that select equal elements of y are in ascending order."
Java
Java's Collections.sort() and Arrays.sort() methods are guaranteed stable.
The following sample demonstrates Java's sort stability: <lang Java>import java.util.Arrays; import java.util.Comparator;
public class RJSortStability {
public static void main(String[] args) {
String[] cityList = { "UK London", "US New York", "US Birmingham", "UK Birmingham", };
String[] cn = cityList.clone();
System.out.println("\nBefore sort:");
for (String city : cn) {
System.out.println(city);
}
// sort by city
Arrays.sort(cn, new Comparator<String>() {
public int compare(String lft, String rgt) {
return lft.substring(4).compareTo(rgt.substring(4));
}
});
System.out.println("\nAfter sort on city:");
for (String city : cn) {
System.out.println(city);
}
cn = cityList.clone();
System.out.println("\nBefore sort:");
for (String city : cn) {
System.out.println(city);
}
// sort by country
Arrays.sort(cn, new Comparator<String>() {
public int compare(String lft, String rgt) {
return lft.substring(0, 2).compareTo(rgt.substring(0, 2));
}
});
System.out.println("\nAfter sort on country:");
for (String city : cn) {
System.out.println(city);
}
System.out.println(); }
}</lang>
- Output
Before sort: UK London US New York US Birmingham UK Birmingham After sort on city: US Birmingham UK Birmingham UK London US New York Before sort: UK London US New York US Birmingham UK Birmingham After sort on country: UK London UK Birmingham US New York US Birmingham
JavaScript
The ECMA standard does not specify what sorting algorithm to use, so it depends upon the implementation.
<lang javascript>ary = [["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"]] print(ary);
ary.sort(function(a,b){return (a[1]<b[1] ? -1 : (a[1]>b[1] ? 1 : 0))}); print(ary);
/* a stable sort will output ["US", "Birmingham"] before ["UK", "Birmingham"] */</lang>
Stable implementations:
UK,London,US,New York,US,Birmingham,UK,Birmingham US,Birmingham,UK,Birmingham,UK,London,US,New York
Not stable:
UK,London,US,New York,US,Birmingham,UK,Birmingham UK,Birmingham,US,Birmingham,UK,London,US,New York
Julia
Julia's built-in sort function is documented to be stable by default (although non-stable sort algorithms can optionally be selected).
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")
Lasso
Arrays can be sorted in two “built in" ways in Lasso:
<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 => { … } </lang>
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: <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' ^}</lang>
- Output:
US - Birmingham UK - Birmingham UK - London US - New York
Sort by second then by first: <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' ^}</lang>
- Output:
UK - Birmingham US - Birmingham UK - London US - New York
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. <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 </lang>
- Output:
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
Lua
The built-in function table.sort is not guaranteed stable.
Mathematica
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: <lang Mathematica>mylist = {{1, 2, 3}, {4, 5, 6}, {5, 4, 3}, {9, 5, 1}}; Sort[mylist, (#12 < #22) &]
- [[Ordering[#All, 2]]] &[mylist]</lang>
gives: <lang Mathematica>{{1, 2, 3}, {5, 4, 3}, {9, 5, 1}, {4, 5, 6}} {{1, 2, 3}, {5, 4, 3}, {4, 5, 6}, {9, 5, 1}}</lang> Showing that Sort is unstable, and that by using input[[Ordering[input]]] Ordering provides a way to make a stable sort.
MATLAB
MathWorks' policy seems to be that their built-in sorting algorithm will always be a stable sort across all versions (reference). To check to see if your version of MATLAB provides a stable sort,check the output of command "help sort".
NetRexx
Java's Collections.sort() and Arrays.sort() methods are guaranteed stable. The following sample takes advantage of this to demonstrate sort stability.
<lang NetRexx>/* NetRexx */ options replace format comments java crossref savelog symbols nobinary
class RCSortStability
method main(args = String[]) public constant
cityList = [String "UK London", "US New York", "US Birmingham", "UK Birmingham"]
cn = String[cityList.length]
say say "Before sort:" System.arraycopy(cityList, 0, cn, 0, cityList.length) loop city = 0 to cn.length - 1 say cn[city] end city
cCompNm = Comparator CityComparator() Arrays.sort(cn, cCompNm)
say say "After sort on city:" loop city = 0 to cn.length - 1 say cn[city] end city
say say "Before sort:" System.arraycopy(cityList, 0, cn, 0, cityList.length) loop city = 0 to cn.length - 1 say cn[city] end city
cCompCtry = Comparator CountryComparator() Arrays.sort(cn, cCompCtry)
say say "After sort on country:" loop city = 0 to cn.length - 1 say cn[city] end city say
return
class RCSortStability.CityComparator implements Comparator
method compare(lft = Object, rgt = Object) public binary returns int
return (String lft).substring(4).compareTo((String rgt).substring(4))
class RCSortStability.CountryComparator implements Comparator
method compare(lft = Object, rgt = Object) public binary returns int
return (String lft).substring(0, 2).compareTo((String rgt).substring(0, 2))
</lang>
- Output
Before sort: UK London US New York US Birmingham UK Birmingham After sort on city: US Birmingham UK Birmingham UK London US New York Before sort: UK London US New York US Birmingham UK Birmingham After sort on country: UK London UK Birmingham US New York US Birmingham
Nim
Default Nim sort in the algorithm module is stable.
OCaml
OCaml's List.sort and Array.sort functions are not guaranteed to be stable. The stable versions are List.stable_sort and Array.stable_sort, respectively.
ooRexx
Open Object Rexx provides sort methods (sort and sortWith(comparator)) for its collection classes. By default these sort methods are implemented via an unstable Quicksort algorithm but the language does provide stable sorting methods (stableSort and stableSortWith(comparator)) implemented via a stable Mergesort algorithm.
<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 </lang>
- Output
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
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. <lang progress>DEFINE TEMP-TABLE tt
FIELD country AS CHAR FORMAT 'x(2)' FIELD city AS CHAR FORMAT 'x(16)' .
DEFINE VARIABLE cc AS CHARACTER EXTENT 2.
CREATE tt. ASSIGN tt.country = 'UK' tt.city = 'London'. CREATE tt. ASSIGN tt.country = 'US' tt.city = 'New York'. CREATE tt. ASSIGN tt.country = 'US' tt.city = 'Birmingham'. CREATE tt. ASSIGN tt.country = 'UK' tt.city = 'Birmingham'.
cc[1] = 'by country~n~n'. FOR EACH tt BY tt.country BY ROWID( tt ):
cc[1] = cc[1] + tt.country + '~t' + tt.city + '~n'.
END.
cc[2] = 'by city~n~n'. FOR EACH tt BY tt.city BY ROWID( tt ):
cc[2] = cc[2] + tt.country + '~t' + tt.city + '~n'.
END.
MESSAGE
cc[1] SKIP(1) cc[2]
VIEW-AS ALERT-BOX.</lang>
Output:
--------------------------- Message --------------------------- by country UK London UK Birmingham US New York US Birmingham by city US Birmingham UK Birmingham UK London US New York --------------------------- OK ---------------------------
Oz
Oz' Sort function is not guaranteed to be stable in the documentation.
However, internally it uses Merge sort and in practice is stable if a reflexive ordering is used, e.g. Value.'=<' or Value.'>='.
Example: <lang oz>declare
Cities = ['UK'#'London'
'US'#'New York'
'US'#'Birmingham'
'UK'#'Birmingham']
in
%% sort by city; stable because '=<' is reflexiv
{Show {Sort Cities fun {$ A B} A.2 =< B.2 end}}
%% sort by country; NOT stable because '<' is not reflexiv
{Show {Sort Cities fun {$ A B} A.1 < B.1 end}}</lang>
PARI/GP
Pari's vecsort is stable, see 3.8.60 in the User's Guide. In particular, it uses a merge sort.
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.
Perl
The stability of Perl's in-built sort function is version-dependent. If you want to guarantee a stable sort from it, you should use the following sort pragma: <lang perl>use sort 'stable';</lang>
Perl 6
The sort built-in (available as sub and method) is stable.
Short demonstration for sorting only on the second item of each array: <lang perl6>use v6; my @cities =
['UK', 'London'], ['US', 'New York'], ['US', 'Birmingham'], ['UK', 'Birmingham'], ;
.say for @cities.sort: { .[1] };</lang>
PHP
PHP uses QuickSort for most of its sort functions so it is unstable. [3]
PicoLisp
The sort function is unstable
PureBasic
PureBasic's includes two built-in sort functions for arrays, SortArray() and SortStructuredArray(), and two built-in sort functions for linked lists, SortList() and SortStructuredList(). Sorting of linked lists is stable and uses a merge-sort, while sorting for arrays is unstable and uses a quicksort.
Python
Python's in-built sorted function as well as the sort method of lists are guaranteed stable (since version 2.3). (For even more information on the underlying routine, wp:timsort, see this).
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.
<lang R>
- First, define a bernoulli sample, of length 26.
x <- sample(c(0, 1), 26, replace=T)
x
- [1] 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0
- Give names to the entries. "letters" is a builtin value
names(x) <- letters
x
- a b c d e f g h i j k l m n o p q r s t u v w x y z
- 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0
- The unstable one, see how "a" appears after "l" now
sort(x, method="quick")
- z h s u e q x n j r t v w y p o m l a i g f d c b k
- 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
- The stable sort, letters are ordered in each section
sort(x, method="shell")
- 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
</lang>
Racket
Racket comes with a standard sort function, which is documented [here]. It is documented as stable.
<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"))
</lang>
REBOL
<lang rebol>; REBOL's sort function is not stable by default. You need to use a custom comparator to make it so.
blk: [
[UK London] [US New-York] [US Birmingham] [UK Birmingham]
] sort/compare blk func [a b] [either a/2 < b/2 [-1] [either a/2 > b/2 [1] [0]]]
- Note that you can also do a stable sort without nested blocks.
blk: [
UK London US New-York US Birmingham UK Birmingham
] sort/skip/compare blk 2 func [a b] [either a < b [-1] [either a > b [1] [0]]]</lang>
REXX
Classic REXX has no built-in routines for sorting, so this programming example uses a classic bubble sort (which is stable). <lang rexx>/*REXX program sorts a (stemmed) array using a (stable) bubble─sort algorithm. */ call gen@ /*generate the array elements (strings)*/ call show 'before sort' /*show the before array elements. */
say copies('▒', 50) /*show a separator line between shows. */
call bubbleSort # /*invoke the bubble sort. */ call show ' after sort' /*show the after array elements. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ bubbleSort: procedure expose @.; parse arg n; m=n-1 /*N: number of array elements. */
do m=m for m by -1 until ok; ok=1 /*keep sorting array until done.*/
do j=1 for m; k=j+1; if @.j<=@.k then iterate /*Not out─of─order?*/
_=@.j; @.j=@.k; @.k=_; ok=0 /*swap 2 elements; flag as ¬done*/
end /*j*/
end /*m*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/ gen@: @.=; @.1 = 'UK London'
@.2 = 'US New York'
@.3 = 'US Birmingham'
@.4 = 'UK Birmingham'
do #=1 while @.#\==; end; #=#-1 /*determine how many entries in list. */
return
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: do j=1 for #; say ' element' right(j,length(#)) arg(1)":" @.j; end; return</lang> output using the default list:
element 1 before sort: UK London
element 2 before sort: US New York
element 3 before sort: US Birmingham
element 4 before sort: UK Birmingham
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
element 1 after sort: UK Birmingham
element 2 after sort: UK London
element 3 after sort: US Birmingham
element 4 after sort: US New York
Ring
<lang ring> aList = [["UK", "London"],
["US", "New York"],
["US", "Birmingham"],
["UK", "Birmingham"]]
see sort(aList,2) </lang>
Ruby
Ruby's built-in sort methods (Array#sort, Array#sort!, Array#sort_by!, Enumerable#sort and Enumerable#sort_by) are not stable. MRI uses quicksort, which is not stable (1). It seems that stable sorting is not worth the performance trade-off; MRI rejected a proposal to switch to a stable sort (2).
<lang ruby>ary = [["UK", "London"],
["US", "New York"],
["US", "Birmingham"],
["UK", "Birmingham"]]
p ary.sort {|a,b| a[1] <=> b[1]}
- MRI reverses the Birminghams:
- => [["UK", "Birmingham"], ["US", "Birmingham"], ["UK", "London"], ["US", "New York"]]</lang>
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. (3)
Stable sort in Ruby
To code a stable sort, without implementing another sorting algorithm (such as merge sort), use a Schwartzian transform.
<lang ruby>class Array
def stable_sort
n = -1
if block_given?
collect {|x| n += 1; [x, n]
}.sort! {|a, b|
c = yield a[0], b[0]
if c.nonzero? then c else a[1] <=> b[1] end
}.collect! {|x| x[0]}
else
sort_by {|x| n += 1; [x, n]}
end
end
def stable_sort_by
block_given? or return enum_for(:stable_sort_by)
n = -1
sort_by {|x| n += 1; [(yield x), n]}
end
end</lang>
<lang ruby>ary = [["UK", "London"],
["US", "New York"],
["US", "Birmingham"],
["UK", "Birmingham"]]
p ary.stable_sort {|a, b| a[1] <=> b[1]}
- => [["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"]]</lang>
Scala
There are two sort methods defined on Seq, which is the base collection trait for all sequences. The methods are sortWith and sortBy, and differ only on the argument used. The first expects a function that will implement the "less than" method for the type of the sequence. The second expects a function from the type of the sequence into any type for which there is an Ordering, plus an implicit Ordering of the proper type.
The sort is stable.
Examples: <lang scala>scala> val list = List((1, 'c'), (1, 'b'), (2, 'a')) list: List[(Int, Char)] = List((1,c), (1,b), (2,a))
scala> val srt1 = list.sortWith(_._2 < _._2) srt1: List[(Int, Char)] = List((2,a), (1,b), (1,c))
scala> val srt2 = srt1.sortBy(_._1) // Ordering[Int] is implicitly defined srt2: List[(Int, Char)] = List((1,b), (1,c), (2,a))
scala> val cities = """
| |UK London
| |US New York
| |US Birmingham
| |UK Birmingham
| |""".stripMargin.lines.filterNot(_ isEmpty).toSeq
cities: Seq[String] = ArrayBuffer(UK London, US New York, US Birmingham, UK Birmingham)
scala> cities.sortBy(_ substring 4) res47: Seq[String] = ArrayBuffer(US Birmingham, UK Birmingham, UK London, US New York)</lang> Besides that, there is the object scala.util.Sorting, which provides quickSort and stableSort. The former is only provided on Array, but the latter is provided over both Array and Seq. These sorts operate in-place, with the one over Seq returning a sorted Array. Here is one example: <lang scala>scala> val cityArray = cities.toArray cityArray: Array[String] = Array(UK London, US New York, US Birmingham, UK Birmingham)
scala> scala.util.Sorting.stableSort(cityArray, (_: String).substring(4) < (_: String).substring(4))
scala> cityArray res56: Array[String] = Array(US Birmingham, UK Birmingham, UK London, US New York)</lang>
Sidef
Sidef uses the stable merge-sort algorithm for sorting an array. <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]}"
}</lang>
- Output:
UK London UK Birmingham US New York US Birmingham
Tcl
Tcl's built-in lsort command implements a stable sort. It has been guaranteed to be stable since Tcl 8.0. Internally, it uses the mergesort algorithm.
zkl
zkl's sort methods don't mention stability or columns, they are comparison based. <lang zkl>fcn sortByColumn(list,col)
{ list.sort('wrap(city1,city2){ city1[col]<city2[col] }) }</lang>
<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();</lang>
- Output:
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")
- Programming Tasks
- Sorting
- AutoHotkey
- AWK
- BBC BASIC
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- Déjà Vu
- Elixir
- Erlang
- Factor
- F Sharp
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Julia
- Lasso
- Liberty BASIC
- Lua
- Mathematica
- MATLAB
- NetRexx
- Nim
- OCaml
- OoRexx
- OpenEdge/Progress
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PureBasic
- Python
- R
- Racket
- REBOL
- REXX
- Ring
- Ruby
- Scala
- Sidef
- Tcl
- Zkl