Mercurial > lbo > hg > juliaplay
view julia/quicksort.jl @ 40:5e3662b65004 default tip
Land/water find peak problem
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Mon, 03 Apr 2023 22:04:42 +0200 |
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