fork download 
  1. /*
  2.   ・参照透過性は考慮していない
  3.   ・型のパラメータ化？には挑戦していない
  4.   ・パターンマッチ再現？にも挑戦していない
  5.   ・クロージャが欲しいところには呼び出し元の文脈を手渡して誤魔化す
  6.   ・とにかくlist_qsort内部がそれっぽい感じの手順になってたらヨシとす
  7. */
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. struct node {
  11.   int value;
  12.   struct node *next;
  13. };
  14. void list_each(void (f)(int), const struct node *list) {
  15.   for (; list; list = list->next) f(list->value);
  16. }
  17. struct node *list_cons(int value, struct node *next) {
  18.   struct node *p = malloc(sizeof (struct node));
  19.   p->value = value, p->next = next;
  20.   return p;
  21. }
  22. void list_free(struct node *list) {
  23.   struct node *next;
  24.   for (; list; list = next) next = list->next, free(list);
  25. }
  26. struct node *rev(const struct node *list) {
  27.   struct node *p = 0;
  28.   for (; list; list = list->next) p = list_cons(list->value, p);
  29.   return p;
  30. }
  31. struct node *list_append(const struct node *a, const struct node *b) {
  32.   struct node *c = 0, *p, *next;
  33.   for (p = rev(b); p; p = next) next = p->next, p->next = c, c = p;
  34.   for (p = rev(a); p; p = next) next = p->next, p->next = c, c = p;
  35.   return c;
  36. }
  37. void list_partition(void *context, int (predicate)(void *, int), const struct node *list, struct node **a, struct node **b) {
  38.   struct node *p, *next, **x;
  39.   for (*a = 0, *b = 0, p = rev(list); p; p = next)
  40.     x = predicate(context, p->value) ? a : b, next = p->next, p->next = *x, *x = p;
  41. }
  42. int less_than_context(void *context, int value) {
  43.   return value < *(int *)context;
  44. }
  45. struct node *list_qsort(const struct node *list) {
  46.   int pivot;
  47.   struct node *sorted = 0, *tail, *smaller, *rest, *a, *b;
  48.   if (list) {
  49.     pivot = list->value, tail = list->next;
  50.     list_partition(&pivot, less_than_context, tail, &smaller, &rest);
  51.     sorted = list_append(a = list_qsort(smaller), b = list_cons(pivot, list_qsort(rest)));
  52.     list_free(smaller), list_free(rest), list_free(a), list_free(b);
  53.   }
  54.   return sorted;
  55. }
  56. void print_int(int x) {printf("%d", x);}
  57. int main() {
  58.   struct node *list = list_cons(4, list_cons(8, list_cons(8, list_cons(3, 0))));
  59.   struct node *sorted = list_qsort(list);
  60.   list_each(print_int, list);puts("");
  61.   list_each(print_int, sorted);puts("");
  62.   list_free(list), list = 0;
  63.   list_free(sorted), sorted = 0;
  64.   return 0;
  65. }
  66.  
Success #stdin #stdout 0s 5532KB
comments (?)
stdin 
Standard input is empty
stdout 
4883
3488
https://ideone.com/yYGR7x
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!