/* $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. */ /* inplace merge sort example implementation for single-linked lists */ #include #include #include #include typedef struct list List; struct list { int value; List *link; }; int cmp(const List *, const List *); List *lsort(List *list, int (*compare)(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 (*compare)(const List *, const List *)) { List **listp, *p, *q, *endp, *endq; int i, k, merges; assert(list && compare); k = 1; do { p = list; list = NULL; listp = &list; for (merges = 0; p; merges++) { endp = p; for (i = 0; endp && i < k; i++) endp = endp->link; endq = q = endp; for (i = 0; endq && i < k; i++) endq = endq->link; while (p != endp || q != endq) { if (p == endp && q != endq) { *listp = q; q = q->link; } else if (p != endp && q == endq) { *listp = p; p = p->link; } else if (p != endp && q != endq && compare(p, q) > 0) { *listp = q; q = q->link; } else { *listp = p; p = p->link; } listp = &(*listp)->link; } p = endq; } *listp = NULL; lprint(">", list); k *= 2; } while (merges > 1); 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(int argc, char **argv) { List *head, **headp, *p, *next; int i, n; n = (argc == 2) ? atoi(argv[1]) : 13; head = NULL; headp = &head; srandom(time(NULL)); for (i = 0; i < n; i++) { *headp = malloc(sizeof(List)); assert(*headp); (*headp)->value = random() % (n << 1); 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; }