Mercurial > lbo > hg > juliaplay
view julia/quicksort.jl @ 6:661876a2502e
py: dp
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 12:50:44 +0100 |
parents | c1db337c15be |
children |
line wrap: on
line source
function partition(v::Vector{T}, from::Int, to::Int)::Int where {T} piv = v[to] i = from-1 for j = from:to-1 if v[j] <= piv i += 1 v[i], v[j] = v[j], v[i] end end i += 1 v[i], v[to] = v[to], v[i] i end function hoare!(v::AbstractArray, from::Int, to::Int)::Int if from >= to return from end lo, hi = from-1, to+1 piv = v[div(from+to,2)] while true lo += 1 while v[lo] < piv lo += 1 end hi -= 1 while v[hi] > piv hi -= 1 end if lo >= hi return hi end v[lo], v[hi] = v[hi], v[lo] end end function quicksort!(v::Vector{T}, from=1, to=-1) where {T} if to < 0 to = length(v) end if to <= from return else mid = hoare!(v, from, to) quicksort!(v, from, mid) quicksort!(v, mid+1, to) end end