Author: Piotr Pelczar (piotpel817@student.polsl.pl)
Silesian University of Technology, Algorithms and Data Structures course.
Full article is avaliable under:
http://athlan.pl/incopy/polsl-benchmark-sort-algorithms/Main.pdf
This paper describes and compares counting sort and bucket sort algorithms implementations written in C language. The main doubt is what is the impact of pointers operations in bucket sort relatively to single operations on arrays in counting sort.
- TeX paper is under
article
directory - Source code is under
code
directory bin
directory contains some Bash scripts utils
Counting sort is more effective than Bucket sort (4.76 times in average and 5.91 times for full optimization) in all cases for key range from 0 to 65k. Key range (in integer range) have no impact on time consumtion.
Moreover, gcc optimization have huge impact for Bucket sort which has operations on pointers (132% faster) and small impact for Counting sort (22% faster).
Operations on pointers can be strongly optimized and have huge impact on algorithms.
There are several utils in this project:
./bin/compile.sh
or in all gcc modes:
./bin/compile-all-optimizations.sh
Results will be stored in ./target
If you want to output COUNT numbers from MIN_VALUE to MAX_VALUE, each in new line, just type:
./bin/rand-dataset.sh MIN_VALUE MAX_VALUE COUNT > somefile.txt
You can edit script and and run. Results are in CSV format, separated by semicolon.
./bin/run-benchmark.sh > some_results.csv
To compile tex article, please ensure, taht you have pdflatex
in your $PATH
and run:
./bin/print-tex.sh