home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / fileutil / ksort12.arj / KSORT.DOC < prev    next >
Encoding:
Text File  |  1991-06-05  |  3.0 KB  |  74 lines
  1. KSORT  Copyright (c) Josh Greifer 1991
  2.  
  3. This program allows sorting of text files of any size up to 20Mb, or one
  4. million lines, up to 30 times faster than DOS sort.com.
  5.  
  6. The syntax is identical to DOS sort.com, including the /R and /+ switches.  In
  7. addition you can specify input and output files instead of using it as a pipe,
  8. turn case sensitivity on, ignore leading white space in the sort, display
  9. messages during long sorts, and specify a line buffer smaller than the default
  10. 16k lines if you don't have enough RAM.
  11.  
  12. The algorithm used is D.E.Knuth's partition-exchange sort, which is a
  13. double-ended Quicksort (i.e. sorting is done from both ends of the array).
  14.  
  15. The algorithm is in Knuth's "The Art of Computer Programming",
  16. Volume 3, "Sorting and Searching", Section 5.2.2, p. 117.
  17.  
  18. Besides being much faster than most qsort() implementations in commercial
  19. C libraries, it uses no stack, so it won't cause a stack overflow on nasty
  20. files (such as reverse-ordered files).
  21.  
  22. The algorithm drops through to a enhanced insertion sort (bubble sort) at
  23. a user-specified point. If the the threshold is, say, 50, then the last 50
  24. lines to be sorted will be insertion-sorted. The threshold is set with the
  25. /I switch. If it's less than 1, no insertion sort takes place. If it's
  26. set to a value greater than the buffer size, the entire sort is done using
  27. the insertion sort.
  28.  
  29. The program is written in Microsoft C 6.0 -- remove the underscores before
  30. the "_huge" keyword, and it should compile with 5.1. You MUST use the
  31. /AC (Compact Model) switch.
  32.  
  33. For a blindingly fast version that sorts small (< 100k) files, get rid
  34. of the halloc() call, and reduce MAXARRAYSIZE to 16382. Now compile for
  35. the Small Model /AS.
  36.  
  37. The function ksort() in the source uses goto's and labels. These match
  38. Knuth's Q algorithm exactly. It's not too hard to rewrite in assembler --
  39. it looks more like assembler than C, anyway!
  40.  
  41. The program will create temporary files if necessary, and then merge them.
  42.  
  43. Remember, ksort is meant to replace DOS sort.com, so it defaults to
  44. "silent" behaviour, and should be used as a pipe:
  45.  
  46.     type bigfile.txt | ksort > bigfile.srt
  47.  
  48. Alternatively you can use it like this:
  49.  
  50.     ksort bigfile.txt bigfile.srt
  51.  
  52. or like this:
  53.  
  54.     ksort bigfile.txt
  55.  
  56. which will convert the file "in place", deleting the unsorted version.
  57.  
  58. The switches are summarised below: (Case Sensitive)
  59.  
  60. Usage: ksort [/R] [/+<column>] [/N] [/S] [/v|V] [/B<size>] [infile] [outfile]
  61.  
  62.     option        description                 default
  63.     -----------------------------------------------------------
  64.     R      - reverse sort                  (off)
  65.     +<column> - start sort at <column>            (1)
  66.     N      - Don't ignore case                         (off)
  67.     S      - Skip and trim leading white space          (off)
  68.     v      - verbose -- screen messages              (off)
  69.     V      - Very verbose -- more screen messages      (off)
  70.     I<lines>  - Insertion Sort threshold (see above)    (0)
  71.     B<lines>  - Buffer size (number of lines) max 64000 (16000)
  72.  
  73.  
  74.