1 ! Copyright (C) 2014 John Benediktsson
2 ! See http://factorcode.org/license.txt for BSD license
4 USING: arrays combinators kernel locals math math.order
5 sequences sequences.private strings vectors ;
11 :: quicksort ( seq from to quot: ( obj1 obj2 -- <=> ) -- )
13 from to + 2/ seq nth-unsafe :> pivot
17 over seq nth-unsafe pivot quot call
19 ] [ [ 1 + ] dip ] while
22 dup seq nth-unsafe pivot quot call
27 [ seq exchange-unsafe ]
28 [ [ 1 + ] [ 1 - ] bi* ] 2bi
32 [ seq from ] dip quot quicksort
33 [ seq ] dip to quot quicksort
34 ] when ; inline recursive
38 : sort! ( seq quot: ( obj1 obj2 -- <=> ) -- )
39 [ 0 over length 1 - ] dip quicksort ; inline
41 : sort-with! ( seq quot: ( elt -- key ) -- )
42 [ compare ] curry sort! ; inline
44 : inv-sort-with! ( seq quot: ( elt -- key ) -- )
45 [ compare invert-comparison ] curry sort! ; inline
47 GENERIC: natural-sort! ( seq -- )
49 M: object natural-sort! [ <=> ] sort! ;
50 M: array natural-sort! [ <=> ] sort! ;
51 M: vector natural-sort! [ <=> ] sort! ;
52 M: string natural-sort! [ <=> ] sort! ;