Sorting and Related Functions¶
Julia has an extensive, flexible API for sorting and interacting with already-sorted arrays of values. For many users, sorting in standard ascending order, letting Julia pick reasonable default algorithms will be sufficient:
julia> sort([2,3,1])
3-element Array{Int64,1}:
1
2
3
You can easily sort in reverse order as well:
julia> sort([2,3,1], rev=true)
3-element Array{Int64,1}:
3
2
1
To sort an array in-place, use the “bang” version of the sort function:
julia> a = [2,3,1];
julia> sort!(a);
julia> a
3-element Array{Int64,1}:
1
2
3
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-element Array{Float64,1}:
0.297288
0.382396
-0.597634
-0.0104452
-0.839027
julia> p = sortperm(v)
5-element Array{Int64,1}:
5
3
4
1
2
julia> v[p]
5-element Array{Float64,1}:
-0.839027
-0.597634
-0.0104452
0.297288
0.382396
Arrays can easily be sorted acording to an arbitrary transformation of their values:
julia> sort(v, by=abs)
5-element Array{Float64,1}:
-0.0104452
0.297288
0.382396
-0.597634
-0.839027
Or in reverse order by a transformation:
julia> sort(v, by=abs, rev=true)
5-element Array{Float64,1}:
-0.839027
-0.597634
0.382396
0.297288
-0.0104452
Reasonable sorting algorithms are used by default, but you can choose other algorithms as well:
julia> sort(v, alg=InsertionSort)
5-element Array{Float64,1}:
-0.839027
-0.597634
-0.0104452
0.297288
0.382396
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!
.
-
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. Ifk
is a single index, that values is returned; ifk
is a range, an array of values at those indices is returned. Note thatselect!
does not fully sort the input array, but does leave the returned elements where they would be if the array were fully sorted.
-
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.
Sorting Algorithms¶
There are currently three sorting algorithms available in base Julia:
InsertionSort
QuickSort
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.
MergeSort
is an O(n log n) stable sorting algorithm but is not
in-place – it requires a temporary array of equal size to the
input array – and is typically not quite as fast as QuickSort
.
It is the default algorithm for non-numeric data.
The sort functions select a reasonable default algorithm, depending on
the type of the array to be sorted. To force a specific algorithm to be
used for sort
or other soring functions, supply alg=<algorithm>
as a keyword argument after the array to be sorted.