compsort

Source ยป Wikipedia

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

Program was tested with g++. To compile you may have to use -lboost_program_options.

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 --help
Allowed options:

General options:
  --help                     produce this help message
  --quiet                    disable printing sorted list
  --time                     print CPU time for each algorithm
  --prec arg (=21)           set OUTPUT precision
  --avg arg (=1)             rerun sorting a specified number times on the same
                             list
  --delim arg (= )           delimiters used when printing lists, wrap in
                             quotation marks, escape characters as needed

Fill options:
  --list arg                 input a list of values
  --fill-rand arg (=10)      fill the list random numbers
  --rand-lower arg (=-10)    specify the lower bound for '--fill-rand'
  --rand-upper arg (=10)     specify the upper bound for '--fill-rand'
  --fill-forward arg         fill the list with incrementing numbers
  --fill-backward arg        fill the list with decrementing numbers
  --fill-increment arg (=1)  specify the fill increment used with
                             '--fill-forward' and '--fill-backward'

Algorithm options:
  --alg-all                  use all available algorithms
  --alg-except arg           except algorithms when using '--alg-all', wrap
                             each argument in quotation marks
  --alg-bogosort             use the bogosort algorithm
  --alg-bubble-sort          use the bubble sort algorithm
  --alg-cocktail-sort        use the cocktail shaker sort
  --alg-gnome-sort           use the gnome sort algorithm
  --alg-heap-sort            use the heap sort algorithm
  --alg-insertion-sort       use the insertion sort algorithm
  --alg-merge-sort           use the merge sort algorithm
  --alg-permutation-sort     use the permutation sort algorithm
  --alg-quick-sort           use the quick sort algorithm
  --alg-selection-sort       use the selection sort algorithm

compsort.cpp

Example

$ ./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