home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part02 / bogo_sort.c next >
C/C++ Source or Header  |  1992-12-18  |  4KB  |  205 lines
  1.  
  2. #undef TEST
  3. #define EXIT_SUCCESS 0
  4. #define EXIT_FAILURE 1
  5. #define RAND_MAX 32767
  6.  
  7. /*
  8.  
  9. In alt.folklore.computers, there has been a discussion of the worst
  10. possible sorting algorithm, which has been called "bogosort".
  11.  
  12. My interpretation of the algorithm is this: Exchange two randomly
  13. chosen elements of the array to be sorted.  Check to see if the array
  14. is in order.  Iterate until done.
  15.  
  16. From what I've read, theoretical analysis of this algorithm gives it a
  17. performance of O(n!), which means that the time to sort is
  18. proportional to the factorial of the number of elements.  And since
  19. the algorithm is random in nature, it could range from instantaneous
  20. (only two entries out of order, and it happens to exchange them first)
  21. to to infinite (it might never succeed).
  22.  
  23. So, for kicks I coded up a bogosort routine.
  24.  
  25. In my testing, I discovered that the mean time to sort an array of ten
  26. integers was 75 seconds (25MHz 486, Unix, gcc 2.1, "optimized").
  27.  
  28. Extrapolating from this, assuming O(n!), gives 312 days to sort 15
  29. integers and 1,593,378 years to sort 20 integers.  Someone with a much
  30. faster machine than mine will have to verify these figures.
  31.  
  32. -- 
  33. Richard Krehbiel                                 richk@grebyn.com
  34. OS/2 2.0 will do for me until AmigaDOS for the 386 comes along...
  35.  
  36.  
  37. ===== cut here ====== bogosort.c =====================================
  38.  
  39. */
  40.  
  41. #include <stdio.h>
  42. #include <stdlib.h>
  43. #include <time.h>
  44. #include <assert.h>
  45.  
  46. #define TRUE 1
  47. #define FALSE 0
  48.  
  49. #if 0
  50. #define range_rand(range) ((long)rand() * (long)range / (RAND_MAX + 1))
  51.  
  52. #if ! defined(range_rand)
  53. int range_rand(range) int range;
  54. {
  55.     return (long)rand() * (long)range / (RAND_MAX + 1);
  56. }
  57. #endif
  58.  
  59. #endif
  60.  
  61. /* bogo sort is sensitive to rand()'s repeating-lower-digits feature 
  62.    plus the above macro and function gave me different results with
  63.    and without -O, so I replaced them with this slow but serviceable
  64.    function. */
  65.  
  66. int range_rand(range) 
  67.   int range;
  68. {
  69.   int result;
  70.   extern long random();
  71.  
  72.   do { 
  73.     result = (int) random(); 
  74.   } 
  75.   while (result < 0);
  76.   
  77.   result = result % range;
  78.  
  79.   return result;
  80. }
  81.  
  82.  
  83. void swap_elem(elem1, elem2, elem_size) 
  84.                register char *elem1;
  85.                register char *elem2;
  86.                register size_t elem_size;
  87.  
  88. {
  89.     /***
  90.     int temp;
  91.  
  92.     temp = *(int*) elem1;
  93.     *(int*) elem1 = *(int*) elem2;
  94.     *(int*) elem2 = temp;
  95.     ***/
  96.  
  97.     while(elem_size-- > 0)
  98.     {
  99.         char temp;
  100.         temp = *elem1;
  101.         *elem1++ = *elem2;
  102.         *elem2++ = temp;
  103.     }
  104.  
  105. }
  106.  
  107. int in_order(base, n_elem, elem_size, compare)
  108.    register char *base;
  109.    register int n_elem;
  110.    register size_t elem_size;
  111.    int (*compare)();
  112. {
  113.     while(--n_elem > 0)
  114.     {
  115.         if(compare(base, base+elem_size) > 0)
  116.             return FALSE;
  117.         base += elem_size;
  118.     }
  119.     return TRUE;
  120. }
  121.  
  122. /*
  123.   The bogo() function:
  124.  
  125.   This function is called with the same arguments as qsort.  When it returns,
  126.   the elements of the given array are in order.
  127.  
  128.   You may wish to call srand() before using bogosort.
  129. */
  130.  
  131. int bogo_sort(base, n_elem, elem_size, compare)
  132.           char *base;
  133.           int n_elem;
  134.           size_t elem_size;
  135.           int (*compare)();
  136. {
  137.     assert(n_elem <= RAND_MAX);
  138.  
  139.     while(!in_order(base, n_elem, elem_size, compare))
  140.     {
  141.         register char *elem1, *elem2;
  142.  
  143.         elem1 = base + (range_rand(n_elem) * elem_size);
  144.         elem2 = base + (range_rand(n_elem) * elem_size);
  145.  
  146.         swap_elem(elem1, elem2, elem_size);
  147.     }
  148. }
  149.  
  150. #ifdef TEST
  151.  
  152. int array[100];        /* Up to 100 elements - no further */
  153.  
  154. int int_compare(i1, i2)
  155.   char *i1; char *i2;
  156. {
  157.     return *(int *)i1 - *(int *)i2;
  158. }
  159.  
  160. main(argc, argv)
  161.   int argc; char *argv[];
  162. {
  163.     time_t now;
  164.     int n_elem;
  165.     int i;
  166.  
  167.     if(argc < 2)
  168.     {
  169.         fprintf(stderr, "useage: %s <number of elements>\n",
  170.                 argv[0]);
  171.         exit(EXIT_FAILURE);
  172.     }
  173.  
  174.     n_elem = atoi(argv[1]);
  175.     if(n_elem > 100)
  176.     {
  177.         fprintf(stderr, 
  178.   "No more than 100 elements, please (as if your life is that long...)\n");
  179.         exit(EXIT_FAILURE);
  180.     }
  181.  
  182.     now = time((time_t *)NULL);
  183.     srandom(now);
  184.  
  185.     fputs("Starting array:\n", stdout);
  186.  
  187.     for(i = 0; i < n_elem; i++)
  188.     {
  189.         array[i] = random();
  190.         printf("%d ", array[i]);
  191.     }
  192.     fputs("\n", stdout);
  193.  
  194.     bogo_sort((char *)array, n_elem, sizeof(int), int_compare);
  195.  
  196.     fputs("Ending array:\n", stdout);
  197.     for(i = 0; i < n_elem; i++)
  198.     {
  199.         printf("%d ", array[i]);
  200.     }
  201.     fputs("\n", stdout);
  202. }
  203. #endif
  204.  
  205.