From e92c0f6e9459e3dcc1d1dc55e856c09e813e6976 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Wed, 21 Oct 2009 18:45:18 +0000 Subject: merge sort for linked lists --- Makefile | 6 +++ lsort.c | 126 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 132 insertions(+) create mode 100644 Makefile create mode 100644 lsort.c diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..3fc6337 --- /dev/null +++ b/Makefile @@ -0,0 +1,6 @@ +# $Id$ + +PROG= lsort +NOMAN= + +.include diff --git a/lsort.c b/lsort.c new file mode 100644 index 0000000..ef58cf2 --- /dev/null +++ b/lsort.c @@ -0,0 +1,126 @@ +/* $Id$ */ +/* + * Copyright (c) 2009 Dimitri Sokolyuk + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include +#include + +typedef struct list List; + +struct list { + int value; + List *link; +}; + +int cmp(const List *, const List *); +List *lsort(List *list, int (*compar)(const List *, const List *)); +void lprint(char *, List *); + +int +cmp(const List *a, const List *b) +{ + assert(a && b); + return a->value - b->value; +} + +List * +lsort(List *list, int (*compar)(const List *, const List *)) +{ + List **listp, *p, *q, *ep, *eq; + int i, k, merges; + + assert(list && compar); + + for (k = 1;; k *= 2) { + p = list; + list = NULL; + listp = &list; + + for (merges = 0; p; merges++) { + ep = p; + for (i = 0; ep && i < k; i++) + ep = ep->link; + eq = q = ep; + for (i = 0; eq && i < k; i++) + eq = eq->link; + + while (p != ep || q != eq) { + if (p == ep && q != eq) { + *listp = q; + q = q->link; + } else if (p != ep && q == eq) { + *listp = p; + p = p->link; + } else if (p != ep && q != eq && compar(p, q) > 0) { + *listp = q; + q = q->link; + } else { + *listp = p; + p = p->link; + } + listp = &(*listp)->link; + } + p = eq; + } + *listp = NULL; + if (merges <= 1) + break; + } + + return list; +} + +void +lprint(char *pre, List *p) +{ + assert(p); + if (pre) + printf("%s\t", pre); + for (; p; p = p->link) + printf("%3d", p->value); + printf("\n"); +} + +int +main(void) +{ + List *head, **headp, *p, *next; + int order[] = {6, 2, 8, 4, 11, 1, 12, 7, 3, 9, 5, 0, 10}; + int i, n = sizeof(order) / sizeof(order[0]); + + head = NULL; + headp = &head; + + for (i = 0; i < n; i++) { + *headp = malloc(sizeof(List)); + assert(*headp); + (*headp)->value = order[i]; + headp = &(*headp)->link; + } + *headp = NULL; + + lprint(">>>", head); + head = lsort(head, cmp); + lprint("<<<", head); + + for (p = head; p; p = next) { + next = p->link; + free(p); + } + + return 0; +} -- cgit v1.2.3