Benchmarking Sorting Algorithms

This project implements five classic sorting algorithms:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

The program measures the number of comparisons, number of swaps, and time taken (in microseconds) for each algorithm in best, average, and worst cases across multiple input sizes.

🚀 Getting Started

Prerequisites

To build and run this project, you will need:

• A C++17 compatible compiler (e.g., g++)
• make utility
• Python 3 with pandas and matplotlib libraries installed. You can install them using pip:

  pip install pandas matplotlib

Building and Running

1. Clone the repository:

   git clone https://github.com/arhamgarg/sorting-benchmark.git
   cd sorting-benchmark

2. Run the benchmark:

   make

   This command will:
   • Compile the C++ source files.
   • Run the benchmark executable.
   • Save the results into data/results.csv.
   • Clean up all compiled binaries and the executable.
3. Generate plots:

   python scripts/plot.py

   This will generate best_case.png, average_case.png, and worst_case.png files in the plots/ directory.

📊 Output Format

The program prints CSV-formatted data to standard output, which is then redirected to data/results.csv:

SIZE,CASE,ALGORITHM,COMPARISONS,SWAPS,TIME(us)

100,BEST,BUBBLE,99,0,0
100,BEST,SELECTION,4950,0,14
100,BEST,INSERTION,99,0,0
100,BEST,MERGE,356,0,7
100,BEST,QUICK,4950,5049,7

100,AVERAGE,BUBBLE,4940,2824,41
100,AVERAGE,SELECTION,4950,94,18
100,AVERAGE,INSERTION,2915,2824,4
100,AVERAGE,MERGE,544,0,10
100,AVERAGE,QUICK,661,392,5

100,WORST,BUBBLE,4950,4950,57
100,WORST,SELECTION,4950,50,16
100,WORST,INSERTION,4950,4950,5
100,WORST,MERGE,316,0,6
100,WORST,QUICK,4950,2549,8

📈 Performance Plots

The scripts/plot.py script generates the following plots visualising the performance of the sorting algorithms in different cases:

Best Case Performance

Average Case Performance

Worst Case Performance