# Empirical Evaluation of Classic Sorting Algorithms

<!--toc:start-->

-   [Empirical Evaluation of Classic Sorting Algorithms](#empirical-evaluation-of-classic-sorting-algorithms)
    -   [Overview](#overview)
        -   [Machine-Dependent Time Graph](#machine-dependent-time-graph)
        -   [Algorithms Implemented](#algorithms-implemented)
    -   [Results and Report](#results-and-report)
        -   [Full Sorting Results](#full-sorting-results)
        -   [Final Report](#final-report)
        -   [Comparison Table](#comparison-table)
    -   [Plots](#plots)
        -   [Number of Comparisons vs Input Size](#number-of-comparisons-vs-input-size)
        -   [Execution Time vs Input Size](#execution-time-vs-input-size)
        -   [Memory Usage vs Input Size](#memory-usage-vs-input-size)
    -   [Requirements](#requirements)
    -   [Project Structure](#project-structure)
    <!--toc:end-->

**Data Structures And Algorithm Analysis**

This project explores the relative empirical performances of four fundamental sorting algorithms:

-   Quick Sort (Random Pivot)
-   Quick Sort (Deterministic Pivot)
-   Merge Sort
-   Heap Sort

The goal is to evaluate these algorithms by comparing their number of comparisons, execution time, and memory usage when sorting datasets of various sizes. This project emphasizes empirical evaluation, analyzing performance with both randomly generated datasets and specially ordered datasets (non-decreasing and non-increasing order).

## Overview

The project benchmarks the sorting algorithms across a range of dataset sizes (10,000 to 800,000 elements). It measures performance by counting the number of comparisons, recording execution time, and monitoring memory usage for different input configurations. This approach highlights differences in performance, particularly as input size increases, and how each algorithm handles ordered and random data.

The performance evaluation is visualized through detailed comparison tables and graphical plots showing how the number of comparisons scales with input size. The final results provide insight into how the empirical data matches the worst-case time complexities of each algorithm.

### Machine-Dependent Time Graph

While the number of comparisons is the most reliable metric for measuring an algorithm’s performance, a machine-dependent time graph is also generated for perspective purposes. This graph measures the execution time of each algorithm in seconds on the specific machine used for testing, providing additional context for performance on a particular hardware setup. However, note that these times can vary significantly based on the hardware, so they are not generalizable across different systems.

**Note:** The running time reported for each sorting algorithm excludes time spent on dataset generation, dataset copying, or any other overhead operations. The measurement focuses solely on the algorithm execution time for fair and accurate benchmarking.

**Disclaimer:** The process of detecting memory usage (e.g., using `tracemalloc`) may introduce additional overhead to the execution time measurements. Despite this, all algorithms are subjected to the same memory detection process, ensuring that the relative performance comparisons remain valid. The actual data is proportional and relative to the number of comparisons made, maintaining fairness across all algorithms.

### Algorithms Implemented

1. **Quick Sort (Random Pivot)**: Uses random pivot selection to avoid worst-case scenarios in average cases.

2. **Quick Sort (Deterministic Pivot)**: Uses the last element as the pivot. This version is implemented iteratively to handle large datasets without exceeding recursion limits.

3. **Merge Sort**: A classic divide-and-conquer sorting algorithm with O(n log n) time complexity.

4. **Heap Sort**: An in-place sorting algorithm based on the heap data structure.

## Results and Report

### Full Sorting Results

-   [Full Sorting Results (Markdown)](/results/sorting_results.md)
    Detailed empirical comparison of all algorithms across multiple dataset sizes.

### Final Report

-   [Final Report (PDF)](/report/report.pdf)
    Full analysis and comparison of the sorting algorithms, including discussion of empirical and theoretical complexities.

### Comparison Table

Below is the comparison table summarizing the number of comparisons made by each algorithm on non-decreasing and non-increasing datasets:

![](/results/comparison_table.png)

## Plots

### Number of Comparisons vs Input Size

-   **Input Sizes 10,000 to 100,000**

    ![Comparisons 10,000 to 100,000](/results/comparisons_10000_to_100000.png)

-   **Input Sizes 100,000 to 800,000**

    ![Comparisons 100,000 to 800,000](/results/comparisons_100000_to_800000.png)

### Execution Time vs Input Size

-   **Input Sizes 10,000 to 100,000**

    ![Time 10,000 to 100,000](/results/time_10000_to_100000.png)

-   **Input Sizes 100,000 to 800,000**

    ![Time 100,000 to 800,000](/results/time_100000_to_800000.png)

### Memory Usage vs Input Size

-   **Input Sizes 10,000 to 100,000**

    ![Memory Usage 10,000 to 100,000](/results/memory_10000_to_100000.png)

-   **Input Sizes 100,000 to 800,000**

    ![Memory Usage 100,000 to 800,000](/results/memory_100000_to_800000.png)

## Requirements

To run the project and generate the plots and tables, you need to install the following Python packages:

-   **numpy**
-   **matplotlib**
-   **pandas**
-   **tabulate**

You can install them using the following command:

```bash
conda env create -f environment.yml
```

## Project Structure

```
./
│
├── data/                          # Contains generated datasets for different input sizes
│   ├── size_10000/
│   │   ├── input_1.txt
│   │   ├── input_2.txt
│   │   └── ...
│   ├── size_20000/
│   ├── ...
│   └── size_800000/
│
├── report/
│   └── report.pdf                 # Final report
│
├── results/                       # Contains results data and comparison plots
│   ├── comparison_table.md               # Table of sorted results for non-decreasing and non-increasing datasets
│   ├── comparison_table.png              # PNG image of the comparison table
│   ├── comparisons_10000_to_100000.png   # Plot of comparisons for input sizes 10,000 to 100,000
│   ├── comparisons_100000_to_800000.png  # Plot of comparisons for input sizes 100,000 to 800,000
│   ├── memory_10000_to_100000.png        # Plot of memory usage for input sizes 10,000 to 100,000
│   ├── memory_100000_to_800000.png       # Plot of memory usage for input sizes 100,000 to 800,000
│   ├── time_10000_to_100000.png          # Plot of times for input sizes 10,000 to 100,000
│   ├── time_100000_to_800000.png         # Plot of times for input sizes 100,000 to 800,000
│   ├── plot_data.csv                     # CSV data for plotting comparisons and times
│   ├── table_data.csv                    # CSV data for table of sorted comparisons
│   └── sorting_results.md                # Markdown report of the sorting comparisons and timings
│
├── src/
│   ├── generate_datasets.py       # Script to generate random datasets
│   ├── sorting_algorithms.py      # Sorting algorithms (Quick Sort, Merge Sort, Heap Sort)
│   ├── main.py                    # Main script to run sorting and collect comparison data
│   ├── plotting_script.py         # Script to generate plots from comparison data
│   └── table_script.py            # Script to generate tables from comparison data
│
├── tests/                         # Test files for sorting algorithms on different input types
│
├── README.md
└── environment.yml               # Python environment dependencies
```