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 |