summaryrefslogtreecommitdiff
path: root/lsort.c
diff options
context:
space:
mode:
Diffstat (limited to 'lsort.c')
-rw-r--r--lsort.c36
1 files 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 <assert.h>
#include <stdio.h>
@@ -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;