From 8161ac06785068da5234553b528ecbbc8339e232 Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Sun, 2 Nov 2014 22:34:23 -0600 Subject: Fill buffer with smallest elements This avoids the need to distribute the buffer through the whole array at the end. It also allows us to skips most of the work for sorted and reverse-sorted inputs. --- counts.c | 2 +- counts.h | 3 ++- grailsort.c | 34 +++++++++++++++++++++++++++++++++- 3 files changed, 36 insertions(+), 3 deletions(-) diff --git a/counts.c b/counts.c index d1f3910..f644706 100644 --- a/counts.c +++ b/counts.c @@ -30,7 +30,7 @@ void add_counts(struct counts *target, struct counts *snapshot) void print_counts(void) { - char *labels[] = {"total", "sortnet", "overlap", "merge", "move buffer", "distribute"}; + char *labels[] = {"total", "sortnet", "check sorted", "steal buffer", "overlap", "merge", "distribute" }; for (int i = 0; i < MAX_COUNTS; i++) { const struct counts *c = counts+i; dprintf(42, "%12s: %10lu cmp, %10lu swap, %10lu rotate\n", labels[i], c->compare, c->swap, c->rotate); diff --git a/counts.h b/counts.h index 46e2e18..b066647 100644 --- a/counts.h +++ b/counts.h @@ -4,9 +4,10 @@ enum { CURRENT, SORTNET, + CHECK_SORTED, + STEAL_BUF, LAST_OVERLAP, MERGE, - MOVE_BUFFER, DISTRIBUTE, MAX_COUNTS }; diff --git a/grailsort.c b/grailsort.c index 9caf28f..2e0131a 100644 --- a/grailsort.c +++ b/grailsort.c @@ -83,6 +83,39 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) grailsort(buf, acount * blknmel + bufnmel, width, cmp); grailsort(b, bcount * blknmel, width, cmp); + struct counts snapshot = counts[CURRENT]; + int tmp = cmp(tail(a, acount*blknmel, width), b) <= 0; + add_counts(counts + CHECK_SORTED, &snapshot); + if (tmp) return; + + snapshot = counts[CURRENT]; + tmp = cmp(base, tail(b, bcount*blknmel, width)) >= 0; + if (tmp) { + rotate(base, nmel*width, acount*bwidth + bufnmel*width); + add_counts(counts + CHECK_SORTED, &snapshot); + return; + } + add_counts(counts + CHECK_SORTED, &snapshot); + + /* steal some small elements from b for the buffer, + * so the buffer has the bufnmel smallest elements */ + size_t usebuf = 0, stealb = 0; + snapshot = counts[CURRENT]; + do { + if (cmp(buf + usebuf*width, b + stealb*width) <= 0) { + usebuf++; + } else { + stealb++; + } + } while (usebuf + stealb < bufnmel); + if (stealb) { + swap(a - stealb*width, b, stealb*width); + add_counts(counts + STEAL_BUF, &snapshot); + grailsort(b, bcount * blknmel, width, cmp); + } else { + add_counts(counts + STEAL_BUF, &snapshot); + } + /* sort all the a and b blocks together by their head elements */ grailsort(a, blocks, bwidth, cmp); @@ -102,7 +135,6 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) } grailsort(buf, bufnmel, width, cmp); - distribute_buffer(buf, bufnmel, nmel - bufnmel, width, cmp); #if 0 assert_sorted(base, nmel, width, cmp); -- cgit v1.2.3