extra/sorting/quick/quick.factor

   1 ! Copyright (C) 2014 John Benediktsson
   2 ! See http://factorcode.org/license.txt for BSD license
   3
   4 USING: combinators kernel locals math math.order sequences
   5 sequences.private ;
   6
   7 IN: sorting.quick
   8
   9 <PRIVATE
  10
  11 :: (quicksort) ( seq from to -- )
  12     from to < [
  13         from to + 2/ seq nth-unsafe :> pivot
  14
  15         from to [ 2dup <= ] [
  16             [ over seq nth-unsafe pivot before? ] [ [ 1 + ] dip ] while
  17             [ dup  seq nth-unsafe pivot after? ] [ 1 - ] while
  18             2dup <= [
  19                 [ seq exchange-unsafe ]
  20                 [ [ 1 + ] [ 1 - ] bi* ] 2bi
  21             ] when
  22         ] while
  23
  24         [ seq from ] dip (quicksort)
  25         [ seq ] dip to (quicksort)
  26
  27     ] when ; inline recursive
  28
  29 PRIVATE>
  30
  31 : quicksort ( seq -- )
  32     0 over length 1 - (quicksort) ;