From 0887d8f96950a060a122e14ed2981182ff1eb37d Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sat, 28 Dec 2019 21:16:58 +0700 Subject: [usth/ICT2.1] Algorithm and Data Structures --- usth/ICT2.1/labwork/5/Ex2.c | 74 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 74 insertions(+) create mode 100644 usth/ICT2.1/labwork/5/Ex2.c (limited to 'usth/ICT2.1/labwork/5/Ex2.c') diff --git a/usth/ICT2.1/labwork/5/Ex2.c b/usth/ICT2.1/labwork/5/Ex2.c new file mode 100644 index 0000000..edb5c26 --- /dev/null +++ b/usth/ICT2.1/labwork/5/Ex2.c @@ -0,0 +1,74 @@ +/* + * Merge sorting integers from stdin + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +#include +#include + +#include "construct.h" + +construct *merge(construct *left, construct *right, + int (*compar)(const void *, const void *)) +{ + if (left == NULL) + return right; + if (right == NULL) + return left; + if (compar(car(left), car(right)) <= 0) + return cons(car(left), merge(cdr(left), right, compar)); + return cons(car(right), merge(left, cdr(right), compar)); +} + +construct *msort(construct *list, int (*compar)(const void *, const void *)) +{ + construct *rest, *left = NULL, *right = NULL; + while (list != NULL) { + left = cons(car(list), left); + rest = cdr(list); + if (rest == NULL) + break; + right = cons(car(rest), right); + list = cdr(rest); + } + if (left == NULL) + return right; + if (right == NULL) + return left; + return merge(msort(left, compar), msort(right, compar), compar); +} + +int cmp(const void *x, const void *y) +{ + return *(int *) x - *(int *) y; +} + +construct *iread(size_t n) +{ + if (!n) + return NULL; + int *tmp = malloc(sizeof(int)); + scanf("%d", tmp); + return cons(tmp, iread(n - 1)); +} + +void iprint(construct *list) +{ + if (list == NULL) { + putchar(10); + } else { + printf("%d ", *(int *) car(list)); + iprint(cdr(list)); + } +} + +int main() +{ + size_t n; + + scanf("%zu", &n); + iprint(msort(iread(n), cmp)); + + return 0; +} -- cgit 1.4.1