Java Sorting Benchmark

A comprehensive implementation and performance analysis of classic sorting classes.algorithms in Java.
This repository was created for educational purposes to demonstrate the practical differences between sorting classes.algorithms with varying time complexities.

---

Overview

This project provides:

1. A modular architecture, where each sorting algorithm (BubbleSort, InsertionSort, SelectionSort, MergeSort, QuickSort) implements a shared SortAlgorithm interface, ensuring flexibility and scalability.
2. A classes.SortFactory class that applies the Factory Design Pattern to dynamically create instances of sorting classes.algorithms at runtime based on user input.
3. A PerformanceTest class that benchmarks all implemented classes.algorithms under multiple real-world scenarios (random, sorted, and reverse-sorted datasets).
4. A detailed performance analysis connecting theoretical time complexity with practical execution results.

---

Implemented Algorithms

Each algorithm implements the SortAlgorithm interface, ensuring consistency and easy interchangeability.

Algorithm	Average Complexity	Strategy	Description
Bubble Sort	O(N²)	Comparison & Swap	Repeatedly compares adjacent elements and swaps them if out of order.
Selection Sort	O(N²)	Direct Selection	Finds the smallest element and moves it to its correct position.
Insertion Sort	O(N²) (avg), O(N) (best)	Incremental Insertion	Builds the sorted array one element at a time; ideal for small or nearly sorted arrays.
Merge Sort	O(N log N)	Divide & Conquer	Recursively divides the array, sorts each half, and merges them efficiently.
Quick Sort	O(N log N)	Divide & Conquer	Partitions the array around a pivot element and recursively sorts the sub-arrays. Highly efficient on average.

---

Performance Benchmark

To understand the practical implications of algorithmic complexity, a series of benchmarks was conducted.

Methodology

The tests were executed on arrays of 50,000 integers under three distinct scenarios:

1. Random Array: Represents the average case.
2. Sorted Array: Represents the best case for some classes.algorithms.
3. Reverse-Sorted Array: Represents the worst case for most simple classes.algorithms.

Test Environment

• CPU: Intel Core i5-9400F
• Memory: 16 GB DDR4
• Java Version: OpenJDK 17

Execution time was measured in milliseconds (ms).

---

Benchmark Results

Algorithm	Random Array (ms)	Sorted Array (ms)	Reverse-Sorted (ms)
Bubble Sort	4056	1360	1534
Selection Sort	963	976	828
Insertion Sort	641	0	1120
Merge Sort	10	3	3
Quick Sort	8	1	1

---

Analysis of Results

• Quick Sort: Often the fastest practical choice, with an average complexity of $O(N \log N) and great cache performance due to being in-place. Its $O(N²) worst-case is rare in good implementations.

• Merge Sort:
  Stands out for its consistency, with a guaranteed $O(N \log N) performance in all scenarios. It is a stable sort but requires extra $O(N) memory.

• Insertion Sort:
  While O(N²) in the average and worst cases, it performs exceptionally well (O(N)) on already sorted arrays — so fast it registered as 0 ms. Great for small or nearly sorted datasets.

• Selection Sort:
  Performance remains nearly constant across all scenarios, since it always performs the same number of comparisons, regardless of input order.

• Bubble Sort:
  The slowest overall, as expected for large datasets. Although its runtime varies slightly due to CPU branch prediction, it remains inefficient for practical applications.

---

How to Use

1. Selecting Algorithms with the Factory

import classes.SortFactory;
import interfaces.SortAlgorithm;

public class Main {
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};

        SortAlgorithm sorter = SortFactory.getSorter("quick");
        sorter.sort(array);

        System.out.println("Sorted array:");
        for (int num : array)
            System.out.print(num + " ");
    }
}

The factory (classes.SortFactory) accepts: "bubble", "selection", "insertion", "merge", "quick"

2. Running the Benchmark

You can run the main method in the PerformanceTest.java file to replicate the benchmark on your own machine. Feel free to adjust the ARRAY_SIZE constant to test with different dataset sizes.