| Commit message (Collapse) | Author | Age | Files | Lines | |
|---|---|---|---|---|---|
| * | Slightly simplify grailsort | Bobby Bingham | 2014-08-16 | 1 | -7/+8 |
| | | | | | | Remove unused pending variable, and unused return value from merge(). Saves 29 bytes on x86_64. | ||||
| * | Delete portions of grailsort reference code we're not using | Bobby Bingham | 2014-08-16 | 1 | -136/+19 |
| | | | | | | | There's a lot of code in here that works with an externally provided extra buffer, but because we're not testing with that, it unfairly skews the code size against this algorithm. | ||||
| * | Remove duplicate declarations of MIN_SIZE and MAX_SIZE | Bobby Bingham | 2014-08-03 | 1 | -3/+0 |
| | | |||||
| * | Add quicksort-killer testcase | Bobby Bingham | 2014-08-03 | 1 | -0/+31 |
| | | | | | | | | This doesn't generate an input sequence up-front, but rather generates it on the fly in response to the order in which the algorithm is comparing elements in such a way as to invoke quadratic runtime in most quicksort implementations. | ||||
| * | Make global state explicit in testcase generators | Bobby Bingham | 2014-08-03 | 5 | -26/+23 |
| | | | | | | | | The quicksort-killer testcase will require more global state, unless we go to the effort of implementing qsort_r versions of all the sorting algorithms. Since we're not doing that, we'll simply make the global state explicit. | ||||
| * | Rename generators to testcases | Bobby Bingham | 2014-08-03 | 5 | -110/+119 |
| | | | | | | | This is in preparation for adding an implementation of the quicksort-killer test case, which requires a custom comparison function rather than just a custom imput-generation function. | ||||
| * | Remove unnecessary test of bnmel | Bobby Bingham | 2014-08-03 | 1 | -1/+1 |
| | | |||||
| * | Reformat | Bobby Bingham | 2014-07-31 | 1 | -10/+3 |
| | | |||||
| * | Remove grailsort dependency on bsearch | Bobby Bingham | 2014-07-31 | 1 | -3/+3 |
| | | |||||
| * | Optimize swap for larger swaps | Bobby Bingham | 2014-07-31 | 1 | -0/+14 |
| | | |||||
| * | Don't pre-sort the temp swap buffer | Bobby Bingham | 2014-07-31 | 1 | -4/+5 |
| | | | | | | | | | | This is a close call. On the one hand, this buffer will get jumbled when used for merging adjacent blocks, so we'll need to sort it again before distributing it. On the other hand, by sorting it early, we know that we won't have to distribute it very far. In testing, pre-sorting seems to lose out overall. | ||||
| * | Don't special-case reverse sort order | Bobby Bingham | 2014-07-31 | 1 | -6/+0 |
| | | | | | This increases code size, and doesn't seem to help very significantly. | ||||
| * | Use linear search when distributing buffer | Bobby Bingham | 2014-07-31 | 1 | -4/+2 |
| | | |||||
| * | Add reference grailsort implementation | Bobby Bingham | 2014-07-31 | 3 | -0/+516 |
| | | |||||
| * | Factor out binary_search | Bobby Bingham | 2014-07-17 | 2 | -21/+26 |
| | | |||||
| * | Vastly improve performance of distribute_buffer | Bobby Bingham | 2014-07-06 | 1 | -10/+11 |
| | | |||||
| * | Move wikisort/grailsort common code to a shared header | Bobby Bingham | 2014-07-06 | 4 | -210/+123 |
| | | |||||
| * | Add a generator for slightly noisy reverse order data | Bobby Bingham | 2014-07-06 | 1 | -9/+20 |
| | | |||||
| * | Add an implementation of grailsort | Bobby Bingham | 2014-07-06 | 3 | -0/+194 |
| | | |||||
| * | Add the C++ reference wikisort implementation | Bobby Bingham | 2014-07-04 | 4 | -8/+985 |
| | | |||||
| * | Remove unnecessary safeguard in rotate | Bobby Bingham | 2014-06-30 | 1 | -1/+0 |
| | | |||||
| * | Move penda info into a struct array | Bobby Bingham | 2014-06-30 | 1 | -24/+25 |
| | | |||||
| * | Small cleanup | Bobby Bingham | 2014-06-30 | 1 | -5/+2 |
| | | |||||
| * | Use an array structure to track the temp buffer | Bobby Bingham | 2014-06-30 | 1 | -12/+13 |
| | | |||||
| * | Rename stract blockarray to more generic "array" | Bobby Bingham | 2014-06-29 | 1 | -15/+15 |
| | | |||||
| * | Don't bother merging when there are no pending elements | Bobby Bingham | 2014-06-29 | 1 | -3/+6 |
| | | |||||
| * | Don't roll a b block if it doesn't make sense to | Bobby Bingham | 2014-06-29 | 1 | -6/+2 |
| | | | | | | | | This added a pathological case where each iteration we'd roll a b block into place, just to have to do a giant rotate to move all the accumulated b blocks over to make room for the a block that should have been inserted next. | ||||
| * | Add generator of mostly sorted data | Bobby Bingham | 2014-06-29 | 1 | -4/+20 |
| | | |||||
| * | Build with -Os | Bobby Bingham | 2014-06-29 | 1 | -1/+1 |
| | | |||||
| * | Run smaller test cases before larger | Bobby Bingham | 2014-06-29 | 1 | -2/+2 |
| | | |||||
| * | Move assert_sorted helper somewhere more public | Bobby Bingham | 2014-06-29 | 3 | -10/+15 |
| | | |||||
| * | Generate nicer numbers for debugging | Bobby Bingham | 2014-06-29 | 1 | -1/+14 |
| | | |||||
| * | Add wikisort optimizations for some common cases | Bobby Bingham | 2014-06-29 | 1 | -0/+9 |
| | | |||||
| * | Initial stab at wikisort | Bobby Bingham | 2014-06-29 | 4 | -1/+227 |
| | | |||||
| * | Add freebsd's qsort | Bobby Bingham | 2014-06-21 | 3 | -0/+168 |
| | | |||||
| * | validate that sorter succeeded in sorting the input | Bobby Bingham | 2014-06-21 | 1 | -0/+11 |
| | | |||||
| * | Add glibc's sorts | Bobby Bingham | 2014-06-21 | 6 | -4/+566 |
| | | | | | Also rename musl's sort function for more consistency. | ||||
| * | Initial commit: benchmark musl's qsort | Bobby Bingham | 2014-06-20 | 7 | -0/+369 |
 |
index : qsort comparisons | |
| qsort algorithm comparative benchmarks |
| summaryrefslogtreecommitdiff |