| Line | Exclusive | Inclusive | Code |
|---|---|---|---|
| 1 | # This file is a part of Julia. License is MIT: https://julialang.org/license | ||
| 2 | |||
| 3 | module Sort | ||
| 4 | |||
| 5 | import ..@__MODULE__, ..parentmodule | ||
| 6 | const Base = parentmodule(@__MODULE__) | ||
| 7 | using .Base.Order | ||
| 8 | using .Base: copymutable, LinearIndices, length, (:), | ||
| 9 | eachindex, axes, first, last, similar, zip, OrdinalRange, | ||
| 10 | AbstractVector, @inbounds, AbstractRange, @eval, @inline, Vector, @noinline, | ||
| 11 | AbstractMatrix, AbstractUnitRange, isless, identity, eltype, >, <, <=, >=, |, +, -, *, !, | ||
| 12 | extrema, sub_with_overflow, add_with_overflow, oneunit, div, getindex, setindex!, | ||
| 13 | length, resize!, fill, Missing, require_one_based_indexing | ||
| 14 | |||
| 15 | using .Base: >>>, !== | ||
| 16 | |||
| 17 | import .Base: | ||
| 18 | sort, | ||
| 19 | sort!, | ||
| 20 | issorted, | ||
| 21 | sortperm, | ||
| 22 | to_indices | ||
| 23 | |||
| 24 | export # also exported by Base | ||
| 25 | # order-only: | ||
| 26 | issorted, | ||
| 27 | searchsorted, | ||
| 28 | searchsortedfirst, | ||
| 29 | searchsortedlast, | ||
| 30 | # order & algorithm: | ||
| 31 | sort, | ||
| 32 | sort!, | ||
| 33 | sortperm, | ||
| 34 | sortperm!, | ||
| 35 | partialsort, | ||
| 36 | partialsort!, | ||
| 37 | partialsortperm, | ||
| 38 | partialsortperm!, | ||
| 39 | # algorithms: | ||
| 40 | InsertionSort, | ||
| 41 | QuickSort, | ||
| 42 | MergeSort, | ||
| 43 | PartialQuickSort | ||
| 44 | |||
| 45 | export # not exported by Base | ||
| 46 | Algorithm, | ||
| 47 | DEFAULT_UNSTABLE, | ||
| 48 | DEFAULT_STABLE, | ||
| 49 | SMALL_ALGORITHM, | ||
| 50 | SMALL_THRESHOLD | ||
| 51 | |||
| 52 | |||
| 53 | ## functions requiring only ordering ## | ||
| 54 | |||
| 55 | function issorted(itr, order::Ordering) | ||
| 56 | y = iterate(itr) | ||
| 57 | y === nothing && return true | ||
| 58 | prev, state = y | ||
| 59 | y = iterate(itr, state) | ||
| 60 | while y !== nothing | ||
| 61 | this, state = y | ||
| 62 | lt(order, this, prev) && return false | ||
| 63 | prev = this | ||
| 64 | y = iterate(itr, state) | ||
| 65 | end | ||
| 66 | return true | ||
| 67 | end | ||
| 68 | |||
| 69 | """ | ||
| 70 | issorted(v, lt=isless, by=identity, rev:Bool=false, order::Ordering=Forward) | ||
| 71 | |||
| 72 | Test whether a vector is in sorted order. The `lt`, `by` and `rev` keywords modify what | ||
| 73 | order is considered to be sorted just as they do for [`sort`](@ref). | ||
| 74 | |||
| 75 | # Examples | ||
| 76 | ```jldoctest | ||
| 77 | julia> issorted([1, 2, 3]) | ||
| 78 | true | ||
| 79 | |||
| 80 | julia> issorted([(1, "b"), (2, "a")], by = x -> x[1]) | ||
| 81 | true | ||
| 82 | |||
| 83 | julia> issorted([(1, "b"), (2, "a")], by = x -> x[2]) | ||
| 84 | false | ||
| 85 | |||
| 86 | julia> issorted([(1, "b"), (2, "a")], by = x -> x[2], rev=true) | ||
| 87 | true | ||
| 88 | ``` | ||
| 89 | """ | ||
| 90 | issorted(itr; | ||
| 91 | lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) = | ||
| 92 | issorted(itr, ord(lt,by,rev,order)) | ||
| 93 | |||
| 94 | function partialsort!(v::AbstractVector, k::Union{Integer,OrdinalRange}, o::Ordering) | ||
| 95 | inds = axes(v, 1) | ||
| 96 | sort!(v, first(inds), last(inds), PartialQuickSort(k), o) | ||
| 97 | maybeview(v, k) | ||
| 98 | end | ||
| 99 | |||
| 100 | maybeview(v, k) = view(v, k) | ||
| 101 | maybeview(v, k::Integer) = v[k] | ||
| 102 | |||
| 103 | """ | ||
| 104 | partialsort!(v, k; by=<transform>, lt=<comparison>, rev=false) | ||
| 105 | |||
| 106 | Partially sort the vector `v` in place, according to the order specified by `by`, `lt` and | ||
| 107 | `rev` so that the value at index `k` (or range of adjacent values if `k` is a range) occurs | ||
| 108 | at the position where it would appear if the array were fully sorted via a non-stable | ||
| 109 | algorithm. If `k` is a single index, that value is returned; if `k` is a range, an array of | ||
| 110 | values at those indices is returned. Note that `partialsort!` does not fully sort the input | ||
| 111 | array. | ||
| 112 | |||
| 113 | # Examples | ||
| 114 | ```jldoctest | ||
| 115 | julia> a = [1, 2, 4, 3, 4] | ||
| 116 | 5-element Array{Int64,1}: | ||
| 117 | 1 | ||
| 118 | 2 | ||
| 119 | 4 | ||
| 120 | 3 | ||
| 121 | 4 | ||
| 122 | |||
| 123 | julia> partialsort!(a, 4) | ||
| 124 | 4 | ||
| 125 | |||
| 126 | julia> a | ||
| 127 | 5-element Array{Int64,1}: | ||
| 128 | 1 | ||
| 129 | 2 | ||
| 130 | 3 | ||
| 131 | 4 | ||
| 132 | 4 | ||
| 133 | |||
| 134 | julia> a = [1, 2, 4, 3, 4] | ||
| 135 | 5-element Array{Int64,1}: | ||
| 136 | 1 | ||
| 137 | 2 | ||
| 138 | 4 | ||
| 139 | 3 | ||
| 140 | 4 | ||
| 141 | |||
| 142 | julia> partialsort!(a, 4, rev=true) | ||
| 143 | 2 | ||
| 144 | |||
| 145 | julia> a | ||
| 146 | 5-element Array{Int64,1}: | ||
| 147 | 4 | ||
| 148 | 4 | ||
| 149 | 3 | ||
| 150 | 2 | ||
| 151 | 1 | ||
| 152 | ``` | ||
| 153 | """ | ||
| 154 | partialsort!(v::AbstractVector, k::Union{Integer,OrdinalRange}; | ||
| 155 | lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) = | ||
| 156 | partialsort!(v, k, ord(lt,by,rev,order)) | ||
| 157 | |||
| 158 | """ | ||
| 159 | partialsort(v, k, by=<transform>, lt=<comparison>, rev=false) | ||
| 160 | |||
| 161 | Variant of [`partialsort!`](@ref) which copies `v` before partially sorting it, thereby returning the | ||
| 162 | same thing as `partialsort!` but leaving `v` unmodified. | ||
| 163 | """ | ||
| 164 | partialsort(v::AbstractVector, k::Union{Integer,OrdinalRange}; kws...) = | ||
| 165 | partialsort!(copymutable(v), k; kws...) | ||
| 166 | |||
| 167 | # This implementation of `midpoint` is performance-optimized but safe | ||
| 168 | # only if `lo <= hi`. | ||
| 169 | midpoint(lo::T, hi::T) where T<:Integer = lo + ((hi - lo) >>> 0x01) | ||
| 170 | midpoint(lo::Integer, hi::Integer) = midpoint(promote(lo, hi)...) | ||
| 171 | |||
| 172 | # reference on sorted binary search: | ||
| 173 | # http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary | ||
| 174 | |||
| 175 | # index of the first value of vector a that is greater than or equal to x; | ||
| 176 | # returns length(v)+1 if x is greater than all values in v. | ||
| 177 | function searchsortedfirst(v::AbstractVector, x, lo::T, hi::T, o::Ordering) where T<:Integer | ||
| 178 | u = T(1) | ||
| 179 | lo = lo - u | ||
| 180 | hi = hi + u | ||
| 181 | @inbounds while lo < hi - u | ||
| 182 | m = midpoint(lo, hi) | ||
| 183 | if lt(o, v[m], x) | ||
| 184 | lo = m | ||
| 185 | else | ||
| 186 | hi = m | ||
| 187 | end | ||
| 188 | end | ||
| 189 | return hi | ||
| 190 | end | ||
| 191 | |||
| 192 | # index of the last value of vector a that is less than or equal to x; | ||
| 193 | # returns 0 if x is less than all values of v. | ||
| 194 | function searchsortedlast(v::AbstractVector, x, lo::T, hi::T, o::Ordering) where T<:Integer | ||
| 195 | u = T(1) | ||
| 196 | lo = lo - u | ||
| 197 | hi = hi + u | ||
| 198 | @inbounds while lo < hi - u | ||
| 199 | m = midpoint(lo, hi) | ||
| 200 | if lt(o, x, v[m]) | ||
| 201 | hi = m | ||
| 202 | else | ||
| 203 | lo = m | ||
| 204 | end | ||
| 205 | end | ||
| 206 | return lo | ||
| 207 | end | ||
| 208 | |||
| 209 | # returns the range of indices of v equal to x | ||
| 210 | # if v does not contain x, returns a 0-length range | ||
| 211 | # indicating the insertion point of x | ||
| 212 | function searchsorted(v::AbstractVector, x, ilo::T, ihi::T, o::Ordering) where T<:Integer | ||
| 213 | u = T(1) | ||
| 214 | lo = ilo - u | ||
| 215 | hi = ihi + u | ||
| 216 | @inbounds while lo < hi - u | ||
| 217 | m = midpoint(lo, hi) | ||
| 218 | if lt(o, v[m], x) | ||
| 219 | lo = m | ||
| 220 | elseif lt(o, x, v[m]) | ||
| 221 | hi = m | ||
| 222 | else | ||
| 223 | a = searchsortedfirst(v, x, max(lo,ilo), m, o) | ||
| 224 | b = searchsortedlast(v, x, m, min(hi,ihi), o) | ||
| 225 | return a : b | ||
| 226 | end | ||
| 227 | end | ||
| 228 | return (lo + 1) : (hi - 1) | ||
| 229 | end | ||
| 230 | |||
| 231 | function searchsortedlast(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering) | ||
| 232 | require_one_based_indexing(a) | ||
| 233 | if step(a) == 0 | ||
| 234 | lt(o, x, first(a)) ? 0 : length(a) | ||
| 235 | else | ||
| 236 | n = round(Integer, clamp((x - first(a)) / step(a) + 1, 1, length(a))) | ||
| 237 | lt(o, x, a[n]) ? n - 1 : n | ||
| 238 | end | ||
| 239 | end | ||
| 240 | |||
| 241 | function searchsortedfirst(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering) | ||
| 242 | require_one_based_indexing(a) | ||
| 243 | if step(a) == 0 | ||
| 244 | lt(o, first(a), x) ? length(a) + 1 : 1 | ||
| 245 | else | ||
| 246 | n = round(Integer, clamp((x - first(a)) / step(a) + 1, 1, length(a))) | ||
| 247 | lt(o, a[n] ,x) ? n + 1 : n | ||
| 248 | end | ||
| 249 | end | ||
| 250 | |||
| 251 | function searchsortedlast(a::AbstractRange{<:Integer}, x::Real, o::DirectOrdering) | ||
| 252 | require_one_based_indexing(a) | ||
| 253 | h = step(a) | ||
| 254 | if h == 0 | ||
| 255 | lt(o, x, first(a)) ? 0 : length(a) | ||
| 256 | elseif h > 0 && x < first(a) | ||
| 257 | firstindex(a) - 1 | ||
| 258 | elseif h > 0 && x >= last(a) | ||
| 259 | lastindex(a) | ||
| 260 | elseif h < 0 && x > first(a) | ||
| 261 | firstindex(a) - 1 | ||
| 262 | elseif h < 0 && x <= last(a) | ||
| 263 | lastindex(a) | ||
| 264 | else | ||
| 265 | fld(floor(Integer, x) - first(a), h) + 1 | ||
| 266 | end | ||
| 267 | end | ||
| 268 | |||
| 269 | function searchsortedfirst(a::AbstractRange{<:Integer}, x::Real, o::DirectOrdering) | ||
| 270 | require_one_based_indexing(a) | ||
| 271 | h = step(a) | ||
| 272 | if h == 0 | ||
| 273 | lt(o, first(a), x) ? length(a)+1 : 1 | ||
| 274 | elseif h > 0 && x <= first(a) | ||
| 275 | firstindex(a) | ||
| 276 | elseif h > 0 && x > last(a) | ||
| 277 | lastindex(a) + 1 | ||
| 278 | elseif h < 0 && x >= first(a) | ||
| 279 | firstindex(a) | ||
| 280 | elseif h < 0 && x < last(a) | ||
| 281 | lastindex(a) + 1 | ||
| 282 | else | ||
| 283 | -fld(floor(Integer, -x) + first(a), h) + 1 | ||
| 284 | end | ||
| 285 | end | ||
| 286 | |||
| 287 | function searchsortedfirst(a::AbstractRange{<:Integer}, x::Unsigned, o::DirectOrdering) | ||
| 288 | require_one_based_indexing(a) | ||
| 289 | if lt(o, first(a), x) | ||
| 290 | if step(a) == 0 | ||
| 291 | length(a) + 1 | ||
| 292 | else | ||
| 293 | min(cld(x - first(a), step(a)), length(a)) + 1 | ||
| 294 | end | ||
| 295 | else | ||
| 296 | 1 | ||
| 297 | end | ||
| 298 | end | ||
| 299 | |||
| 300 | function searchsortedlast(a::AbstractRange{<:Integer}, x::Unsigned, o::DirectOrdering) | ||
| 301 | require_one_based_indexing(a) | ||
| 302 | if lt(o, x, first(a)) | ||
| 303 | 0 | ||
| 304 | elseif step(a) == 0 | ||
| 305 | length(a) | ||
| 306 | else | ||
| 307 | min(fld(x - first(a), step(a)) + 1, length(a)) | ||
| 308 | end | ||
| 309 | end | ||
| 310 | |||
| 311 | searchsorted(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering) = | ||
| 312 | searchsortedfirst(a, x, o) : searchsortedlast(a, x, o) | ||
| 313 | |||
| 314 | for s in [:searchsortedfirst, :searchsortedlast, :searchsorted] | ||
| 315 | @eval begin | ||
| 316 | $s(v::AbstractVector, x, o::Ordering) = (inds = axes(v, 1); $s(v,x,first(inds),last(inds),o)) | ||
| 317 | $s(v::AbstractVector, x; | ||
| 318 | lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) = | ||
| 319 | $s(v,x,ord(lt,by,rev,order)) | ||
| 320 | end | ||
| 321 | end | ||
| 322 | |||
| 323 | """ | ||
| 324 | searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false) | ||
| 325 | |||
| 326 | Return the range of indices of `a` which compare as equal to `x` (using binary search) | ||
| 327 | according to the order specified by the `by`, `lt` and `rev` keywords, assuming that `a` | ||
| 328 | is already sorted in that order. Return an empty range located at the insertion point | ||
| 329 | if `a` does not contain values equal to `x`. | ||
| 330 | |||
| 331 | # Examples | ||
| 332 | ```jldoctest | ||
| 333 | julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match | ||
| 334 | 3:3 | ||
| 335 | |||
| 336 | julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches | ||
| 337 | 4:5 | ||
| 338 | |||
| 339 | julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle | ||
| 340 | 3:2 | ||
| 341 | |||
| 342 | julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end | ||
| 343 | 7:6 | ||
| 344 | |||
| 345 | julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start | ||
| 346 | 1:0 | ||
| 347 | ``` | ||
| 348 | """ searchsorted | ||
| 349 | |||
| 350 | """ | ||
| 351 | searchsortedfirst(a, x; by=<transform>, lt=<comparison>, rev=false) | ||
| 352 | |||
| 353 | Return the index of the first value in `a` greater than or equal to `x`, according to the | ||
| 354 | specified order. Return `length(a) + 1` if `x` is greater than all values in `a`. | ||
| 355 | `a` is assumed to be sorted. | ||
| 356 | |||
| 357 | # Examples | ||
| 358 | ```jldoctest | ||
| 359 | julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # single match | ||
| 360 | 3 | ||
| 361 | |||
| 362 | julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # multiple matches | ||
| 363 | 4 | ||
| 364 | |||
| 365 | julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle | ||
| 366 | 3 | ||
| 367 | |||
| 368 | julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9) # no match, insert at end | ||
| 369 | 7 | ||
| 370 | |||
| 371 | julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no match, insert at start | ||
| 372 | 1 | ||
| 373 | ``` | ||
| 374 | """ searchsortedfirst | ||
| 375 | |||
| 376 | """ | ||
| 377 | searchsortedlast(a, x; by=<transform>, lt=<comparison>, rev=false) | ||
| 378 | |||
| 379 | Return the index of the last value in `a` less than or equal to `x`, according to the | ||
| 380 | specified order. Return `0` if `x` is less than all values in `a`. `a` is assumed to | ||
| 381 | be sorted. | ||
| 382 | |||
| 383 | # Examples | ||
| 384 | ```jldoctest | ||
| 385 | julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # single match | ||
| 386 | 3 | ||
| 387 | |||
| 388 | julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # multiple matches | ||
| 389 | 5 | ||
| 390 | |||
| 391 | julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle | ||
| 392 | 2 | ||
| 393 | |||
| 394 | julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # no match, insert at end | ||
| 395 | 6 | ||
| 396 | |||
| 397 | julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # no match, insert at start | ||
| 398 | 0 | ||
| 399 | ``` | ||
| 400 | """ searchsortedlast | ||
| 401 | |||
| 402 | |||
| 403 | ## sorting algorithms ## | ||
| 404 | |||
| 405 | abstract type Algorithm end | ||
| 406 | |||
| 407 | struct InsertionSortAlg <: Algorithm end | ||
| 408 | struct QuickSortAlg <: Algorithm end | ||
| 409 | struct MergeSortAlg <: Algorithm end | ||
| 410 | |||
| 411 | """ | ||
| 412 | PartialQuickSort{T <: Union{Integer,OrdinalRange}} | ||
| 413 | |||
| 414 | Indicate that a sorting function should use the partial quick sort | ||
| 415 | algorithm. Partial quick sort returns the smallest `k` elements sorted from smallest | ||
| 416 | to largest, finding them and sorting them using [`QuickSort`](@ref). | ||
| 417 | |||
| 418 | Characteristics: | ||
| 419 | * *not stable*: does not preserve the ordering of elements which | ||
| 420 | compare equal (e.g. "a" and "A" in a sort of letters which | ||
| 421 | ignores case). | ||
| 422 | * *in-place* in memory. | ||
| 423 | * *divide-and-conquer*: sort strategy similar to [`MergeSort`](@ref). | ||
| 424 | """ | ||
| 425 | struct PartialQuickSort{T <: Union{Integer,OrdinalRange}} <: Algorithm | ||
| 426 | k::T | ||
| 427 | end | ||
| 428 | |||
| 429 | |||
| 430 | """ | ||
| 431 | InsertionSort | ||
| 432 | |||
| 433 | Indicate that a sorting function should use the insertion sort | ||
| 434 | algorithm. Insertion sort traverses the collection one element | ||
| 435 | at a time, inserting each element into its correct, sorted position in | ||
| 436 | the output list. | ||
| 437 | |||
| 438 | Characteristics: | ||
| 439 | * *stable*: preserves the ordering of elements which | ||
| 440 | compare equal (e.g. "a" and "A" in a sort of letters | ||
| 441 | which ignores case). | ||
| 442 | * *in-place* in memory. | ||
| 443 | * *quadratic performance* in the number of elements to be sorted: | ||
| 444 | it is well-suited to small collections but should not be used for large ones. | ||
| 445 | """ | ||
| 446 | const InsertionSort = InsertionSortAlg() | ||
| 447 | """ | ||
| 448 | QuickSort | ||
| 449 | |||
| 450 | Indicate that a sorting function should use the quick sort | ||
| 451 | algorithm, which is *not* stable. | ||
| 452 | |||
| 453 | Characteristics: | ||
| 454 | * *not stable*: does not preserve the ordering of elements which | ||
| 455 | compare equal (e.g. "a" and "A" in a sort of letters which | ||
| 456 | ignores case). | ||
| 457 | * *in-place* in memory. | ||
| 458 | * *divide-and-conquer*: sort strategy similar to [`MergeSort`](@ref). | ||
| 459 | * *good performance* for large collections. | ||
| 460 | """ | ||
| 461 | const QuickSort = QuickSortAlg() | ||
| 462 | """ | ||
| 463 | MergeSort | ||
| 464 | |||
| 465 | Indicate that a sorting function should use the merge sort | ||
| 466 | algorithm. Merge sort divides the collection into | ||
| 467 | subcollections and repeatedly merges them, sorting each | ||
| 468 | subcollection at each step, until the entire | ||
| 469 | collection has been recombined in sorted form. | ||
| 470 | |||
| 471 | Characteristics: | ||
| 472 | * *stable*: preserves the ordering of elements which compare | ||
| 473 | equal (e.g. "a" and "A" in a sort of letters which ignores | ||
| 474 | case). | ||
| 475 | * *not in-place* in memory. | ||
| 476 | * *divide-and-conquer* sort strategy. | ||
| 477 | """ | ||
| 478 | const MergeSort = MergeSortAlg() | ||
| 479 | |||
| 480 | const DEFAULT_UNSTABLE = QuickSort | ||
| 481 | const DEFAULT_STABLE = MergeSort | ||
| 482 | const SMALL_ALGORITHM = InsertionSort | ||
| 483 | const SMALL_THRESHOLD = 20 | ||
| 484 | |||
| 485 | function sort!(v::AbstractVector, lo::Integer, hi::Integer, ::InsertionSortAlg, o::Ordering) | ||
| 486 | @inbounds for i = lo+1:hi | ||
| 487 | j = i | ||
| 488 | 10 (1 %) |
10 (100 %)
samples spent calling
getindex
x = v[i]
|
|
| 489 | while j > lo | ||
| 490 | 11 (1 %) | if lt(o, x, v[j-1]) | |
| 491 | 1 (0 %) |
1 (100 %)
samples spent calling
getindex
v[j] = v[j-1]
|
|
| 492 | j -= 1 | ||
| 493 | continue | ||
| 494 | end | ||
| 495 | break | ||
| 496 | end | ||
| 497 | 4 (0 %) | 4 (0 %) | v[j] = x |
| 498 | end | ||
| 499 | 2 (0 %) | 2 (0 %) | return v |
| 500 | end | ||
| 501 | |||
| 502 | # selectpivot! | ||
| 503 | # | ||
| 504 | # Given 3 locations in an array (lo, mi, and hi), sort v[lo], v[mi], v[hi]) and | ||
| 505 | # choose the middle value as a pivot | ||
| 506 | # | ||
| 507 | # Upon return, the pivot is in v[lo], and v[hi] is guaranteed to be | ||
| 508 | # greater than the pivot | ||
| 509 | |||
| 510 | @inline function selectpivot!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering) | ||
| 511 | @inbounds begin | ||
| 512 | mi = midpoint(lo, hi) | ||
| 513 | |||
| 514 | # sort v[mi] <= v[lo] <= v[hi] such that the pivot is immediately in place | ||
| 515 | if lt(o, v[lo], v[mi]) | ||
| 516 | v[mi], v[lo] = v[lo], v[mi] | ||
| 517 | end | ||
| 518 | |||
| 519 | if lt(o, v[hi], v[lo]) | ||
| 520 | if lt(o, v[hi], v[mi]) | ||
| 521 | v[hi], v[lo], v[mi] = v[lo], v[mi], v[hi] | ||
| 522 | else | ||
| 523 | v[hi], v[lo] = v[lo], v[hi] | ||
| 524 | end | ||
| 525 | end | ||
| 526 | |||
| 527 | # return the pivot | ||
| 528 | return v[lo] | ||
| 529 | end | ||
| 530 | end | ||
| 531 | |||
| 532 | # partition! | ||
| 533 | # | ||
| 534 | # select a pivot, and partition v according to the pivot | ||
| 535 | |||
| 536 | function partition!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering) | ||
| 537 | pivot = selectpivot!(v, lo, hi, o) | ||
| 538 | # pivot == v[lo], v[hi] > pivot | ||
| 539 | i, j = lo, hi | ||
| 540 | @inbounds while true | ||
| 541 | i += 1; j -= 1 | ||
| 542 | while lt(o, v[i], pivot); i += 1; end; | ||
| 543 | while lt(o, pivot, v[j]); j -= 1; end; | ||
| 544 | i >= j && break | ||
| 545 | v[i], v[j] = v[j], v[i] | ||
| 546 | end | ||
| 547 | v[j], v[lo] = pivot, v[j] | ||
| 548 | |||
| 549 | # v[j] == pivot | ||
| 550 | # v[k] >= pivot for k > j | ||
| 551 | # v[i] <= pivot for i < j | ||
| 552 | return j | ||
| 553 | end | ||
| 554 | |||
| 555 | function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::QuickSortAlg, o::Ordering) | ||
| 556 | @inbounds while lo < hi | ||
| 557 | hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o) | ||
| 558 | j = partition!(v, lo, hi, o) | ||
| 559 | if j-lo < hi-j | ||
| 560 | # recurse on the smaller chunk | ||
| 561 | # this is necessary to preserve O(log(n)) | ||
| 562 | # stack space in the worst case (rather than O(n)) | ||
| 563 | lo < (j-1) && sort!(v, lo, j-1, a, o) | ||
| 564 | lo = j+1 | ||
| 565 | else | ||
| 566 | j+1 < hi && sort!(v, j+1, hi, a, o) | ||
| 567 | hi = j-1 | ||
| 568 | end | ||
| 569 | end | ||
| 570 | return v | ||
| 571 | end | ||
| 572 | |||
| 573 |
4393 (527 %)
samples spent in sort!
function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::MergeSortAlg, o::Ordering, t=similar(v,0))
7 (0 %) (ex.), 1880 (43 %) (incl.) when called from sort! line 581 3 (0 %) (ex.), 1911 (44 %) (incl.) when called from sort! line 580 1 (0 %) (ex.), 602 (14 %) (incl.) when called from sort! line 574 |
||
| 574 | 602 (72 %) |
602 (100 %)
samples spent calling
sort!
@inbounds if lo < hi
|
|
| 575 | 1 (0 %) | 29 (3 %) |
28 (100 %)
samples spent calling
sort!
hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
|
| 576 | |||
| 577 | m = midpoint(lo, hi) | ||
| 578 | (length(t) < m-lo+1) && resize!(t, m-lo+1) | ||
| 579 | |||
| 580 | 1911 (229 %) |
1911 (100 %)
samples spent calling
sort!
sort!(v, lo, m, a, o, t)
|
|
| 581 | 1880 (225 %) |
1880 (100 %)
samples spent calling
sort!
sort!(v, m+1, hi, a, o, t)
|
|
| 582 | |||
| 583 | i, j = 1, lo | ||
| 584 | 1 (0 %) |
1 (100 %)
samples spent calling
<=
while j <= m
|
|
| 585 | 71 (9 %) | t[i] = v[j] | |
| 586 | i += 1 | ||
| 587 | 9 (1 %) |
9 (100 %)
samples spent calling
+
j += 1
|
|
| 588 | end | ||
| 589 | |||
| 590 | i, k = 1, lo | ||
| 591 | 11 (1 %) | 11 (1 %) | while k < j <= hi |
| 592 | 373 (45 %) |
34 (9 %)
samples spent calling
getindex
if lt(o, v[j], t[i])
1 (0 %) samples spent calling getindex 338 (91 %) samples spent calling lt |
|
| 593 | 25 (3 %) |
25 (100 %)
samples spent calling
setindex!
v[k] = v[j]
|
|
| 594 | 26 (3 %) |
26 (100 %)
samples spent calling
+
j += 1
|
|
| 595 | else | ||
| 596 | 23 (3 %) |
23 (100 %)
samples spent calling
setindex!
v[k] = t[i]
|
|
| 597 | 25 (3 %) |
25 (100 %)
samples spent calling
+
i += 1
|
|
| 598 | end | ||
| 599 | 10 (1 %) |
10 (100 %)
samples spent calling
+
k += 1
|
|
| 600 | end | ||
| 601 | while k < j | ||
| 602 | v[k] = t[i] | ||
| 603 | k += 1 | ||
| 604 | i += 1 | ||
| 605 | end | ||
| 606 | end | ||
| 607 | |||
| 608 | return v | ||
| 609 | end | ||
| 610 | |||
| 611 | function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::PartialQuickSort{<:Integer}, | ||
| 612 | o::Ordering) | ||
| 613 | @inbounds while lo < hi | ||
| 614 | hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o) | ||
| 615 | j = partition!(v, lo, hi, o) | ||
| 616 | if j >= a.k | ||
| 617 | # we don't need to sort anything bigger than j | ||
| 618 | hi = j-1 | ||
| 619 | elseif j-lo < hi-j | ||
| 620 | # recurse on the smaller chunk | ||
| 621 | # this is necessary to preserve O(log(n)) | ||
| 622 | # stack space in the worst case (rather than O(n)) | ||
| 623 | lo < (j-1) && sort!(v, lo, j-1, a, o) | ||
| 624 | lo = j+1 | ||
| 625 | else | ||
| 626 | (j+1) < hi && sort!(v, j+1, hi, a, o) | ||
| 627 | hi = j-1 | ||
| 628 | end | ||
| 629 | end | ||
| 630 | return v | ||
| 631 | end | ||
| 632 | |||
| 633 | |||
| 634 | function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::PartialQuickSort{T}, | ||
| 635 | o::Ordering) where T<:OrdinalRange | ||
| 636 | @inbounds while lo < hi | ||
| 637 | hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o) | ||
| 638 | j = partition!(v, lo, hi, o) | ||
| 639 | |||
| 640 | if j <= first(a.k) | ||
| 641 | lo = j+1 | ||
| 642 | elseif j >= last(a.k) | ||
| 643 | hi = j-1 | ||
| 644 | else | ||
| 645 | if j-lo < hi-j | ||
| 646 | lo < (j-1) && sort!(v, lo, j-1, a, o) | ||
| 647 | lo = j+1 | ||
| 648 | else | ||
| 649 | hi > (j+1) && sort!(v, j+1, hi, a, o) | ||
| 650 | hi = j-1 | ||
| 651 | end | ||
| 652 | end | ||
| 653 | end | ||
| 654 | return v | ||
| 655 | end | ||
| 656 | |||
| 657 | |||
| 658 | ## generic sorting methods ## | ||
| 659 | |||
| 660 | defalg(v::AbstractArray) = DEFAULT_STABLE | ||
| 661 | defalg(v::AbstractArray{<:Union{Number, Missing}}) = DEFAULT_UNSTABLE | ||
| 662 | |||
| 663 | function sort!(v::AbstractVector, alg::Algorithm, order::Ordering) | ||
| 664 | inds = axes(v,1) | ||
| 665 | 602 (72 %) |
602 (100 %)
samples spent calling
sort!
sort!(v,first(inds),last(inds),alg,order)
|
|
| 666 | end | ||
| 667 | |||
| 668 | """ | ||
| 669 | sort!(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward) | ||
| 670 | |||
| 671 | Sort the vector `v` in place. [`QuickSort`](@ref) is used by default for numeric arrays while | ||
| 672 | [`MergeSort`](@ref) is used for other arrays. You can specify an algorithm to use via the `alg` | ||
| 673 | keyword (see [Sorting Algorithms](@ref) for available algorithms). The `by` keyword lets you provide | ||
| 674 | a function that will be applied to each element before comparison; the `lt` keyword allows | ||
| 675 | providing a custom "less than" function; use `rev=true` to reverse the sorting order. These | ||
| 676 | options are independent and can be used together in all possible combinations: if both `by` | ||
| 677 | and `lt` are specified, the `lt` function is applied to the result of the `by` function; | ||
| 678 | `rev=true` reverses whatever ordering specified via the `by` and `lt` keywords. | ||
| 679 | |||
| 680 | # Examples | ||
| 681 | ```jldoctest | ||
| 682 | julia> v = [3, 1, 2]; sort!(v); v | ||
| 683 | 3-element Array{Int64,1}: | ||
| 684 | 1 | ||
| 685 | 2 | ||
| 686 | 3 | ||
| 687 | |||
| 688 | julia> v = [3, 1, 2]; sort!(v, rev = true); v | ||
| 689 | 3-element Array{Int64,1}: | ||
| 690 | 3 | ||
| 691 | 2 | ||
| 692 | 1 | ||
| 693 | |||
| 694 | julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v | ||
| 695 | 3-element Array{Tuple{Int64,String},1}: | ||
| 696 | (1, "c") | ||
| 697 | (2, "b") | ||
| 698 | (3, "a") | ||
| 699 | |||
| 700 | julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v | ||
| 701 | 3-element Array{Tuple{Int64,String},1}: | ||
| 702 | (3, "a") | ||
| 703 | (2, "b") | ||
| 704 | (1, "c") | ||
| 705 | ``` | ||
| 706 | """ | ||
| 707 | function sort!(v::AbstractVector; | ||
| 708 | alg::Algorithm=defalg(v), | ||
| 709 | lt=isless, | ||
| 710 | by=identity, | ||
| 711 | rev::Union{Bool,Nothing}=nothing, | ||
| 712 | order::Ordering=Forward) | ||
| 713 | 602 (72 %) |
602 (100 %)
samples spent calling
#sort!#7
ordr = ord(lt,by,rev,order)
|
|
| 714 | if (ordr === Forward || ordr === Reverse) && eltype(v)<:Integer | ||
| 715 | n = length(v) | ||
| 716 | if n > 1 | ||
| 717 | min, max = extrema(v) | ||
| 718 | (diff, o1) = sub_with_overflow(max, min) | ||
| 719 | (rangelen, o2) = add_with_overflow(diff, oneunit(diff)) | ||
| 720 | if !o1 && !o2 && rangelen < div(n,2) | ||
| 721 | return sort_int_range!(v, rangelen, min, ordr === Reverse ? reverse : identity) | ||
| 722 | end | ||
| 723 | end | ||
| 724 | end | ||
| 725 | 602 (72 %) |
602 (100 %)
samples spent calling
sort!
sort!(v, alg, ordr)
|
|
| 726 | end | ||
| 727 | |||
| 728 | # sort! for vectors of few unique integers | ||
| 729 | function sort_int_range!(x::AbstractVector{<:Integer}, rangelen, minval, maybereverse) | ||
| 730 | offs = 1 - minval | ||
| 731 | |||
| 732 | where = fill(0, rangelen) | ||
| 733 | @inbounds for i = eachindex(x) | ||
| 734 | where[x[i] + offs] += 1 | ||
| 735 | end | ||
| 736 | |||
| 737 | idx = firstindex(x) | ||
| 738 | @inbounds for i = maybereverse(1:rangelen) | ||
| 739 | lastidx = idx + where[i] - 1 | ||
| 740 | val = i-offs | ||
| 741 | for j = idx:lastidx | ||
| 742 | x[j] = val | ||
| 743 | end | ||
| 744 | idx = lastidx + 1 | ||
| 745 | end | ||
| 746 | |||
| 747 | return x | ||
| 748 | end | ||
| 749 | |||
| 750 | """ | ||
| 751 | sort(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward) | ||
| 752 | |||
| 753 | Variant of [`sort!`](@ref) that returns a sorted copy of `v` leaving `v` itself unmodified. | ||
| 754 | |||
| 755 | # Examples | ||
| 756 | ```jldoctest | ||
| 757 | julia> v = [3, 1, 2]; | ||
| 758 | |||
| 759 | julia> sort(v) | ||
| 760 | 3-element Array{Int64,1}: | ||
| 761 | 1 | ||
| 762 | 2 | ||
| 763 | 3 | ||
| 764 | |||
| 765 | julia> v | ||
| 766 | 3-element Array{Int64,1}: | ||
| 767 | 3 | ||
| 768 | 1 | ||
| 769 | 2 | ||
| 770 | ``` | ||
| 771 | """ | ||
| 772 | sort(v::AbstractVector; kws...) = sort!(copymutable(v); kws...) | ||
| 773 | |||
| 774 | ## partialsortperm: the permutation to sort the first k elements of an array ## | ||
| 775 | |||
| 776 | """ | ||
| 777 | partialsortperm(v, k; by=<transform>, lt=<comparison>, rev=false) | ||
| 778 | |||
| 779 | Return a partial permutation `I` of the vector `v`, so that `v[I]` returns values of a fully | ||
| 780 | sorted version of `v` at index `k`. If `k` is a range, a vector of indices is returned; if | ||
| 781 | `k` is an integer, a single index is returned. The order is specified using the same | ||
| 782 | keywords as `sort!`. The permutation is stable, meaning that indices of equal elements | ||
| 783 | appear in ascending order. | ||
| 784 | |||
| 785 | Note that this function is equivalent to, but more efficient than, calling `sortperm(...)[k]`. | ||
| 786 | |||
| 787 | # Examples | ||
| 788 | ```jldoctest | ||
| 789 | julia> v = [3, 1, 2, 1]; | ||
| 790 | |||
| 791 | julia> v[partialsortperm(v, 1)] | ||
| 792 | 1 | ||
| 793 | |||
| 794 | julia> p = partialsortperm(v, 1:3) | ||
| 795 | 3-element view(::Array{Int64,1}, 1:3) with eltype Int64: | ||
| 796 | 2 | ||
| 797 | 4 | ||
| 798 | 3 | ||
| 799 | |||
| 800 | julia> v[p] | ||
| 801 | 3-element Array{Int64,1}: | ||
| 802 | 1 | ||
| 803 | 1 | ||
| 804 | 2 | ||
| 805 | ``` | ||
| 806 | """ | ||
| 807 | partialsortperm(v::AbstractVector, k::Union{Integer,OrdinalRange}; kwargs...) = | ||
| 808 | partialsortperm!(similar(Vector{eltype(k)}, axes(v,1)), v, k; kwargs..., initialized=false) | ||
| 809 | |||
| 810 | """ | ||
| 811 | partialsortperm!(ix, v, k; by=<transform>, lt=<comparison>, rev=false, initialized=false) | ||
| 812 | |||
| 813 | Like [`partialsortperm`](@ref), but accepts a preallocated index vector `ix` the same size as | ||
| 814 | `v`, which is used to store (a permutation of) the indices of `v`. | ||
| 815 | |||
| 816 | If the index vector `ix` is initialized with the indices of `v` (or a permutation thereof), `initialized` should be set to | ||
| 817 | `true`. | ||
| 818 | |||
| 819 | If `initialized` is `false` (the default), then `ix` is initialized to contain the indices of `v`. | ||
| 820 | |||
| 821 | If `initialized` is `true`, but `ix` does not contain (a permutation of) the indices of `v`, the behavior of | ||
| 822 | `partialsortperm!` is undefined. | ||
| 823 | |||
| 824 | (Typically, the indices of `v` will be `1:length(v)`, although if `v` has an alternative array type | ||
| 825 | with non-one-based indices, such as an `OffsetArray`, `ix` must also be an `OffsetArray` with the same | ||
| 826 | indices, and must contain as values (a permutation of) these same indices.) | ||
| 827 | |||
| 828 | Upon return, `ix` is guaranteed to have the indices `k` in their sorted positions, such that | ||
| 829 | |||
| 830 | ```julia | ||
| 831 | partialsortperm!(ix, v, k); | ||
| 832 | v[ix[k]] == partialsort(v, k) | ||
| 833 | ``` | ||
| 834 | |||
| 835 | The return value is the `k`th element of `ix` if `k` is an integer, or view into `ix` if `k` is | ||
| 836 | a range. | ||
| 837 | |||
| 838 | # Examples | ||
| 839 | ```jldoctest | ||
| 840 | julia> v = [3, 1, 2, 1]; | ||
| 841 | |||
| 842 | julia> ix = Vector{Int}(undef, 4); | ||
| 843 | |||
| 844 | julia> partialsortperm!(ix, v, 1) | ||
| 845 | 2 | ||
| 846 | |||
| 847 | julia> ix = [1:4;]; | ||
| 848 | |||
| 849 | julia> partialsortperm!(ix, v, 2:3, initialized=true) | ||
| 850 | 2-element view(::Array{Int64,1}, 2:3) with eltype Int64: | ||
| 851 | 4 | ||
| 852 | 3 | ||
| 853 | ``` | ||
| 854 | """ | ||
| 855 | function partialsortperm!(ix::AbstractVector{<:Integer}, v::AbstractVector, | ||
| 856 | k::Union{Integer, OrdinalRange}; | ||
| 857 | lt::Function=isless, | ||
| 858 | by::Function=identity, | ||
| 859 | rev::Union{Bool,Nothing}=nothing, | ||
| 860 | order::Ordering=Forward, | ||
| 861 | initialized::Bool=false) | ||
| 862 | if axes(ix,1) != axes(v,1) | ||
| 863 | throw(ArgumentError("The index vector is used as a workspace and must have the " * | ||
| 864 | "same length/indices as the source vector, $(axes(ix,1)) != $(axes(v,1))")) | ||
| 865 | end | ||
| 866 | if !initialized | ||
| 867 | @inbounds for i = axes(ix,1) | ||
| 868 | ix[i] = i | ||
| 869 | end | ||
| 870 | end | ||
| 871 | |||
| 872 | # do partial quicksort | ||
| 873 | sort!(ix, PartialQuickSort(k), Perm(ord(lt, by, rev, order), v)) | ||
| 874 | |||
| 875 | maybeview(ix, k) | ||
| 876 | end | ||
| 877 | |||
| 878 | ## sortperm: the permutation to sort an array ## | ||
| 879 | |||
| 880 | """ | ||
| 881 | sortperm(v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward) | ||
| 882 | |||
| 883 | Return a permutation vector `I` that puts `v[I]` in sorted order. The order is specified | ||
| 884 | using the same keywords as [`sort!`](@ref). The permutation is guaranteed to be stable even | ||
| 885 | if the sorting algorithm is unstable, meaning that indices of equal elements appear in | ||
| 886 | ascending order. | ||
| 887 | |||
| 888 | See also [`sortperm!`](@ref). | ||
| 889 | |||
| 890 | # Examples | ||
| 891 | ```jldoctest | ||
| 892 | julia> v = [3, 1, 2]; | ||
| 893 | |||
| 894 | julia> p = sortperm(v) | ||
| 895 | 3-element Array{Int64,1}: | ||
| 896 | 2 | ||
| 897 | 3 | ||
| 898 | 1 | ||
| 899 | |||
| 900 | julia> v[p] | ||
| 901 | 3-element Array{Int64,1}: | ||
| 902 | 1 | ||
| 903 | 2 | ||
| 904 | 3 | ||
| 905 | ``` | ||
| 906 | """ | ||
| 907 | function sortperm(v::AbstractVector; | ||
| 908 | alg::Algorithm=DEFAULT_UNSTABLE, | ||
| 909 | lt=isless, | ||
| 910 | by=identity, | ||
| 911 | rev::Union{Bool,Nothing}=nothing, | ||
| 912 | order::Ordering=Forward) | ||
| 913 | ordr = ord(lt,by,rev,order) | ||
| 914 | if ordr === Forward && isa(v,Vector) && eltype(v)<:Integer | ||
| 915 | n = length(v) | ||
| 916 | if n > 1 | ||
| 917 | min, max = extrema(v) | ||
| 918 | (diff, o1) = sub_with_overflow(max, min) | ||
| 919 | (rangelen, o2) = add_with_overflow(diff, oneunit(diff)) | ||
| 920 | if !o1 && !o2 && rangelen < div(n,2) | ||
| 921 | return sortperm_int_range(v, rangelen, min) | ||
| 922 | end | ||
| 923 | end | ||
| 924 | end | ||
| 925 | ax = axes(v, 1) | ||
| 926 | p = similar(Vector{eltype(ax)}, ax) | ||
| 927 | for (i,ind) in zip(eachindex(p), ax) | ||
| 928 | p[i] = ind | ||
| 929 | end | ||
| 930 | sort!(p, alg, Perm(ordr,v)) | ||
| 931 | end | ||
| 932 | |||
| 933 | |||
| 934 | """ | ||
| 935 | sortperm!(ix, v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, initialized::Bool=false) | ||
| 936 | |||
| 937 | Like [`sortperm`](@ref), but accepts a preallocated index vector `ix`. If `initialized` is `false` | ||
| 938 | (the default), `ix` is initialized to contain the values `1:length(v)`. | ||
| 939 | |||
| 940 | # Examples | ||
| 941 | ```jldoctest | ||
| 942 | julia> v = [3, 1, 2]; p = zeros(Int, 3); | ||
| 943 | |||
| 944 | julia> sortperm!(p, v); p | ||
| 945 | 3-element Array{Int64,1}: | ||
| 946 | 2 | ||
| 947 | 3 | ||
| 948 | 1 | ||
| 949 | |||
| 950 | julia> v[p] | ||
| 951 | 3-element Array{Int64,1}: | ||
| 952 | 1 | ||
| 953 | 2 | ||
| 954 | 3 | ||
| 955 | ``` | ||
| 956 | """ | ||
| 957 | function sortperm!(x::AbstractVector{<:Integer}, v::AbstractVector; | ||
| 958 | alg::Algorithm=DEFAULT_UNSTABLE, | ||
| 959 | lt=isless, | ||
| 960 | by=identity, | ||
| 961 | rev::Union{Bool,Nothing}=nothing, | ||
| 962 | order::Ordering=Forward, | ||
| 963 | initialized::Bool=false) | ||
| 964 | if axes(x,1) != axes(v,1) | ||
| 965 | throw(ArgumentError("index vector must have the same length/indices as the source vector, $(axes(x,1)) != $(axes(v,1))")) | ||
| 966 | end | ||
| 967 | if !initialized | ||
| 968 | @inbounds for i = axes(v,1) | ||
| 969 | x[i] = i | ||
| 970 | end | ||
| 971 | end | ||
| 972 | sort!(x, alg, Perm(ord(lt,by,rev,order),v)) | ||
| 973 | end | ||
| 974 | |||
| 975 | # sortperm for vectors of few unique integers | ||
| 976 | function sortperm_int_range(x::Vector{<:Integer}, rangelen, minval) | ||
| 977 | offs = 1 - minval | ||
| 978 | n = length(x) | ||
| 979 | |||
| 980 | where = fill(0, rangelen+1) | ||
| 981 | where[1] = 1 | ||
| 982 | @inbounds for i = 1:n | ||
| 983 | where[x[i] + offs + 1] += 1 | ||
| 984 | end | ||
| 985 | |||
| 986 | #cumsum!(where, where) | ||
| 987 | @inbounds for i = 2:length(where) | ||
| 988 | where[i] += where[i-1] | ||
| 989 | end | ||
| 990 | |||
| 991 | P = Vector{Int}(undef, n) | ||
| 992 | @inbounds for i = 1:n | ||
| 993 | label = x[i] + offs | ||
| 994 | P[where[label]] = i | ||
| 995 | where[label] += 1 | ||
| 996 | end | ||
| 997 | |||
| 998 | return P | ||
| 999 | end | ||
| 1000 | |||
| 1001 | ## sorting multi-dimensional arrays ## | ||
| 1002 | |||
| 1003 | """ | ||
| 1004 | sort(A; dims::Integer, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward) | ||
| 1005 | |||
| 1006 | Sort a multidimensional array `A` along the given dimension. | ||
| 1007 | See [`sort!`](@ref) for a description of possible | ||
| 1008 | keyword arguments. | ||
| 1009 | |||
| 1010 | To sort slices of an array, refer to [`sortslices`](@ref). | ||
| 1011 | |||
| 1012 | # Examples | ||
| 1013 | ```jldoctest | ||
| 1014 | julia> A = [4 3; 1 2] | ||
| 1015 | 2×2 Array{Int64,2}: | ||
| 1016 | 4 3 | ||
| 1017 | 1 2 | ||
| 1018 | |||
| 1019 | julia> sort(A, dims = 1) | ||
| 1020 | 2×2 Array{Int64,2}: | ||
| 1021 | 1 2 | ||
| 1022 | 4 3 | ||
| 1023 | |||
| 1024 | julia> sort(A, dims = 2) | ||
| 1025 | 2×2 Array{Int64,2}: | ||
| 1026 | 3 4 | ||
| 1027 | 1 2 | ||
| 1028 | ``` | ||
| 1029 | """ | ||
| 1030 | function sort(A::AbstractArray; | ||
| 1031 | dims::Integer, | ||
| 1032 | alg::Algorithm=DEFAULT_UNSTABLE, | ||
| 1033 | lt=isless, | ||
| 1034 | by=identity, | ||
| 1035 | rev::Union{Bool,Nothing}=nothing, | ||
| 1036 | order::Ordering=Forward) | ||
| 1037 | dim = dims | ||
| 1038 | order = ord(lt,by,rev,order) | ||
| 1039 | n = length(axes(A, dim)) | ||
| 1040 | if dim != 1 | ||
| 1041 | pdims = (dim, setdiff(1:ndims(A), dim)...) # put the selected dimension first | ||
| 1042 | Ap = permutedims(A, pdims) | ||
| 1043 | Av = vec(Ap) | ||
| 1044 | sort_chunks!(Av, n, alg, order) | ||
| 1045 | permutedims(Ap, invperm(pdims)) | ||
| 1046 | else | ||
| 1047 | Av = A[:] | ||
| 1048 | sort_chunks!(Av, n, alg, order) | ||
| 1049 | reshape(Av, axes(A)) | ||
| 1050 | end | ||
| 1051 | end | ||
| 1052 | |||
| 1053 | @noinline function sort_chunks!(Av, n, alg, order) | ||
| 1054 | inds = LinearIndices(Av) | ||
| 1055 | for s = first(inds):n:last(inds) | ||
| 1056 | sort!(Av, s, s+n-1, alg, order) | ||
| 1057 | end | ||
| 1058 | Av | ||
| 1059 | end | ||
| 1060 | |||
| 1061 | """ | ||
| 1062 | sort!(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward) | ||
| 1063 | |||
| 1064 | Sort the multidimensional array `A` along dimension `dims`. | ||
| 1065 | See [`sort!`](@ref) for a description of possible keyword arguments. | ||
| 1066 | |||
| 1067 | To sort slices of an array, refer to [`sortslices`](@ref). | ||
| 1068 | |||
| 1069 | !!! compat "Julia 1.1" | ||
| 1070 | This function requires at least Julia 1.1. | ||
| 1071 | |||
| 1072 | # Examples | ||
| 1073 | ```jldoctest | ||
| 1074 | julia> A = [4 3; 1 2] | ||
| 1075 | 2×2 Array{Int64,2}: | ||
| 1076 | 4 3 | ||
| 1077 | 1 2 | ||
| 1078 | |||
| 1079 | julia> sort!(A, dims = 1); A | ||
| 1080 | 2×2 Array{Int64,2}: | ||
| 1081 | 1 2 | ||
| 1082 | 4 3 | ||
| 1083 | |||
| 1084 | julia> sort!(A, dims = 2); A | ||
| 1085 | 2×2 Array{Int64,2}: | ||
| 1086 | 1 2 | ||
| 1087 | 3 4 | ||
| 1088 | ``` | ||
| 1089 | """ | ||
| 1090 | function sort!(A::AbstractArray; | ||
| 1091 | dims::Integer, | ||
| 1092 | alg::Algorithm=defalg(A), | ||
| 1093 | lt=isless, | ||
| 1094 | by=identity, | ||
| 1095 | rev::Union{Bool,Nothing}=nothing, | ||
| 1096 | order::Ordering=Forward) | ||
| 1097 | ordr = ord(lt, by, rev, order) | ||
| 1098 | nd = ndims(A) | ||
| 1099 | k = dims | ||
| 1100 | |||
| 1101 | 1 <= k <= nd || throw(ArgumentError("dimension out of range")) | ||
| 1102 | |||
| 1103 | remdims = ntuple(i -> i == k ? 1 : size(A, i), nd) | ||
| 1104 | for idx in CartesianIndices(remdims) | ||
| 1105 | Av = view(A, ntuple(i -> i == k ? Colon() : idx[i], nd)...) | ||
| 1106 | sort!(Av, alg, ordr) | ||
| 1107 | end | ||
| 1108 | A | ||
| 1109 | end | ||
| 1110 | |||
| 1111 | ## fast clever sorting for floats ## | ||
| 1112 | |||
| 1113 | module Float | ||
| 1114 | using ..Sort | ||
| 1115 | using ...Order | ||
| 1116 | using ..Base: @inbounds, AbstractVector, Vector, last, axes | ||
| 1117 | |||
| 1118 | import Core.Intrinsics: slt_int | ||
| 1119 | import ..Sort: sort! | ||
| 1120 | import ...Order: lt, DirectOrdering | ||
| 1121 | |||
| 1122 | const Floats = Union{Float32,Float64} | ||
| 1123 | |||
| 1124 | struct Left <: Ordering end | ||
| 1125 | struct Right <: Ordering end | ||
| 1126 | |||
| 1127 | left(::DirectOrdering) = Left() | ||
| 1128 | right(::DirectOrdering) = Right() | ||
| 1129 | |||
| 1130 | left(o::Perm) = Perm(left(o.order), o.data) | ||
| 1131 | right(o::Perm) = Perm(right(o.order), o.data) | ||
| 1132 | |||
| 1133 | lt(::Left, x::T, y::T) where {T<:Floats} = slt_int(y, x) | ||
| 1134 | lt(::Right, x::T, y::T) where {T<:Floats} = slt_int(x, y) | ||
| 1135 | |||
| 1136 | isnan(o::DirectOrdering, x::Floats) = (x!=x) | ||
| 1137 | isnan(o::Perm, i::Integer) = isnan(o.order,o.data[i]) | ||
| 1138 | |||
| 1139 | function nans2left!(v::AbstractVector, o::Ordering, lo::Integer=first(axes(v,1)), hi::Integer=last(axes(v,1))) | ||
| 1140 | i = lo | ||
| 1141 | @inbounds while i <= hi && isnan(o,v[i]) | ||
| 1142 | i += 1 | ||
| 1143 | end | ||
| 1144 | j = i + 1 | ||
| 1145 | @inbounds while j <= hi | ||
| 1146 | if isnan(o,v[j]) | ||
| 1147 | v[i], v[j] = v[j], v[i] | ||
| 1148 | i += 1 | ||
| 1149 | end | ||
| 1150 | j += 1 | ||
| 1151 | end | ||
| 1152 | return i, hi | ||
| 1153 | end | ||
| 1154 | function nans2right!(v::AbstractVector, o::Ordering, lo::Integer=first(axes(v,1)), hi::Integer=last(axes(v,1))) | ||
| 1155 | i = hi | ||
| 1156 | @inbounds while lo <= i && isnan(o,v[i]) | ||
| 1157 | i -= 1 | ||
| 1158 | end | ||
| 1159 | j = i - 1 | ||
| 1160 | @inbounds while lo <= j | ||
| 1161 | if isnan(o,v[j]) | ||
| 1162 | v[i], v[j] = v[j], v[i] | ||
| 1163 | i -= 1 | ||
| 1164 | end | ||
| 1165 | j -= 1 | ||
| 1166 | end | ||
| 1167 | return lo, i | ||
| 1168 | end | ||
| 1169 | |||
| 1170 | nans2end!(v::AbstractVector, o::ForwardOrdering) = nans2right!(v,o) | ||
| 1171 | nans2end!(v::AbstractVector, o::ReverseOrdering) = nans2left!(v,o) | ||
| 1172 | nans2end!(v::AbstractVector{<:Integer}, o::Perm{<:ForwardOrdering}) = nans2right!(v,o) | ||
| 1173 | nans2end!(v::AbstractVector{<:Integer}, o::Perm{<:ReverseOrdering}) = nans2left!(v,o) | ||
| 1174 | |||
| 1175 | issignleft(o::ForwardOrdering, x::Floats) = lt(o, x, zero(x)) | ||
| 1176 | issignleft(o::ReverseOrdering, x::Floats) = lt(o, x, -zero(x)) | ||
| 1177 | issignleft(o::Perm, i::Integer) = issignleft(o.order, o.data[i]) | ||
| 1178 | |||
| 1179 | function fpsort!(v::AbstractVector, a::Algorithm, o::Ordering) | ||
| 1180 | i, j = lo, hi = nans2end!(v,o) | ||
| 1181 | @inbounds while true | ||
| 1182 | while i <= j && issignleft(o,v[i]); i += 1; end | ||
| 1183 | while i <= j && !issignleft(o,v[j]); j -= 1; end | ||
| 1184 | i <= j || break | ||
| 1185 | v[i], v[j] = v[j], v[i] | ||
| 1186 | i += 1; j -= 1 | ||
| 1187 | end | ||
| 1188 | sort!(v, lo, j, a, left(o)) | ||
| 1189 | sort!(v, i, hi, a, right(o)) | ||
| 1190 | return v | ||
| 1191 | end | ||
| 1192 | |||
| 1193 | |||
| 1194 | fpsort!(v::AbstractVector, a::Sort.PartialQuickSort, o::Ordering) = | ||
| 1195 | sort!(v, first(axes(v,1)), last(axes(v,1)), a, o) | ||
| 1196 | |||
| 1197 | sort!(v::AbstractVector{<:Floats}, a::Algorithm, o::DirectOrdering) = fpsort!(v,a,o) | ||
| 1198 | sort!(v::Vector{Int}, a::Algorithm, o::Perm{<:DirectOrdering,<:Vector{<:Floats}}) = fpsort!(v,a,o) | ||
| 1199 | |||
| 1200 | end # module Sort.Float | ||
| 1201 | |||
| 1202 | end # module Sort |