Sorting and Related Functions¶
Julia has an extensive, flexible API for sorting and interacting with already-sorted arrays of values. By default, Julia picks reasonable algorithms and sorts in standard ascending order:
julia>sort([2,3,1])3-elementArray{Int64,1}:123
You can easily sort in reverse order as well:
julia>sort([2,3,1],rev=true)3-elementArray{Int64,1}:321
To sort an array in-place, use the “bang” version of the sort function:
julia>a=[2,3,1];julia>sort!(a);julia>a3-elementArray{Int64,1}:123
Instead of directly sorting an array, you can compute a permutation of the array’s indices that puts the array into sorted order:
julia>v=randn(5)5-elementArray{Float64,1}:0.2972880.382396-0.597634-0.0104452-0.839027julia>p=sortperm(v)5-elementArray{Int64,1}:53412julia>v[p]5-elementArray{Float64,1}:-0.839027-0.597634-0.01044520.2972880.382396
Arrays can easily be sorted according to an arbitrary transformation of their values:
julia>sort(v,by=abs)5-elementArray{Float64,1}:-0.01044520.2972880.382396-0.597634-0.839027
Or in reverse order by a transformation:
julia>sort(v,by=abs,rev=true)5-elementArray{Float64,1}:-0.839027-0.5976340.3823960.297288-0.0104452
If needed, the sorting algorithm can be chosen:
julia>sort(v,alg=InsertionSort)5-elementArray{Float64,1}:-0.839027-0.597634-0.01044520.2972880.382396
All the sorting and order related functions rely on a “less than”
relation defining a total order on the values to be manipulated. The
isless
function is invoked by default, but the relation can be
specified via the lt
keyword.
Sorting Functions¶
sort!
(v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])¶Sort the vector
v
in place.QuickSort
is used by default for numeric arrays whileMergeSort
is used for other arrays. You can specify an algorithm to use via thealg
keyword (see Sorting Algorithms for available algorithms). Theby
keyword lets you provide a function that will be applied to each element before comparison; thelt
keyword allows providing a custom “less than” function; userev=true
to reverse the sorting order. These options are independent and can be used together in all possible combinations: if bothby
andlt
are specified, thelt
function is applied to the result of theby
function;rev=true
reverses whatever ordering specified via theby
andlt
keywords.
sort
(v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])¶Variant of
sort!
that returns a sorted copy ofv
leavingv
itself unmodified.
sort
(A, dim, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])Sort a multidimensional array
A
along the given dimension.
sortperm
(v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])¶Return a permutation vector of indices of
v
that puts it in sorted order. Specifyalg
to choose a particular sorting algorithm (see Sorting Algorithms).MergeSort
is used by default, and since it is stable, the resulting permutation will be the lexicographically first one that puts the input array into sorted order – i.e. indices of equal elements appear in ascending order. If you choose a non-stable sorting algorithm such asQuickSort
, a different permutation that puts the array into order may be returned. The order is specified using the same keywords assort!
.See also
sortperm!()
sortperm!
(ix, v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false,] [initialized=false])¶Like
sortperm
, but accepts a preallocated index vectorix
. Ifinitialized
isfalse
(the default), ix is initialized to contain the values1:length(v)
.See also
sortperm()
sortrows
(A, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])¶Sort the rows of matrix
A
lexicographically.
sortcols
(A, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])¶Sort the columns of matrix
A
lexicographically.
Order-Related Functions¶
issorted
(v, [by=<transform>,] [lt=<comparison>,] [rev=false])¶Test whether a vector is in sorted order. The
by
,lt
andrev
keywords modify what order is considered to be sorted just as they do forsort
.
searchsorted
(a, x, [by=<transform>,] [lt=<comparison>,] [rev=false])¶Returns the range of indices of
a
which compare as equal tox
according to the order specified by theby
,lt
andrev
keywords, assuming thata
is already sorted in that order. Returns an empty range located at the insertion point ifa
does not contain values equal tox
.
searchsortedfirst
(a, x, [by=<transform>,] [lt=<comparison>,] [rev=false])¶Returns the index of the first value in
a
greater than or equal tox
, according to the specified order. Returnslength(a)+1
ifx
is greater than all values ina
.
searchsortedlast
(a, x, [by=<transform>,] [lt=<comparison>,] [rev=false])¶Returns the index of the last value in
a
less than or equal tox
, according to the specified order. Returns0
ifx
is less than all values ina
.
select!
(v, k, [by=<transform>,] [lt=<comparison>,] [rev=false])¶Partially sort the vector
v
in place, according to the order specified byby
,lt
andrev
so that the value at indexk
(or range of adjacent values ifk
is a range) occurs at the position where it would appear if the array were fully sorted via a non-stable algorithm. Ifk
is a single index, that value is returned; ifk
is a range, an array of values at those indices is returned. Note thatselect!
does not fully sort the input array.
select
(v, k, [by=<transform>,] [lt=<comparison>,] [rev=false])¶Variant of
select!
which copiesv
before partially sorting it, thereby returning the same thing asselect!
but leavingv
unmodified.
selectperm
(v, k, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])¶Return a partial permutation of the vector
v
, according to the order specified byby
,lt
andrev
, so thatv[output]
returns the firstk
(or range of adjacent values ifk
is a range) values of a fully sorted version ofv
. Ifk
is a single index (Integer), an array of the firstk
indices is returned; ifk
is a range, an array of those indices is returned. Note that the handling of integer values fork
is different fromselect
in that it returns a vector ofk
elements instead of just thek
th element. Also note that this is equivalent to, but more efficient than, callingsortperm(...)[k]
selectperm!
(ix, v, k, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false,] [initialized=false])¶Like
selectperm
, but accepts a preallocated index vectorix
. Ifinitialized
isfalse
(the default), ix is initialized to contain the values1:length(ix)
.
Sorting Algorithms¶
There are currently four sorting algorithms available in base Julia:
InsertionSort
QuickSort
PartialQuickSort(k)
MergeSort
InsertionSort
is an O(n^2) stable sorting algorithm. It is efficient
for very small n
, and is used internally by QuickSort
.
QuickSort
is an O(n log n) sorting algorithm which is in-place,
very fast, but not stable – i.e. elements which are considered
equal will not remain in the same order in which they originally
appeared in the array to be sorted. QuickSort
is the default
algorithm for numeric values, including integers and floats.
PartialQuickSort(k)
is similar to QuickSort
, but the output array
is only sorted up to index k
if k
is an integer, or in the range
of k
if k
is an OrdinalRange
. For example:
x=rand(1:500,100)k=50k2=50:100s=sort(x;alg=QuickSort)ps=sort(x;alg=PartialQuickSort(k))qs=sort(x;alg=PartialQuickSort(k2))map(issorted,(s,ps,qs))# => (true, false, false)map(x->issorted(x[1:k]),(s,ps,qs))# => (true, true, false)map(x->issorted(x[k2]),(s,ps,qs))# => (true, false, true)s[1:k]==ps[1:k]# => trues[k2]==qs[k2]# => true
MergeSort
is an O(n log n) stable sorting algorithm but is not
in-place – it requires a temporary array of half the size of the
input array – and is typically not quite as fast as QuickSort
.
It is the default algorithm for non-numeric data.
The default sorting algorithms are chosen on the basis that they are
fast and stable, or appear to be so. For numeric types indeed,
QuickSort
is selected as it is faster and indistinguishable in
this case from a stable sort (unless the array records its mutations
in some way). The stability property comes at a non-negligible cost,
so if you don’t need it, you may want to explicitly specify your
preferred algorithm, e.g. sort!(v,alg=QuickSort)
.
The mechanism by which Julia picks default sorting algorithms is
implemented via the Base.Sort.defalg
function. It allows a
particular algorithm to be registered as the default in all sorting
functions for specific arrays. For example, here are the two default
methods from sort.jl:
defalg(v::AbstractArray)=MergeSortdefalg{T<:Number}(v::AbstractArray{T})=QuickSort
As for numeric arrays, choosing a non-stable default algorithm for array types for which the notion of a stable sort is meaningless (i.e. when two values comparing equal can not be distinguished) may make sense.