home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12263 < prev    next >
Encoding:
Text File  |  1992-08-12  |  2.7 KB  |  86 lines
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Sort help needed
  5. Message-ID: <3223@dozo.and.nl>
  6. Date: 13 Aug 92 08:32:07 GMT
  7. References: <1992Aug12.154130.1@ducvax.auburn.edu>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 75
  10.  
  11. In article <1992Aug12.154130.1@ducvax.auburn.edu> swanger@ducvax.auburn.edu writes:
  12. |I am writing a program in C.  I have an array of character strings that
  13. |I want to sort (I dynamically allocate the "array" with a series of
  14. |calloc statements, so to the purist I suppose it isn't really an array,
  15. |I just pretend like it is one).  The array usually contains around 1800
  16. |strings of 512 characters each.  I sort the array (sort the pointers
  17. |actually) with the following sort routine (on a SUN IPC Sparcstation)
  18. |and it usually takes 8 to 10 seconds to finish. [ and this is too slow ... ] 
  19.  
  20. |------------------------------------------------------------------------
  21. |void sort_strings(strings, num)
  22. |char *strings[];
  23. |int num;
  24. |{
  25.   [ bubble sort algorithm deleted ... ]
  26. |}
  27.  
  28. I strongly suggest _not_ to use this algorithm. It's dead slow, it
  29. takes up O(n^2) loop iterations to sort the strings. In your example,
  30. sorting 1800 strings, the innermost instructions (inside both loops)
  31. are executed n*(n-1)/2= 1619100 times.
  32.  
  33. Have a look at the qsort function, it's in you lib somewhere. If you can't
  34. use that function for some reason (I don't see why,) may I suggest an
  35. alternative algorithm: heap sort. It's a bit slower than quick sort,
  36. but it's a very stable algorithm. i.e. quicksort might degenerate to
  37. O(n^2) behavior in the worst case, but heap sort is stable at O(n*log(n)).
  38. Both algortihms sort the array `in place', they don't need additional
  39. storage. An rudimentary implementation of the heap sort looks something
  40. like this:
  41.  
  42. void heap_sort(strings, num)
  43. char *strings[];
  44. int  num;
  45. {
  46. int n;
  47.  
  48. for (n= num/2; n >= 0; n--)        /* Build the inital heap */
  49.    heapify(strings, n, num);
  50.  
  51. for (n= 0; n < num; n++) {        /* Swap root and last element */
  52.    swap(strings, 0, num-1-n);    
  53.    heapify(strings, 0, num-1-n);    /* Build new (smaller) heap */
  54. }
  55.  
  56. }
  57.  
  58. void heapify(strings, n, num) 
  59. char *strings[];
  60. int n;                    /* Position in the heap */    
  61. int num;                /* Number of strings */
  62. {
  63. int l, r;                /* Left and right sons */
  64.  
  65. for(; (l= 2*n+1) < num;) {        /* Loop while left son present */
  66.    if ((r= l+1) < num)            /* Right son present? */
  67.       if (strcmp(strings[l],
  68.          strings[r] < 0)    /* Right son > left son */        
  69.          l= r;
  70.    if (strcmp(strings[n], 
  71.           strings[l]) >= 0)        /* Already a heap here */
  72.       break;
  73.  
  74.    swap(strings, n, l);            /* Swap root with son */
  75.  
  76.    n= l;                /* Descent this sub tree */
  77. }
  78.  
  79. }
  80.  
  81. I hope this is of any help to you,
  82.  
  83. kind regards,
  84.  
  85. Jos aka jos@and.nl
  86.