diff options
-rw-r--r-- | hist-sort.c | 17 |
1 files changed, 17 insertions, 0 deletions
diff --git a/hist-sort.c b/hist-sort.c index 8b88dd4..b5166dc 100644 --- a/hist-sort.c +++ b/hist-sort.c @@ -1,3 +1,20 @@ +/** + * Histogram sort + * + * This sort is interesting in that it is a "comparison-free" sort. That is to + * say that it doesn't ever directly compare two items against each other to + * determine the larger one, much like conventional sorting algorithms does. + * + * Instead, a histogram is built by counting the frequency of each value in + * the input set. Then, a sorted output set is constructed from this histogram + * since it is implicitly in order. + * + * This has the disadvantage of becoming heavy on memory usage when the input + * values increase in range. Theoretically, if the range was high, but sparse, + * some simple compression could be applied. There's an area for + * experimentation. + */ + #include <stdio.h> #include <stdlib.h> #include <time.h> |