sorting algorithms

One of the two workshops offered for the Algorithms and Data Structures course at the University of Ferrara.

This is a modular benchmarking framework for comparing various optimizations across sorting algorithms.

The following algorithms are implemented:

• insertion sort;
• merge sort;
• hybrid insertion-merge sort;
• quick sort;
• quick sort with median-of-three partition;
• tail-recursive quicksort;
• hybrid insertion-quick sort;
• heap sort;
• tim sort;
• introspective sort.

You can customize your benchmarking via a configuration file (see the Usage section). The running time of each algorithm is printed as an explicit matrix in the results folder; optionally, if gnuplot is installed on your system, a plot is generated too.

Certain algorithms are designed to exploit existing patterns in data (e.g., tim sort); you can customize how testing inputs are generated by implementing your own interface to the experiments (see the signatures in sort.h).

Usage

Fill your configuration file by following the example in config/config.toml.example. Run make and execute the binary, providing the relative path of your configuration as the second argument.

Schema

This is an overview of the project.

flowchart TB

    MAIN["main"]

    subgraph Configuration
        CONFIG["config"]
        TOML["tomlc17"]
        STRUCT["struct configuration"]
    end

    subgraph Experiments
        BENCH["benchmark"]
    end

    subgraph External Logic
        SORT["sort"]
        PLOT["plot"]
    end

    MAIN -->|load| CONFIG
    CONFIG -->|read TOML| TOML
    CONFIG -->|populate| STRUCT

    MAIN -->|execute| BENCH
    BENCH -->|fetch parameters| STRUCT

    BENCH -->|genera input| SORT
    BENCH -->|execute algorithm| SORT
    BENCH -->|test| SORT

    BENCH -->|plots| PLOT

Loading

The Configuration module has two responsibilities: defining the configuration structure and loading it. A possible example is given below.

classDiagram

class configuration {
    char name[NAME_BUF]

    char algorithms[ALGO_BUF][NAME_BUF]
    uint8_t algorithm_count

    uint8_t step

    uint32_t repetitions

    uint64_t min_size
    uint64_t max_size

    uint64_t seed
}

Loading

The main function is the entry point of the programme and acts as the driver for the experiments.

The loading of the configuration is delegated to a Configuration module, which fills a structure (see above) to be passed to the Experiments module.

The experiments are responsible for: 1. iterating through a list of algorithms whose performance is to be measured; 2. for each algorithm, generating a random input; 3. calling the algorithm and measuring its execution time; 4. saving the measured time; 5. checking the correctness of the algorithm; 6. repeating step 2 as specified by the configuration; 7. returning the average of the execution times.

Note that steps 1, 2, and 5 of the process above do not know in advance which logic to call. A responsibility is therefore added to the Experiments module: that of exposing three interfaces.

graph TD
    Benchmark[Benchmark]

    Generator[Input generator]
    AlgorithmSelection[Algorithm selector]
    Test[Test strategy]

    Benchmark -->|espone interfaccia| Generator
    Benchmark -->|espone interfaccia| AlgorithmSelection
    Benchmark -->|espone interfaccia| Test

Loading

The External logic module implements these interfaces.

Because of this, you could try to extend this package and also handle the benchmarking of more complex algorithms or operations of certain data structures.

graph BT
    Generator[Input generator]
    AlgorithmSelection[Algorithm selector]
    Test[Test strategy]

    Sort[Sorting]

    Sort -->|implements interface| Generator
    Sort -->|implements interface| AlgorithmSelection
    Sort -->|implements interface| Test

Loading

Last but not least, we want to write the results. The simplest way is to print them as a matrix in the results folder. However, if available, gnuplot (see here) is leveraged.

Credits

Big thanks to the contributors of tomlc17. It is an easy to understand and robust library for parsing toml files.

A big thumb-up for gnuplot, too!