From e0bdb91c26bd7c82f0ffc050256e5c354adef5ce Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Sun, 6 Jul 2014 16:15:03 -0500 Subject: Add an implementation of grailsort --- grailsort.c | 192 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ sorters.c | 1 + sorters.h | 1 + 3 files changed, 194 insertions(+) create mode 100644 grailsort.c diff --git a/grailsort.c b/grailsort.c new file mode 100644 index 0000000..c7a4074 --- /dev/null +++ b/grailsort.c @@ -0,0 +1,192 @@ +#include +#include +#include + +#include "sorters.h" + +#define TAIL(base,nmel,width) ((base) + ((nmel) - 1) * (width)) + +static void swap(char *a, char *b, size_t width) +{ + while (width--) { + char tmp = *a; + *a++ = *b; + *b++ = tmp; + } +} + +static void reverse(char *base, size_t nmel, size_t width) +{ + char *last = base + (nmel - 1) * width; + while (last > base) { + swap(base, last, width); + base += width; + last -= width; + } +} + +/* rotates left */ +static void rotate(char *base, size_t nmel, size_t width, size_t shift) +{ + reverse(base, shift, width); + reverse(base + shift * width, nmel - shift, width); + reverse(base, nmel, width); +} + +/* If a matching element exists, returns index of one of them. + If none exists, returns index where such an element should be inserted. */ +static size_t binary_search(const char *needle, char *haystack, + size_t nmel, size_t width, cmpfun cmp) +{ + size_t baseidx = 0; + while (nmel) { + size_t tryidx = baseidx + nmel / 2; + char *try = haystack + tryidx * width; + int sign = cmp(try, needle); + if (!sign) return tryidx; + else if (sign < 0) { + baseidx = tryidx + 1; + nmel -= nmel / 2 + 1; + } + else { + nmel /= 2; + } + } + return baseidx; +} + +static size_t merge(char *buf, char *base, size_t anmel, size_t bnmel, size_t width, cmpfun cmp) +{ + char *a = buf; + char *b = base + anmel * width; + size_t sorted = binary_search(b, base, anmel, width, cmp); + base += sorted * width; + anmel -= sorted; + + swap(base, a, anmel * width); + + while (anmel > 0 && bnmel > 0) { + if (cmp(a, b) <= 0) { + swap(base, a, width); + a += width; + anmel--; + } else { + swap(base, b, width); + b += width; + bnmel--; + } + base += width; + } + + swap(base, a, anmel * width); + return sorted; +} + +/* get index of last block whose head is less than the previous block's tail */ +static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp) +{ + for (char *cur = TAIL(base, bcount, bwidth); --bcount; cur -= bwidth) + if (cmp(cur - width, cur) > 0) break; + return bcount; +} + +static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp) +{ + char *sorted = base + bufnmel * width; + while (bufnmel) { + char *last = sorted - width; + size_t equals; + for (equals = 1; equals < bufnmel; equals++) { + if (cmp(last, last - equals * width)) break; + } + + size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp); + rotate(sorted - equals * width, insertpos + equals, width, equals); + + bufnmel -= equals; + sortnmel += equals; + sorted -= equals * width; + } +} + +static const uint8_t sortnet[][2] = { + /* 0: index = 0 */ + /* 1: index = 0 */ + /* 2: index = 0 */ + {0,1}, + /* 3: index = 1 */ + {0,1}, {0,2}, {1,2}, + /* 4: index = 4 */ + {0,1}, {2,3}, {0,2}, {1,3}, {1,2}, + /* 5: index = 9 */ + {0,1}, {3,4}, {2,4}, {2,3}, {1,4}, {0,3}, {0,2}, {1,3}, {1,2}, + /* 6: index = 18 */ + {1,2}, {4,5}, {0,2}, {3,5}, {0,1}, {3,4}, {2,5}, {0,3}, {1,4}, {2,4}, + {1,3}, {2,3}, + /* 7: index = 30 */ + {1,2}, {3,4}, {5,6}, {0,2}, {3,5}, {4,6}, {0,1}, {4,5}, {2,6}, {0,4}, + {1,5}, {0,3}, {2,5}, {1,3}, {2,4}, {2,3}, + /* 8: index = 46 */ + {0,1}, {2,3}, {4,5}, {6,7}, {0,2}, {1,3}, {4,6}, {5,7}, {1,2}, {5,6}, + {0,4}, {3,7}, {1,5}, {2,6}, {1,4}, {3,6}, {2,4}, {3,5}, {3,4}, + /* 9: index = 65, if we used a sorting network this large */ +}; + +static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 }; + +static void sorting_network(char *base, size_t nmel, size_t width, cmpfun cmp) +{ + for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) { + char *elem1 = base + sortnet[i][0] * width; + char *elem2 = base + sortnet[i][1] * width; + if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width); + } +} + +void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) +{ + char *base = unsorted; + + if (nmel <= 8) { + sorting_network(base, nmel, width, cmp); + return; + } + + size_t blknmel = sqrt(nmel); /* elements in a block */ + size_t bufnmel = blknmel + nmel % blknmel; /* elements in the buffer */ + size_t bwidth = blknmel * width; /* size of a block in bytes */ + size_t blocks = nmel / blknmel - 1; /* number of blocks in a + b */ + size_t acount = blocks / 2; + size_t bcount = blocks - acount; + + char *a = base + bufnmel * width; + char *b = a + acount * bwidth; + + /* sort the buffer as if it were part of the a array */ + grailsort(base, bufnmel + acount * blknmel, width, cmp); + grailsort(b, bcount * blknmel, width, cmp); + + /* if already sorted, nothing to do */ + if (cmp(TAIL(a, acount * blknmel, width), b) <= 0) return; + + /* if blocks in b are all less than those in a, just need a rotate */ + if (cmp(TAIL(base, nmel, width), base) <= 0) { + rotate(base, nmel, width, acount * blknmel + bufnmel); + return; + } + + /* sort all the a and b blocks together by their head elements */ + grailsort(a, blocks, bwidth, cmp); + + /* merge, starting from the end and working towards the beginning */ + size_t pending = 0; + while (blocks > 1) { + size_t overlap = last_overlap(a, blocks, bwidth, width, cmp); + if (overlap == 0) break; + pending = merge(base, TAIL(a, overlap, bwidth), blknmel, (blocks - overlap) * blknmel, width, cmp); + blocks = overlap; + } + + grailsort(base, bufnmel, width, cmp); + distribute_buffer(base, bufnmel, nmel - bufnmel, width, cmp); +} diff --git a/sorters.c b/sorters.c index c2d04e5..2e9acc9 100644 --- a/sorters.c +++ b/sorters.c @@ -10,6 +10,7 @@ const struct sorter sorters[] = { { .name = "musl", .func = musl_qsort }, { .name = "wikisort", .func = wikisort }, { .name = "wikisort (ref)", .func = wikisort_ref }, + { .name = "grailsort", .func = grailsort }, { 0 } }; diff --git a/sorters.h b/sorters.h index 669f5c4..76c5443 100644 --- a/sorters.h +++ b/sorters.h @@ -11,6 +11,7 @@ void glibc_mergesort(void *, size_t, size_t, cmpfun); void freebsd_qsort(void *, size_t, size_t, cmpfun); void wikisort(void *, size_t, size_t, cmpfun); void wikisort_ref(void *, size_t, size_t, cmpfun); +void grailsort(void *, size_t, size_t, cmpfun); extern const struct sorter { const char *name; -- cgit v1.2.3