home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume34 / flogger / part02 / bubble_sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-18  |  3.3 KB  |  122 lines
  1.  
  2. /* 
  3.  
  4. NAME
  5.   bubble sort
  6.  
  7. DESCRIPTION
  8.  
  9.   Traipse up and down the records until the entire array is in order
  10.   exchanging records with their neighbors if the adjacent records are
  11.   out of order with respect to each other.  A flag keeps track of
  12.   whether exchanges were done; when an entire pass is made and no
  13.   exchanges were performed, the sort is complete.  Also, after each
  14.   pass, the element at the end of the pass is guaranteed to be in it's
  15.   final place so the next pass excludes it.
  16.  
  17.   This algorithm reverses direction on each pass, so that a single item
  18.   out of order won't force worst-case behavior.  Knuth refers to this
  19.   as the "cocktail shaker sort."
  20.  
  21. AUTHORSHIP
  22.  
  23.   Unknown to me.
  24.  
  25. REFERENCES
  26.  
  27.   Knuth Vol 3, page 106-111
  28.  
  29. COMPLEXITY
  30.  
  31.   Best case O(n)
  32.   Worst case O(n^2)
  33.   Iterative.
  34.  
  35. COPYRIGHT
  36.  
  37.   Copyright 1992 Michael Lee.
  38.  
  39.   (1) Permission to use, copy, distribute, and make changes is granted
  40.   providing that (a) that you do so without charging anyone a fee and
  41.   (b) this copyright notice must be included verbatim in all copies and 
  42.   distributions.  
  43.  
  44.   (2) There is no warranty for this program, to the extent permitted by
  45.   applicable law.  This program is provided "AS IS" without warranty of
  46.   any kind, either expressed or implied, including, but not limited to,
  47.   the implied warranties of merchantability and fitness for a particular 
  48.   purpose.  The entire risk as to the quality and performance of this 
  49.   program is with the user.  Should this program prove defective, the 
  50.   user assumes the cost of all necessary servicing, repair or correction.
  51.  
  52.   (3) In no event unless required by applicable law will the copyright
  53.   holder be liable to the user for damages, including any general,
  54.   special, incidental or consequential damages arising out of the use
  55.   or inability to use this program (including but not limited to loss of
  56.   data or data being rendered inaccurate or losses sustained by the
  57.   user or third parties or a failure of this program to operate with any
  58.   other programs), even if such holder or third party has been advised
  59.   of the possibility of such damages.
  60.  
  61.   (4) Object code produced by a compiler from this code may be 
  62.   incorporated into commercial products without being subject to 
  63.   restrictions (1)(a) or (1)(b).
  64.  
  65. */
  66.  
  67. #include <stdio.h>
  68. #include <malloc.h>
  69. #include <memory.h>
  70. #include <string.h>
  71. #include <assert.h>
  72.  
  73. #include "sorting.h"
  74.  
  75. int bubble_sort(base, nelem, width, cmpr_func)
  76.   char * base;
  77.   int nelem;
  78.   int width;
  79.   int (*cmpr_func)();
  80. {
  81.   int top = nelem - 1;
  82.   int bottom = 0;
  83.   int i, did_swap = 1;
  84.   char * temp;
  85.  
  86.   temp = malloc(width);
  87.   assert(temp != NULL);
  88.  
  89.   while (top > bottom)
  90.   {
  91.     did_swap = 0;
  92.     for (i = bottom; i < top; i++)
  93.       if ((*cmpr_func)(base+i*width, base+(i+1)*width) > 0)
  94.       {
  95.         memcpy(temp, base+i*width, width);
  96.         memcpy(base+i*width, base+(i+1)*width, width);
  97.         memcpy(base+(i+1)*width, temp, width);
  98.         did_swap = 1;
  99.       }
  100.  
  101.     if (!did_swap) break;
  102.     top--;
  103.  
  104.     did_swap = 0;
  105.     for (i = top - 1; i >= bottom; i--)
  106.       if ((*cmpr_func)(base+i*width, base+(i+1)*width) > 0)
  107.       {
  108.         memcpy(temp, base+i*width, width);
  109.         memcpy(base+i*width, base+(i+1)*width, width);
  110.         memcpy(base+(i+1)*width, temp, width);
  111.         did_swap = 1;
  112.       }
  113.  
  114.     if (!did_swap) break;
  115.     bottom ++;
  116.   }
  117.  
  118.   free(temp);
  119.   return 0;
  120.  
  121. }
  122.