diff options
author | David Phillips <david@sighup.nz> | 2017-04-05 23:12:38 +1200 |
---|---|---|
committer | David Phillips <david@sighup.nz> | 2017-04-05 23:12:38 +1200 |
commit | 6191da80471187e447f7d40bd9f10258905cb25b (patch) | |
tree | 6e2174f7499a6f14f9034cf2b50127d0da65ebfa | |
download | interesting-sorts-6191da80471187e447f7d40bd9f10258905cb25b.tar.xz |
Add histogram sort
-rw-r--r-- | .gitignore | 1 | ||||
-rw-r--r-- | LICENCE | 27 | ||||
-rw-r--r-- | Makefile | 3 | ||||
-rw-r--r-- | config.mk | 1 | ||||
-rw-r--r-- | hist-sort.c | 76 |
5 files changed, 108 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..30960df --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +hist-sort @@ -0,0 +1,27 @@ +/* + * interesting-sorts - Small collections of sorting algorithms I found to be + * intriguing + * Copyright (c) 2017 David Phillips <dbphillipsnz@gmail.com> + * All rights reserved + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..0f34fd7 --- /dev/null +++ b/Makefile @@ -0,0 +1,3 @@ +include config.mk + +hist-sort: hist-sort.c diff --git a/config.mk b/config.mk new file mode 100644 index 0000000..c526342 --- /dev/null +++ b/config.mk @@ -0,0 +1 @@ +CFLAGS += -Wall diff --git a/hist-sort.c b/hist-sort.c new file mode 100644 index 0000000..409dcb1 --- /dev/null +++ b/hist-sort.c @@ -0,0 +1,76 @@ +#include <stdio.h> +#include <stdlib.h> +#include <time.h> + +#define RANGE 10000 +#define COUNT 10000 + +int is_sorted(unsigned int *data, size_t length) +{ + size_t i = 0; + + for (i = 0; i < length-1; i++) + if (data[i] > data[i+1]) + return 0; + + return 1; +} + +void fill_random(unsigned int *data, size_t length, unsigned int max) +{ + size_t i = 0; + + for (i = 0; i < length; i++) + data[i] = rand()%max+1; +} + +void sort(unsigned int *data, size_t length, unsigned int max) +{ + size_t *hist = calloc(max+1, sizeof(size_t)); + size_t i = 0; + size_t j = 0; + + for (i = 0; i < length; i++) { + hist[data[i]]++; + } + + j = 0; + for (i = 0; i < max+1; i++) { + for (; hist[i]; hist[i]--, j++) + data[j] = i; + } +} + +void dump_data(unsigned int *data, size_t length) +{ + size_t i = 0; + + for (i = 0; i < length; i++) + printf("%d, ", data[i]); + + fputc('\n', stdout); +} + +int main(int argc, char **argv) +{ + unsigned int *data = calloc(COUNT, sizeof(unsigned int)); + + if (!data) { + perror("calloc"); + return 1; + } + + srand(time(NULL)); + + fill_random(data, COUNT, RANGE); + + //dump_data(data, COUNT); + sort(data, COUNT, RANGE); + //dump_data(data, COUNT); + + if (!is_sorted(data, COUNT)) { + fprintf(stderr, "Failed: out of order\n"); + } else { + printf("Success.\n"); + } +} |