Quicksort in XQuery

haskell-reference.hs

--reference implementation in Haskell
qsort' :: (Ord a) => [a] -> [a] 
qsort' [] = []
qsort' (x:xs) = qsort' smaller ++ [x] ++ qsort' larger
  where larger = [a | a <- xs, a > x]
        smaller = [b | b <- xs, b <= x]
        
    

quick-sort-i.xqy

xquery version "3.0";

declare function local:qsort($nums as xs:integer*) as xs:integer*
{
    let $pivot := $nums[1]
    let $smaller := local:qsort($nums[position()=(2 to last())][. < $pivot])
    let $larger := local:qsort($nums[position()=(2 to last())][. >= $pivot])
    where fn:not(fn:empty($pivot))
    return ($smaller, $pivot, $larger)
};

local:qsort((9,1,3,7,2,6,2,4,6,5))

quick-sort-ii.xqy

xquery version "3.1";

(: No FLWOR needed :)

declare function local:qsort($nums as xs:integer*) as xs:integer*
{
    if (fn:not(fn:empty($nums))) then
    (
      local:qsort(fn:tail($nums)[. < fn:head($nums)]), 
      fn:head($nums), 
      local:qsort(fn:tail($nums)[. >= fn:head($nums)])
    )
     else ()
};

local:qsort((9,1,3,7,2,6,2,4,6,5))

quick-sort-iii.xqy

xquery version "3.1";

(: Using fn:head() and fn:tail() from XQuery 3.1 :)

declare function local:qsort($nums as xs:integer*) as xs:integer*
{
    let $pivot := fn:head($nums)
    let $smaller := local:qsort(fn:tail($nums)[. < $pivot])
    let $larger := local:qsort(fn:tail($nums)[. >= $pivot])
    where fn:not(fn:empty($pivot))
    return ($smaller, $pivot, $larger)
};

local:qsort((9,1,3,7,2,6,2,4,6,5))

quick-sort-rnd.xqy

xquery version "3.1";

declare function local:qsort($nums as xs:integer*) as xs:integer*
{
    let $pivot := $nums[1]
    let $smaller := local:qsort($nums[position()=(2 to last())][. < $pivot])
    let $larger := local:qsort($nums[position()=(2 to last())][. >= $pivot])
    where fn:not(fn:empty($pivot))
    return ($smaller, $pivot, $larger)
};

let $rng := fn:random-number-generator('permute')
let $nums := $rng('permute')(1 to 100)
return local:qsort($nums)