From af4eaf3663b79553af78facf8128b8d65fd484d0 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sun, 22 Dec 2013 16:02:03 +0000 Subject: be more verbose --- lsort.c | 36 +++++++++++++++++++----------------- 1 file changed, 19 insertions(+), 17 deletions(-) diff --git a/lsort.c b/lsort.c index c93b08d..66ade94 100644 --- a/lsort.c +++ b/lsort.c @@ -14,6 +14,7 @@ * 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 @@ -28,7 +29,7 @@ struct list { }; int cmp(const List *, const List *); -List *lsort(List *list, int (*compar)(const List *, const List *)); +List *lsort(List *list, int (*compare)(const List *, const List *)); void lprint(char *, List *); int @@ -39,12 +40,12 @@ cmp(const List *a, const List *b) } List * -lsort(List *list, int (*compar)(const List *, const List *)) +lsort(List *list, int (*compare)(const List *, const List *)) { - List **listp, *p, *q, *ep, *eq; + List **listp, *p, *q, *endp, *endq; int i, k, merges; - assert(list && compar); + assert(list && compare); k = 1; do { @@ -53,21 +54,22 @@ lsort(List *list, int (*compar)(const List *, const List *)) 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) { + 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 != ep && q == eq) { + } else if (p != endp && q == endq) { *listp = p; p = p->link; - } else if (p != ep && q != eq && compar(p, q) > 0) { + } else if (p != endp && q != endq && + compare(p, q) > 0) { *listp = q; q = q->link; } else { @@ -76,7 +78,7 @@ lsort(List *list, int (*compar)(const List *, const List *)) } listp = &(*listp)->link; } - p = eq; + p = endq; } *listp = NULL; lprint(">", list); @@ -112,7 +114,7 @@ main(int argc, char **argv) for (i = 0; i < n; i++) { *headp = malloc(sizeof(List)); assert(*headp); - (*headp)->value = random() % n; + (*headp)->value = random() % (n << 1); headp = &(*headp)->link; } *headp = NULL; -- cgit v1.2.3