diff options
Diffstat (limited to 'wikisort.c')
| -rw-r--r-- | wikisort.c | 104 |
1 files changed, 3 insertions, 101 deletions
@@ -1,42 +1,14 @@ #include <math.h> #include <stddef.h> -#include <stdint.h> -#include <string.h> #include "sorters.h" +#include "common.h" struct array { char *base; size_t nmel; }; -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); -} - /* buf must be large enough to hold as->nmel elements */ static void merge_blocks(char *buf, struct array *as, size_t bs_nmel, size_t width, cmpfun cmp) { @@ -69,28 +41,6 @@ static char *find_min_block(char *base, size_t count, size_t bwidth, size_t widt return min; } -/* 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 roll(struct array *a, struct array *b, size_t bwidth, size_t width, char **mina, cmpfun cmp) { @@ -106,60 +56,12 @@ static size_t roll(struct array *a, struct array *b, return iters; } -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 }; - void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp) { char *base = unsorted; - /* use a sorting network for small inputs */ - if (nmel <= 8) { - 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); - } + if (nmel <= MAX_SORTNET) { + sorting_network(base, nmel, width, cmp); return; } |