Moon aka Sun (moon_aka_sun) wrote,
Moon aka Sun
moon_aka_sun

Quicksort: хаскелянты пугают ежа голой задницей

quicksort []     = []
quicksort (p:xs) = quicksort small ++ mid ++ quicksort large
  where
    small = [y | y<-xs, y<p]
    mid   = [y | y<-xs, y==p] ++ [p]
    large = [y | y<-xs, y>p]

-- two partitions
qsort []     = []
qsort (p:xs) = quicksort lesser ++ [p] ++ quicksort greater
  where
    lesser  = filter (< p) xs
    greater = filter (>= p) xs

-- with list comprehension
qs []     = []
qs (p:xs) = qs [x | x<-xs, x<p] ++ [p] ++ qs [x | x<-xs, x>=p]

# Python
def qsort(xs):
  if xs==[]: return []
  p,xs = xs[0],xs[1:]
  s = [x for x in xs if x<p]
  m = [x for x in xs if x==p] + [p]
  l = [x for x in xs if x>p]
  return qsort(s) + m + qsort(l)

# with list comprehension
def qs(xs):
  if xs==[]: return []
  p,xs = xs[0],xs[1:]
  return qs([x for x in xs if x<p]) + [p] + qs([x for x in xs if x>=p])

NB. J
qs=: 3 : 0
if. (#y)<:1 do. y
else.
  h =. {.y NB. head
  t =. }.y NB. tail
  l =. (t<h)#t
  m =. (t=h)#t
  g =. (t>h)#t
  (qs l),m,h,qs g
end.
)

NB. one-liner
qs=: 3 : 'if. 1>:#y do. y else. (qs(t<h)#t),((t=h)#t),h,qs(t>h=.{.y)#t=.}.y end.'

NB. leave h in array
qs=: 3 : 'if. 1>:#y do. y else. (qs(y<h)#y),((y=h)#y),qs(y>h=.{.y)#y end.'

NB. with separate helper function
qF=: 4 : '(qs(x<y)#x),((x=y)#x),qs(x>y)#x'
qF=: ([: qs <#[),(=#[),[: qs >#[   NB. tacit of above (result of 13 : '...')
qF=: (qs@(<#])),(=#]),qs@(>#])     NB. same
qs=: 3 : 'if. 1>:#y do. y else. y qF {.y end.'
qs=: ] ` (]qF{.) @. (1<#)  NB. tacit of above

NB. with adverb
qA=: 1 : '] #~ ] x {.'
qs=: ] ` ($:@(<qA),=qA,$:@(>qA)) @. (1<#)

NB. final tacit
qs=: ]`({.(([:$:>#]),(=#]),[:$:<#])])@.(1<#)

NB. test it
  sorted =: [: *./ 2 <:/\ ]
  sorted a=:?20#10
0
  sorted qs a
1

Tags: haskell, j, python
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments