?

Log in

tachikoma valentines

Another bad sort

Oops, I fell inactive on LJ again.  At least I’m still pretty active on Stack Overflow regardless of what you see here.

Recently a whimsical question there asked for insertion sort in various languages.  Pretty easy stuff, but I chose to answer with J again because my other favorite languages (Haskell, Perl, C) were already implemented.

(([<.{.@]),}.@]$:~[>.{.@])`[@.(0=#@])/  (Yes, it’s actually longer than the quicksort I mentioned a little while ago.)

Breakdown:
NB. given two arguments, return the left argument
insert0 =: 4 : 'x'
insert0 =: [
NB. given two arguments, return the lesser of left and head of right
insert1min =: 4 : 'x <. {. y'
insert1min =: [ <. {.@]
NB. given two arguments, return the greater of left and head of right
insert1max =: [ >. {.@]
NB. recurse with insert1max and tail of right, and prepend insert1min
insert1 =: 4 : 'x insert1min y , (x insert1max y) insert }. y'
insert1 =: insert1min , insert1max insert }.@]
insert1 =: insert1min , }.@] insert~ insert1max
NB. if right has zero length, insert0, else insert1
NB. the recursive reference to insert in insert1 can be replaced by $:
insert =: insert1 ` insert0 @. (0 = #@])
NB. apply insert between all elements of argument
sort =: insert/

Comments