core/sorting/sorting-docs.factor

   1 USING: help.markup help.syntax kernel 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 { $subsections sort }
  14 "Sorting a sequence with common comparators:"
  15 { $subsections
  16     sort-with
  17     inv-sort-with
  18     natural-sort
  19     sort-keys
  20     sort-values
  21 } ;
  22
  23 ABOUT: "sequences-sorting"
  24
  25 HELP: sort
  26 { $values { "seq" sequence } { "quot" { $quotation ( obj1 obj2 -- <=> ) } } { "sortedseq" "a new sorted sequence" } }
  27 { $description "Sorts the elements of " { $snippet "seq" } " into a new array using a stable sort." }
  28 { $notes "The algorithm used is the merge sort." } ;
  29
  30 HELP: sort-with
  31 { $values { "seq" sequence } { "quot" { $quotation ( elt -- key ) } } { "sortedseq" "a new sorted sequence" } }
  32 { $description "Sorts the elements of " { $snippet "seq" } " by applying " { $link compare } " with " { $snippet "quot" } " to each pair of elements in the sequence." } ;
  33
  34 HELP: inv-sort-with
  35 { $values { "seq" sequence } { "quot" { $quotation ( elt -- key ) } } { "sortedseq" "a new sorted sequence" } }
  36 { $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." } ;
  37
  38 HELP: sort-keys
  39 { $values { "obj" object } { "sortedseq" "a new sorted sequence" } }
  40 { $description "Sorts the elements of " { $snippet "obj" } " (converting to an alist first if not a sequence), comparing first elements of pairs using the " { $link <=> } " word." } ;
  41
  42 HELP: sort-values
  43 { $values { "obj" object } { "sortedseq" "a new sorted sequence" } }
  44 { $description "Sorts the elements of " { $snippet "obj" } " (converting to an alist first if not a sequence), comparing second elements of pairs using the " { $link <=> } " word." } ;
  45
  46 HELP: natural-sort
  47 { $values { "seq" sequence } { "sortedseq" "a new sorted sequence" } }
  48 { $description "Sorts a sequence of objects in natural order using the " { $link <=> } " word." } ;
  49
  50 HELP: sort-pair
  51 { $values { "a" object } { "b" object } { "c" object } { "d" object } }
  52 { $description "If " { $snippet "a" } " is greater than " { $snippet "b" } ", exchanges " { $snippet "a" } " with " { $snippet "b" } "." } ;
  53
  54 HELP: compare-with
  55 { $values { "quots" { $sequence { $quotation ( obj1 obj2 -- <=> ) } } } }
  56 { $description "Generate a chained comparator using the specified " { $snippet "quots" } " sequence of comparators." } ;
  57
  58 HELP: midpoint@
  59 { $values { "seq" sequence } { "n" integer } }
  60 { $description "Outputs the index of the midpoint of " { $snippet "seq" } "." } ;
  61
  62 { <=> compare compare-with natural-sort sort-with inv-sort-with sort-keys sort-values } related-words