Compsort

Source ยป Wikipedia

Compsort is a program used to compare common sorting algorithms. This program takes advantage of Boost's program options library.

Code was tested on Linux and compiled with g++ version 7.2.1. In order to compile you may have to use the -lboost_program_options flag. I compiled using the following flags, mostly for debugging purposes:

-Wall -Wextra -Wconversion -pedantic-errors -lboost_program_options

Compsort was tested with Valgrind using -v --track-origins=yes, resulting in 0 errors and no leaks possible.

A majority of the code for the sorting comes from Rosetta Code. I did not feel that it was appropriate, nor necessary, to reinvent the wheel. I made changes to most of the sorting code: removing helper functions, improving performance, cleaning up namespaces, etc. Everything else is my own work.

Compsort only supports full command line arguments, for example: use --help instead of -h.

compsort.cpp

Example output

$ ./compsort --alg-all --quiet --time --fill-rand 1000 --avg 100 --alg-except bogosort permutation-sort
Bubble Sort:      Average CPU time: 0.019333 s
Cocktail Sort:    Average CPU time: 0.016363 s
Gnome Sort:       Average CPU time: 0.013114 s
Heap Sort:        Average CPU time: 0.000540 s
Insertion Sort:   Average CPU time: 0.000961 s
Merge Sort:       Average CPU time: 0.000446 s
Quick Sort:       Average CPU time: 0.000629 s
Selection Sort:   Average CPU time: 0.008658 s
$ ./compsort --alg-all --quiet --time --fill-forward 1000 --avg 100 --alg-except bogosort permutation-sort
Bubble Sort:      Average CPU time: 0.000019 s
Cocktail Sort:    Average CPU time: 0.000019 s
Gnome Sort:       Average CPU time: 0.000019 s
Heap Sort:        Average CPU time: 0.000515 s
Insertion Sort:   Average CPU time: 0.000243 s
Merge Sort:       Average CPU time: 0.000489 s
Quick Sort:       Average CPU time: 0.000287 s
Selection Sort:   Average CPU time: 0.008787 s

Note: I recommend excluding the bogosort and permutation sort algorithms for most use cases. Bogosort and permutation sort are incredibly slow for larger lists due to the way they sort. Bogosort randomly shuffles the list until it happens to be sorted, and permutation sort goes through each iterative permutation until the list is sorted.

$ ./compsort --alg-all --prec 2 --time --avg 10
Before:
-5.75 -5.36 10.00 -6.77 6.40 8.35 -4.61 -2.09 -8.82 -5.56

Bogosort:         Average CPU time: 4.431480 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Bubble Sort:      Average CPU time: 0.000003 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Cocktail Sort:    Average CPU time: 0.000002 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Gnome Sort:       Average CPU time: 0.000003 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Heap Sort:        Average CPU time: 0.000003 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Insertion Sort:   Average CPU time: 0.000002 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Merge Sort:       Average CPU time: 0.000005 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Permutation Sort: Average CPU time: 0.355662 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Quick Sort:       Average CPU time: 0.000003 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00

Selection Sort:   Average CPU time: 0.000003 s
-8.82 -6.77 -5.75 -5.56 -5.36 -4.61 -2.09 6.40 8.35 10.00