fork download 
  1. /*
  2.   ・参照透過性は考慮していない
  3.   ・型のパラメータ化？には挑戦してない
  4.   ・パターンマッチ再現？にも挑戦してない
  5.   ・クロージャが欲しいところには呼び出し元の文脈を手渡して誤魔化す
  6.   ・グローバル変数一個使ってノードの再利用を試みてる
  7.   ・とにかくlist_qsort内部がそれっぽい感じの手順になってたらヨシ
  8. */
  9. #include <stdlib.h>
  10. #include <stdio.h>
  11. struct node {
  12.   int value;
  13.   struct node *next;
  14. };
  15. struct node *list_pop(struct node *list, struct node **p) {
  16.   return (*p = list) ? list->next : list;
  17. }
  18. struct node *list_push(struct node *list, struct node *p) {
  19.   if (!p)
  20.     return list;
  21.   else {
  22.     p->next = list;
  23.     return p;
  24.   }
  25. }
  26. struct node *list_new() {
  27.   return malloc(sizeof (struct node));
  28. }
  29. void list_each(void (f)(int), const struct node *list) {
  30.   for (; list; list = list->next) f(list->value);
  31. }
  32. int list_length(const struct node *list) {
  33.   int len = 0;
  34.   for (; list; list = list->next) len++;
  35.   return len;
  36. }
  37.  
  38. struct node *available = 0;
  39. struct node *list_available_pop() {
  40.   struct node *p = 0;
  41.   available = list_pop(available, &p);
  42.   return p;
  43. }
  44. void list_available_free() {
  45.   struct node *p;
  46.   while (p = list_available_pop()) free(p);
  47. }
  48. void list_available_push(struct node *p) {
  49.   available = list_push(available, p);
  50. }
  51. void list_available_push_all(struct node *list) {
  52.   struct node *next = 0;
  53.   for (; list; list = next) {
  54.     next = list->next;
  55.     list_available_push(list);
  56.   }
  57. }
  58. int list_available_length() {
  59.   return list_length(available);
  60. }
  61. struct node *list_cons(int value, struct node *next) {
  62.   struct node *p = list_available_pop();
  63.   if (!p) p = list_new();
  64.   p->value = value, p->next = next;
  65.   return p;
  66. }
  67. struct node *rev(const struct node *list) {
  68.   struct node *p = 0;
  69.   for (; list; list = list->next) p = list_cons(list->value, p);
  70.   return p;
  71. }
  72. struct node *list_append(const struct node *a, const struct node *b) {
  73.   struct node *c = 0, *p, *next;
  74.   for (p = rev(b); p; p = next) next = p->next, p->next = c, c = p;
  75.   for (p = rev(a); p; p = next) next = p->next, p->next = c, c = p;
  76.   return c;
  77. }
  78. void list_partition(void *context, int (predicate)(void *, int), const struct node *list, struct node **a, struct node **b) {
  79.   struct node *p, *next, **x;
  80.   for (*a = 0, *b = 0, p = rev(list); p; p = next)
  81.     x = predicate(context, p->value) ? a : b, next = p->next, p->next = *x, *x = p;
  82. }
  83. int less_than_context(void *context, int value) {
  84.   return value < *(int *)context;
  85. }
  86. void list_available_push_all4(struct node *a, struct node *b, struct node *c, struct node *d) {
  87.   list_available_push_all(a), list_available_push_all(b), list_available_push_all(c), list_available_push_all(d);
  88. }
  89. struct node *list_qsort(const struct node *list) {
  90.   int pivot;
  91.   struct node *sorted = 0, *tail, *smaller, *rest, *a, *b;
  92.   if (list) {
  93.     pivot = list->value, tail = list->next;
  94.     list_partition(&pivot, less_than_context, tail, &smaller, &rest);
  95.     sorted = list_append(a = list_qsort(smaller), b = list_cons(pivot, list_qsort(rest)));
  96.     list_available_push_all4(smaller, rest, a, b);
  97.   }
  98.   return sorted;
  99. }
  100. void print_int(int x) {printf("%d", x);}
  101. int main() {
  102.   struct node *list = list_cons(4, list_cons(8, list_cons(8, list_cons(3, 0))));
  103.   struct node *sorted = list_qsort(list);
  104.   list_each(print_int, list);puts("");
  105.   list_each(print_int, sorted);puts("");
  106.   list_available_push_all(list), list = 0;
  107.   list_available_push_all(sorted), sorted = 0;
  108.   list_available_free();
  109.   return 0;
  110. }
  111.  
Success #stdin #stdout 0s 5392KB
comments (?)
stdin 
Standard input is empty
stdout 
4883
3488
https://ideone.com/j5KR8Y
language:
C (gcc 8.3)
created:
209 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!