Paste: Insertion sort

Author: yuuki
Mode: factor
Date: Sun, 21 Jun 2009 03:32:40
Plain Text | 
DEFER: insert
: (insert) ( key n seq -- )
    [ [ 1- ] dip nth ] 2keep
    [ set-nth ] 2keep
    [ 1- ] dip insert ; inline recursive

: insert ( key n seq -- )
    over zero? not [
        pick pick 1- pick nth <=> +lt+ = [ (insert) ] [ set-nth ] if
    ] [ set-nth ] if ; inline recursive

: insertion-sort ( seq -- )
    [ length ] keep [ [ nth ] 2keep insert ] curry each ; inline

Annotation: sorting.insertion

Author: yuuki
Mode: factor
Date: Sun, 21 Jun 2009 03:33:54
Plain Text | 
<PRIVATE
:: insert ( seq quot: ( elt -- elt' ) n -- )
    n zero? [
        n n 1- [ seq nth quot call ] bi@ >= [
            n n 1- seq exchange
            seq quot n 1- insert
        ] unless
    ] unless ; inline recursive
PRIVATE>

: insertion-sort ( seq quot -- )
    ! quot is a transformation on elements
    over length [ insert ] with with each ; inline

New Annotation

Summary:
Author:
Mode:
Body: