fork download
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <assert.h>
  5.  
  6. /* #define DEBUG */
  7. #if defined(DEBUG)
  8. #include "xmalloc.h"
  9. #else
  10. #define xmalloc(x, y) malloc(x)
  11. #define xfree(x, y) free(x)
  12. #define xrealloc(x, y, z) realloc(x, y)
  13. #define xmallocdump()
  14. #endif
  15. #define ID_DATANODE 1001
  16.  
  17. struct node {
  18. int value;
  19. struct node *next;
  20. };
  21.  
  22. void push(struct node **root, int value) {
  23. struct node *p;
  24. if ((p = xmalloc(sizeof(struct node), ID_DATANODE)) != 0) {
  25. p->value = value;
  26. p->next = *root;
  27. *root = p;
  28. }
  29. }
  30.  
  31. int pop(struct node **root, int *value) {
  32. int r;
  33. struct node *p;
  34. r = 0;
  35. if (*root != 0) {
  36. p = *root;
  37. *root = p->next;
  38. *value = p->value;
  39. xfree(p, ID_DATANODE);
  40. r = 1;
  41. }
  42. return r;
  43. }
  44.  
  45. void sub_swap(struct node **p, struct node **q) {
  46. struct node *t, *s;
  47. if (&((*p)->next) == q) {
  48. assert((*p)->next == *q);
  49. t = *p;
  50. s = (*q)->next;
  51. *p = (*p)->next;
  52. (*q)->next = t;
  53. *q = s;
  54. } else {
  55. t = *p;
  56. *p = *q;
  57. *q = t;
  58. s = (*p)->next; /* in fact *p<=>*q but neet to do (*p)->next <=> (*q)->next */
  59. (*p)->next = (*q)->next;
  60. (*q)->next = s;
  61. }
  62. }
  63.  
  64. void combsort(struct node **root, int n, int (*comp)(int, int)) {
  65. struct node **p, **q;
  66. int i, h, flag, c;
  67. c = 0;
  68. h = n;
  69. do {
  70. /* h = (int)(h / 1.247330950103979); */
  71. h = 1; /* force to bubble-sort. */
  72. if (h == 10)
  73. h = 11;
  74. if (h < 1)
  75. h = 1;
  76. fprintf(stderr, "%d:%d\n", ++c, h);
  77. flag = 0;
  78. for (q = root, i = 0; i < h; q = &((*q)->next), i++)
  79. ;
  80. p = root;
  81. for (;;) {
  82. if (comp((*p)->value, (*q)->value) > 0) {
  83. flag = 1;
  84. sub_swap(p, q);
  85. }
  86. if (*p == 0 || *q == 0 || (*p)->next == 0 || (*q)->next == 0)
  87. break;
  88. p = &((*p)->next);
  89. q = &((*q)->next);
  90. }
  91. } while (flag);
  92. }
  93.  
  94. int cmp_ascent(int a, int b) {
  95. return a - b;
  96. }
  97.  
  98. int isSortOK(struct node *root) {
  99. if (root->next) {
  100. if (root->value <= root->next->value) {
  101. return isSortOK(root->next);
  102. } else {
  103. return 0;
  104. }
  105. } else {
  106. return 1;
  107. }
  108. }
  109.  
  110. #define SEED 31415926
  111. #define N 100
  112. int main(int argc, char *argv[]) {
  113. struct node *root;
  114. int i, v, flag;
  115.  
  116. root = 0;
  117. srand(SEED);
  118. for (i = 0; i < N; i++)
  119. push(&root, (rand() / (RAND_MAX + 1.0) * 1000.0));
  120.  
  121. combsort(&root, i, cmp_ascent);
  122. flag = isSortOK(root);
  123.  
  124. i = 0;
  125. while (pop(&root, &v) != 0)
  126. printf("%3d : %4d\n", ++i, v);
  127.  
  128. if (flag)
  129. fprintf(stderr, "Good.\n");
  130. else
  131. fprintf(stderr, "NG, there are some bugs in this program.\n");
  132. xmallocdump();
  133. return 0;
  134. }
  135. /* end */
  136.  
Success #stdin #stdout 0.02s 1808KB
stdin
Standard input is empty
stdout
  1 :    2
  2 :    5
  3 :   12
  4 :   14
  5 :   26
  6 :   27
  7 :   42
  8 :   44
  9 :   73
 10 :   96
 11 :  104
 12 :  118
 13 :  123
 14 :  133
 15 :  139
 16 :  171
 17 :  173
 18 :  183
 19 :  184
 20 :  191
 21 :  193
 22 :  197
 23 :  197
 24 :  199
 25 :  200
 26 :  206
 27 :  208
 28 :  228
 29 :  276
 30 :  280
 31 :  293
 32 :  299
 33 :  304
 34 :  316
 35 :  323
 36 :  323
 37 :  326
 38 :  332
 39 :  335
 40 :  339
 41 :  344
 42 :  374
 43 :  382
 44 :  384
 45 :  396
 46 :  410
 47 :  417
 48 :  423
 49 :  427
 50 :  432
 51 :  442
 52 :  452
 53 :  454
 54 :  459
 55 :  474
 56 :  510
 57 :  520
 58 :  541
 59 :  565
 60 :  581
 61 :  603
 62 :  610
 63 :  626
 64 :  628
 65 :  629
 66 :  629
 67 :  644
 68 :  648
 69 :  671
 70 :  672
 71 :  684
 72 :  700
 73 :  709
 74 :  712
 75 :  715
 76 :  742
 77 :  753
 78 :  785
 79 :  793
 80 :  796
 81 :  828
 82 :  828
 83 :  829
 84 :  839
 85 :  869
 86 :  873
 87 :  875
 88 :  879
 89 :  901
 90 :  901
 91 :  908
 92 :  910
 93 :  924
 94 :  926
 95 :  953
 96 :  955
 97 :  988
 98 :  993
 99 :  993
100 :  997