summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2009-10-21 18:45:18 +0000
committerDimitri Sokolyuk <demon@dim13.org>2009-10-21 18:45:18 +0000
commite92c0f6e9459e3dcc1d1dc55e856c09e813e6976 (patch)
tree1564141c6ad77572cea3e2b698a972f0be3d2ef7
merge sort for linked lists
-rw-r--r--Makefile6
-rw-r--r--lsort.c126
2 files changed, 132 insertions, 0 deletions
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 <bsd.prog.mk>
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 <demon@dim13.org>
+ *
+ * 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 <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+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;
+}