C   50

sorts

Guest on 11th July 2022 07:33:27 PM

  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. #define N               1000
  7.  
  8. #if N > 1000000
  9. #error "Value of N too big, must be <= 1000000"
  10. #endif
  11.  
  12. #define LOG10_N         6
  13. #define N_FORMAT        "%06d"
  14.  
  15. #if N <= 1000
  16. static void insert_sort(char *strings[], int n)
  17. {
  18.     char *v, *t;
  19.     char **strp, **endp;
  20.     int i;
  21.  
  22.     endp = &strings[N-1];
  23.     i = N-2;
  24.     do {
  25.         strp = &strings[i];
  26.         v = strp[0];
  27.         do {
  28.             t = strp[1];
  29.             if (strcmp(v, t) <= 0) break;
  30.             *strp++ = t;
  31.         } while (strp < endp);
  32.         strp[0] = v;
  33.     } while (--i >= 0);
  34. }
  35. #endif
  36.  
  37. static void shell_sort(char *strings[], int n)
  38. {
  39.     int h, i, j;
  40.     char *v;
  41.  
  42.     strings--;        /* Make array 1 origin */
  43.     h = 1;
  44.     do {h = h * 3 + 1;} while (h <= n);
  45.     do {
  46.         h = h / 3;
  47.         for (i = h + 1; i <= n; i++) {
  48.             v = strings[i];
  49.             j = i;
  50.             while (j > h && strcmp(strings[j-h], v) > 0) {
  51.                 strings[j] = strings[j-h];
  52.                 j = j-h;
  53.             }
  54.             strings[j] = v;
  55.         }
  56.     }
  57.     while (h > 1);
  58. }
  59.  
  60. static void randomise(char *strings[], int n)
  61. {
  62.     int i;
  63.     int v;
  64.     char *t;
  65.  
  66.     /* srand(clock());  /* comment out for reproducible results */
  67.     for (i = 0; i < N; i++) {
  68.         v = rand() % N;
  69.         t = strings[v];
  70.         strings[v] = strings[i];
  71.         strings[i] = t;
  72.     }
  73. }
  74.  
  75. static void check_order(char *sort_type, char *strings[], int n)
  76. {
  77.     int i;
  78.  
  79.     for (i = 0; i <= n; i++) {
  80.         if (atoi(strings[i]) != i) {
  81.             fprintf(stderr, "%s sort failed - exiting\n", sort_type);
  82.             exit(1);
  83.         }
  84.     }
  85. }
  86.  
  87. int qs_string_compare(const void *a, const void *b)
  88. {
  89.     return strcmp(*(char **)a, *(char **)b);
  90. }
  91.  
  92. int main(void)
  93. {
  94.     char *strings[N], *strings_copy[N];
  95.     char buffer[N*(LOG10_N+1)];
  96.     char *p;
  97.     clock_t starttime, endtime;
  98.     int i;
  99.  
  100.     p = buffer;
  101.     for (i = 0; i < N; i++) {
  102.         sprintf(p, N_FORMAT, i);
  103.         strings[i] = p;
  104.         p += LOG10_N+1;
  105.     }
  106.     randomise(strings, N);
  107.  
  108. #if N <= 1000
  109.     /* Do insertion sort */
  110.     memcpy(strings_copy, strings, sizeof(strings));
  111.     starttime = clock();
  112.     insert_sort(strings_copy, N);
  113.     endtime = clock();
  114.     check_order("Insertion", strings_copy, N);
  115.     printf("Insertion sort took %d clock ticks\n", endtime - starttime);
  116. #else
  117.     printf("Value of N too big to use insertion sort, must be <= 1000\n");
  118. #endif
  119.  
  120.     /* Do shell sort */
  121.     memcpy(strings_copy, strings, sizeof(strings));
  122.     starttime = clock();
  123.     shell_sort(strings_copy, N);
  124.     endtime = clock();
  125.     check_order("Shell", strings_copy, N);
  126.     printf("Shell sort took %d clock ticks\n", endtime - starttime);
  127.  
  128.     /* Do quick sort - use built-in C library sort */
  129.     memcpy(strings_copy, strings, sizeof(strings));
  130.     starttime = clock();
  131.     qsort(strings_copy, N, sizeof(char *), qs_string_compare);
  132.     endtime = clock();
  133.     check_order("Quick", strings_copy, N);
  134.     printf("Quick sort took %d clock ticks\n", endtime - starttime);
  135. }

Raw Paste


Login or Register to edit or fork this paste. It's free.