home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12374 < prev    next >
Encoding:
Text File  |  1992-08-15  |  2.4 KB  |  60 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!uchinews!quads!pynq
  3. From: pynq@quads.uchicago.edu (George Jetson)
  4. Subject: Sorting (continued)
  5. Message-ID: <1992Aug15.135836.23357@midway.uchicago.edu>
  6. Summary: Looking for best sort algorithm
  7. Sender: news@uchinews.uchicago.edu (News System)
  8. Reply-To: pynq@midway.uchicago.edu
  9. Organization: D. J. Dougherty & Associates
  10. Date: Sat, 15 Aug 1992 13:58:36 GMT
  11. Lines: 47
  12.  
  13. (I know this doesn't really belong in comp.lang.c, being as it is an
  14. algorithm question.  Please advise as to better newsgroup(s))
  15.  
  16. I am trying to design an in-memory sort (no, this is not a class project)
  17. (I'm too old for that crap..., but seriously folks...) and have narrowed
  18. it down to 3 possible algorithms.  Note: It is a requirement that the
  19. design not place any limits on the input (i.e., record length or number
  20. of records)  Which do you think would be the best/most efficient?
  21.  
  22.     1) Build up a data structure along the lines of:
  23.  
  24.         struct thing {char *key,*text;}
  25.     
  26.        where the things are malloc'd in blocks and you periodically
  27.        realloc them, so as to keep a contiguous block of memory.
  28.        (I am assuming that realloc does recopy the data if it needs
  29.        to move the block - this re-copying could be costly)
  30.  
  31.        After reading all the input, call the qsort() intrinsic.
  32.  
  33.     2) Build up a linked list, along the lines of:
  34.  
  35.         struct thing {char *key,*text; struct thing *next;}
  36.     
  37.        Now, you don't have to do any reallocs, but at the end, you
  38.        have to traverse the list, and build an array of pointers to
  39.        the things and qsort that.  (You keep a count on the first
  40.        pass so that you known how big to calloc the array of
  41.        pointers)
  42.  
  43.     3) Build a binary tree in the first pass, then simply print the
  44.        tree in traversal order.
  45.  
  46. Thanks for any and all help.  These are essentially the choices, but
  47. feel free to point out any errors in my analysis.
  48.  
  49.  
  50.     (I need to re-read Knuth...)
  51.  
  52. ************************************************************************
  53. Please don't drink the battery acid, it tastes bad and will hurt you.
  54. Also, don't bite the tyres, especially when the bike is moving.
  55. (Our lawyers made us put this in this manual.)
  56.  
  57.     - pynq@quads.uchicago.edu, who is still costing the net
  58.       hundreds, if not thousands, of dollars, every time he posts -
  59. ************************************************************************
  60.