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 sort-with }
  16 { $subsection inv-sort-with }
  17 { $subsection natural-sort }
  18 { $subsection sort-keys }
  19 { $subsection sort-values } ;
  20
  21 ABOUT: "sequences-sorting"
  22
  23 HELP: sort
  24 { $values { "seq" "a sequence" } { "quot" { $quotation "( obj1 obj2 -- <=> )" } } { "sortedseq" "a new sorted sequence" } }
  25 { $description "Sorts the elements of " { $snippet "seq" } " into a new array using a stable sort." }
  26 { $notes "The algorithm used is the merge sort." } ;
  27
  28 HELP: sort-with
  29 { $values { "seq" "a sequence" } { "quot" { $quotation "( object -- key )" } } { "sortedseq" "a new sorted sequence" } }
  30 { $description "Sorts the elements of " { $snippet "seq" } " by applying " { $link compare } " with " { $snippet "quot" } " to each pair of elements in the sequence." } ;
  31
  32 HELP: inv-sort-with
  33 { $values { "seq" "a sequence" } { "quot" { $quotation "( object -- key )" } } { "sortedseq" "a new sorted sequence" } }
  34 { $description "Sorts the elements of " { $snippet "seq" } " by applying " { $link compare } " with " { $snippet "quot" } " to each pair of elements in the sequence and inverting the results." } ;
  35
  36 HELP: sort-keys
  37 { $values { "seq" "an alist" } { "sortedseq" "a new sorted sequence" } }
  38 { $description "Sorts the elements of " { $snippet "seq" } " comparing first elements of pairs using the " { $link <=> } " word." } ;
  39
  40 HELP: sort-values
  41 { $values { "seq" "an alist" } { "sortedseq" "a new sorted sequence" } }
  42 { $description "Sorts the elements of " { $snippet "seq" } " comparing second elements of pairs using the " { $link <=> } " word." } ;
  43
  44 HELP: natural-sort
  45 { $values { "seq" "a sequence of real numbers" } { "sortedseq" "a new sorted sequence" } }
  46 { $description "Sorts a sequence of objects in natural order using the " { $link <=> } " word." } ;
  47
  48 HELP: sort-pair
  49 { $values { "a" object } { "b" object } { "c" object } { "d" object } }
  50 { $description "If " { $snippet "a" } " is greater than " { $snippet "b" } ", exchanges " { $snippet "a" } " with " { $snippet "b" } "." } ;
  51
  52 HELP: midpoint@
  53 { $values { "seq" "a sequence" } { "n" integer } }
  54 { $description "Outputs the index of the midpoint of " { $snippet "seq" } "." } ;
  55
  56 { <=> compare natural-sort sort-with inv-sort-with sort-keys sort-values } related-words