home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / c / 13285 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  2.4 KB
  1. Path: sparky!uunet!elroy.jpl.nasa.gov!usc!rpi!batcomputer!munnari.oz.au!goanna!ok
  2. From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: How can one make a dynamic array?
  5. Message-ID: <14366@goanna.cs.rmit.oz.au>
  6. Date: 7 Sep 92 05:59:06 GMT
  7. References: <aphaswan.1.0@cs1.uct.ac.za>
  8. Organization: Comp Sci, RMIT, Melbourne, Australia
  9. Lines: 50
  10.  
  11. In article <aphaswan.1.0@cs1.uct.ac.za>, aphaswan@cs1.uct.ac.za (AK PHASWANA) writes:
  12. > Most sorting procedures like bubble sort, bisection method, merge sort,
  13. > use arrays.
  14.  
  15. Only the versions that are set up to sort arrays.
  16. Bubble sort (does anyone ever _use_ it other than as a horrible example of
  17. what _not_ to do), insertion sort, selection sort, heap sort, quick sort,
  18. merge sort, all work perfectly well with linked lists.  About the only
  19. well-known sorting method that even begins to be tricky with lists is
  20. Shell sort.  I haven't heard of any sorting algorithm called "bisection
  21. method", how does it work?
  22.  
  23. > The problem with arrays is that they are not dynamic.
  24.  
  25. Only in antique languages like C and Pascal.  Earlier languages like
  26. Algol 60, PL/I, and Algol 68 let you declare arrays whose size is not
  27. known until run-time.  Newer languages like Ada, Fortran, and GNU C (the
  28. language implemented by GCC) also allow this.  For example, in GNU C you
  29. can write
  30.  
  31.     void sort(int n, EltType a[]) {
  32.         auto EltType work[n];
  33.         ...
  34.     }
  35.  
  36. Even in C you can use malloc() to make an array of whatever size you want
  37. (apart from addressing problems on i8086-based machines):
  38.     void sort(int n, EltType a[]) {
  39.         auto EltType *work = malloc(n * sizeof *work);
  40.         assert(work != NULL);
  41.         ... use work[] ...
  42.         free(work);
  43.     }
  44. Having to release the storage yourself is a pain and a common source
  45. of errors.  Viva GNU C!  (Come to that, viva Ada!)
  46.  
  47. > Or is there any way of implementic sorting and searching procedures
  48. > without using arrays?
  49.  
  50. For many applications you will find one-way linked lists a _superb_ data
  51. structure.  Merge sort in particular (one of the most efficient and
  52. adaptable sorting methods around, demonstrably faster than quicksort)
  53. just loves linked lists.
  54.  
  55. For searching, you might as well use red-black trees or splay trees or
  56. even AVL trees; as dynamic as you please and O(lgN) lookup and update.
  57. See any good data structures textbook, e.g. Sedgewick's "Algorithms in C".
  58.  
  59. -- 
  60. You can lie with statistics ... but not to a statistician.
  61.