Sort Algorithms Comparison

For full report in English see REPORT.md.

In this work 4 sorting algorithms -- Insertion sort, Merge Sort, Selection Sort and Shell Sort -- were implemented and compared in time and number of comparisons in 4 different cases:

• Random array (5 experiments were performed and average value was taken). Max value -- array size+1
• Ascending array with values already sorted. Max value -- array size+1
• Descending array with values sorted in reverse order. Max value -- array size + 1
• Random Low array -- contains only elements from the set {1, 2, 3} - that is, the array with many repeated elements (3 experiments were performed and the average value was taken)

Each of the 4 algorithms was ran in all of the 4 cases mentioned above for arrays of size 2^7, 2^8, .. up to 2^15 inclusive (array size step = 2)

The result of the experiments are graphs, built with matplotlib

Installation / Run experiment

If you want to reproduce the experiment on your machine, follow the instructions bellow (it is assumed that you have necessary build dependencies and using Linux OS. For other OS you may have to do some extra commands)

Clone repository:

$ git clone https://github.com/archy-co/imss_sort_algs.git
$ cd imss_sort_algs

Create build folder and run cmake and than make from there. This will create C++ executable file called sort in bin/ directory. You can then run this executable. This will print experiments results to the console output and generate .txt file in project root that will contain formatted data -- experiments outcome. Run following commands:

$ mkdir build && cd build
$ cmake .. -G"Unix Makefiles"
$ make
$ cd ..
$ ./bin/sort

You can also run visualize.py to (re)generate graphs from data in .txt. First create virtual environment (optional) and install matplotlib; then run python program to generate graphs. Commands (assuming that you've done previous step -- you've generated .txt file with experiments outcomes and your currently directory is project root):

$ python3 -m venv venv
$ source ./venv/bin/activate
$ pip install matplotlib

$ python3 visualize.py

You will then see graphs been changed in graphs/ directory.

Note, that generating graphs requires that you have graphs/ directory created and .txt file generated by C++ program in correct format. Otherwise graphs won't be created.

Author

Yaroslav Revera, UCU CS student