home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / cplus / 15826 < prev    next >
Encoding:
Text File  |  1992-11-05  |  2.2 KB  |  45 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!utcsri!torn!cunews!nrcnet0!bnrgate!bcrka451!bcrki65!sjm
  3. From: sjm@bcrki65.bnr.ca (Stuart MacMartin)
  4. Subject: Re: Making qsort type-safe
  5. Message-ID: <1992Nov5.160048.15113@bcrka451.bnr.ca>
  6. Sender: 5E00 Corkstown News Server
  7. Organization: Bell-Northern Research Ltd., Ottawa, Canada
  8. References: <1992Nov4.162131.10289@cs.brown.edu> <1992Nov5.125947.1@vax1.bham.ac.uk>
  9. Date: Thu, 5 Nov 1992 16:00:48 GMT
  10. Lines: 33
  11.  
  12. The library version of qsort on some machines behaves abysmally if many
  13. objects compare equal.  On more than one UNIX workstation I have seen qsort
  14. take more than 3/4 of an *hour* to sort a large list into two buckets,
  15. whereas an appropriately adjusted qsort takes 1/4 *second*.  (Yes I know 
  16. that qsort seems like a silly way to do what could be a single pass
  17. operation, but why should "sort" be applicable to only some kinds of sorts?)
  18.  
  19. The code that is in Lipmann is not good enough if you do a lot of sorting
  20. of large arrays.  It has none of the standard modifications to handle
  21. equal elements efficiently, to use minimal stack, etc.  It is there to
  22. show the essence of qsort and how this would be handled with templates,
  23. for instructional purposes (or perhaps for use in simple applications).
  24.  
  25. If you are sorting large arrays (or more generally, collections), you are
  26. better off sorting pointers.  This way you only swap pointers, not objects.
  27. [Also, you can then keep several sort orders for the same collection, if you
  28. want.]
  29.  
  30. If you might be sorting collections that are huge and will require paging
  31. or that have other I/O implications, you may want to use a different sort
  32. algorithm.  Is it wise to make the sorting algorithm visible outside of 
  33. the class?  (e.g. by using the name "qsort")
  34.  
  35. So about this not re-inventing the wheel business:  be careful what you reuse.
  36. Make sure it satisfies your requirements.  The blanket statements made by
  37. previous posters about reusing qsort because it is there are oversimplifying
  38. things, IMO.
  39.  
  40. Stuart
  41. --
  42. : Stuart MacMartin                                    email: sjm@bnr.ca      :
  43. : Bell-Northern Research                              phone: (613) 763-5625  :
  44. : PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :
  45.