core/sorting/sorting-docs.factor

   1 USING: help.markup help.syntax kernel words math
   2 sequences math.order ;
   3 IN: sorting
   4
   5 ARTICLE: "sequences-sorting" "Sorting sequences"
   6 "The " { $vocab-link "sorting" } " vocabulary implements the merge-sort algorithm. It runs in " { $snippet "O(n log n)" } " time, and is a " { $emphasis "stable" } " sort, meaning that the order of equal elements is preserved."
   7 $nl
   8 "The algorithm only allocates two additional arrays, both the size of the input sequence, and uses iteration rather than recursion, and thus is suitable for sorting large sequences."
   9 $nl
  10 "Sorting combinators all take comparator quotations with stack effect " { $snippet "( elt1 elt2 -- <=> )" } ", where the output value is one of the three " { $link "order-specifiers" } "."
  11 $nl
  12 "Sorting a sequence with a custom comparator:"
  13 { $subsection sort }
  14 "Sorting a sequence with common comparators:"
  15 { $subsection natural-sort }
  16 { $subsection sort-keys }
  17 { $subsection sort-values } ;
  18
  19 ABOUT: "sequences-sorting"
  20
  21 HELP: sort
  22 { $values { "seq" "a sequence" } { "quot" { $quotation "( obj1 obj2 -- <=> )" } } { "sortedseq" "a new sorted sequence" } }
  23 { $description "Sorts the elements into a new array using a stable sort." }
  24 { $notes "The algorithm used is the merge sort." } ;
  25
  26 HELP: sort-keys
  27 { $values { "seq" "an alist" } { "sortedseq" "a new sorted sequence" } }
  28 { $description "Sorts the elements comparing first elements of pairs using the " { $link <=> } " word." } ;
  29
  30 HELP: sort-values
  31 { $values { "seq" "an alist" } { "sortedseq" "a new sorted sequence" } }
  32 { $description "Sorts the elements comparing second elements of pairs using the " { $link <=> } " word." } ;
  33
  34 HELP: natural-sort
  35 { $values { "seq" "a sequence of real numbers" } { "sortedseq" "a new sorted sequence" } }
  36 { $description "Sorts a sequence of objects in natural order using the " { $link <=> } " word." } ;
  37
  38 HELP: sort-pair
  39 { $values { "a" object } { "b" object } { "c" object } { "d" object } }
  40 { $description "If " { $snippet "a" } " is greater than " { $snippet "b" } ", exchanges " { $snippet "a" } " with " { $snippet "b" } "." } ;
  41
  42 HELP: midpoint@
  43 { $values { "seq" "a sequence" } { "n" integer } }
  44 { $description "Outputs the index of the midpoint of " { $snippet "seq" } "." } ;
  45
  46 { <=> compare natural-sort sort-keys sort-values } related-words